Since its inception 20 years ago, SCIP has become one of the most versatile solvers and frameworks for research in mixed integer optimization. The first recorded commit message documenting the start of SCIP's development dates back to October 23, 2002. High time to come together and discuss past, present and future developments!
The spotlight will be on SCIP, but the workshop welcomes a broad audience interested in computational optimization and its theoretical underpinnings. The workshop invites contributed presentations: find registration information below!
It was a great workshop, thank you everybody!
The scientific programme is scheduled for 9:30am6:00pm. We are excited to host two invited speakers with talks on their latest research in computational mixed integer optimization:
Merve Bodur,
University of Toronto:
“Methodological Advances in Twostage Stochastic Programming”
Domenico Salvagnin,
Università di Padova:
“A fixpropagaterepair heuristic for Mixed Integer Programming”
The programme will feature many more presentations on applications of SCIP and the latest algorithmic developments in mixed integer optimization by the following speakers:
The day will be concluded by a birthday celebration at Gastraum Esskultur starting at 6:00pm.
The workshop will be free of charge. For any questions contact us at scip20workshop@zib.de.
Zuse Institute Berlin, main lecture hall and and seminar room of ZIB.
Online streaming, available via zoom and in FU/Rostlaube in Rooms KL 29/235 and JK 29/124
Registration and stream of nonparallel sessions will be in KL 29/235.
You can find some travel and accomodation hints on the ZIB Contact page or on the website of the city of Berlin (search for districts "Zehlendorf" and "Steglitz" for nearby locations).
Ambros Gleixner, Zuse Institute and HTW Berlin
Marc Pfetsch, TU Darmstadt
Sebastian Pokutta, Zuse Institute and TU Berlin
Franziska Schlösser, Zuse Institute Berlin
To see the abstract of a talk, please click on its title.
Time 
Lecture hall
Seminar room


09:00  Registration 
09:30 
Opening 
09:45 
Tobias Achterberg, Gurobi Optimization
SCIP Origins
The source code repository of SCIP was created in October 2002.
Since then, SCIP evolved into a very large project with many contributors, and it is still active today.
We report on the circumstances that lead to the invention of SCIP and touch on some of the events in the early days of SCIP that influenced its design. 
10:00 
Marc Pfetsch, TU Darmstadt
SCIP: Past, Present, Future
TBA

10:30  Coffeebreak 
10:45 
Merve Bodur, University of Toronto
Methodological Advances in Twostage Stochastic Programming
Stochastic programming is a useful framework for dealing with uncertainty and integrality requirements in optimization problems.
In this talk, we focus on twostage stochastic integer programs (2SIPs), in particular their sample average approximations which yield computationally challenging mixedinteger programming (MIP) models.
For various classes of 2SIPs, we review commonly used decomposition approaches (most notably logicbased Benders decomposition variants), and present some important enhancement strategies such as incorporation of general purpose cutting planes from the MIP literature.
We also introduce several recently proposed techniques, such as the uses of (i) decision diagrams to convexify the secondstage problems, (ii) machine learning to learn the recourse value functions as well as cut selection/generation, and (iii) MIPbased methodology for scenario reduction.
For the presented methods, we provide numerical results on problems from a variety of application domains.

11:45 
Christopher Hojny, TU Eindhoven
Symmetry Handling in SCIP  An Overview
Symmetries are wellknown to deteriorate the performance of branchandbound
Since the release of version 5.0, SCIP is able to automatically handle symmetries and its symmetry handling methods have been continuously improved and extended since then
In this presentation, I will provide an overview of the different symmetry handling methods that are available in SCIP
Moreover, I will discuss ways how users can provide SCIP with symmetry information.
James Cussens, University of Bristol
Branchpriceandcut for Bayesian network structure learning
Bayesian network structure learning (BNSL) is an NPhard problem where, given some observed data, the goal is to find a directed acyclic graph (DAG) that maximises an objective defined by that data
It is possible to encode the problem as a (binary) MIP and use e.g
SCIP to solve it
Moreover, much is known about the facets of relevant polytope: for example, every connected matroid defines a facet of this polytope
The large number of such facets motivate a cutting plane approach which has been implemented in the SCIPbased system GOBNILP
However, in general, a MIP approach to BNSL requires very many MIP variables which motivates adding a pricer
Implementing a correct pricer is not too hard
However, integrating pricing, cutting (and branching) to solve the BNSL problem reasonably quickly raises a number of tricky problems.

12:15 
Daniel Rehfeldt, Zuse Institute Berlin
Building combinatorial optimization solvers with SCIP: Steiner tree, QUBO, and MaxCut
This talk discusses how to build stateoftheart combinatorial optimization solvers based on SCIP
First, we introduce the solver SCIPJack, which can handle Steiner tree and 14 related network optimization problems
Second, we introduce the QUBO and MaxCut solver QBOWL
For SCIPJack as well as QBOWL, we also provide computational comparisons, both with generic (commercial) optimization solvers and specialized solvers.
Edward Lam, Monash University
What I Learned in ML4CO
Researchers are starting to explore datadriven subroutines based on machine learning or reinforcement learning within mixedinteger programming solvers
We present a small case study on learning to branch using reinforcement learning on the combinatorial structures of a highlevel problem description instead of on the variables and constraints of a mixedinteger program
The learned branching rule participated in the ML4CO competition at NeurIPS 2021, ranking third among 23 entries
Experiments on the ML4CO instances show that it performs significantly better than the default branching rule of the stateoftheart solver SCIP in terms of optimality gap and dual integral.

12:45  Lunch 
13:45 
Domenico Salvagnin, Università di Padova
A fixpropagaterepair heuristic for Mixed Integer Programming
We describe a diving heuristic framework based on constraint propagation for mixed integer linear programs.
The proposed approach is an extension of the common fixandpropagate scheme, with the addition of solution repairing after each step.
The repair logic is loosely based on the WalkSAT strategy for boolean satisfiability.
Different strategies for variable ranking and value selection, as well as other options, yield different diving heuristics.
The overall method is relatively cheap, as it is basically LPfree: the full linear programming relaxation is solved only at the beginning, and only for the ranking strategies that make use of it, while additional (typically much smaller) LPs are only used to compute values for the continuous variables (if any), once at the bottom of a dive.
While individual strategies are not very robust in finding feasible solutions on a heterogenous testbed, a portfolio approach proved quite effective, consistently finding feasible solutions in 14 out of 19 instances from the public testbed of the MIP 2022 competition.

14:45 
Jasper van Doornmalen, TU Eindhoven
Symmetry handling in binary programs through propagation
Symmetries of binary programs are known to dramatically slow down branchandbound procedures
A classical approach is to add symmetry handling constraints (e.g
symresacks) that cut off solutions that are not lexicographically larger or equal to their permuted solutions
In particular, one can add symmetry handling constraints such that solutions are lexicographically maximal in their symmetry class.
In this talk, we extend the work on polyhedral symmetry handling techniques: We ensure that we find lexicographically maximal solutions for permutations and groups acting on binary variables We present three improvements: (i.) We provide an asymptotically faster algorithm for sets of symresackconstraints; (ii.) For cyclic symmetry (sub)groups, we provide an algorithm that finds all possible fixings; and (iii.) we show that a polynomial running time can be attained, even if the group order is exponentially large. We have implemented our methods as a SCIP plugin, and provide computational results for MIPLIB instances, and for class problems with mainly cyclic symmetries.
Antonia Chmiela, Zuse Institute Berlin
Monoidal Strengthening for Intersection Cuts Using Maximal QuadraticFree Sets
Over the last decades, the performance of stateoftheart MIP solvers has significantly improved.
However, nonconvex quadratic MIPs still constitute a big challenge for modern solvers.
The generation of strong cutting planes plays a crucial role in efficiently solving MIPs.
Many of the most successful cuts in practice, such as MIR and GMI, are intersection cuts.
This methodology was recently applied to generate cuts for general QCQPs using maximal quadraticfree sets.
Even though experimental results show that these intersection cuts are promising, they do not leverage the structure imposed by the integer constraints.
In this talk, we discuss how to apply monoidal strengthening to derive stronger intersection cuts for quadratic problems with integer variables.
We show how to construct a nontrivial monoid and give a geometric interpretation of the strengthening problem which reveals a procedure to solve it efficiently.
Preliminary experiments show that the strengthened cutting planes consistently outperform the pure intersection cuts.

15:05 
Christoph Graczyk, Zuse Institute Berlin
OrthogonalityBased Cut Selection
Cutting planes are an important element in reducing the solving time of mixedinteger programs (MIPs)
Because of the many available generators for these cutting planes, we need good selection policies to avoid increasingly bloating the original problem throughout the solving process while minimizing the impact of discarding cuts
In this talk I present new cut selection methods that employ a dynamic orthogonality criterion to greedily select cuts with a guaranteed minimum increase of the efficacy for any pair of cutting planes in the set
We present detailed computational results for an implementation in SCIP 8 on the MIPLIB2017 benchmark testset.
Tanuj Karia, Imperial College London
Revisiting quadratic reformulation for the global optimization of Mixed Integer Rational Programs
Recently, we revisited the quadratic reformulation approach to solve MixedInteger Polynomial Programs (MIPOPs) to global optimality by developing and implementing an algorithm to generate MixedInteger Quadratically Constrained Programs (MIQCPs) from MIPOPs
We solved the original MIPOPs and the equivalent MIQCPs for a collection of 137 MIPOPs with several global optimization software packages, finding that the reformulation often leads to better performance
Specifically, it was found that by using SCIP (1), the shifted geometric wall time mean (SGWM) was 45% lower for solving reformulated MIQCPs compared to solving the original MIPOPs (2)
In this work, we extend the study by considering the global optimization of MixedInteger Rational Programs (MIROPs), reformulating them as MIQCPs (3)
We discuss the development of a formal and systematic methodology to implement quadratic reformulation alongside preprocessing strategies such as local search (4) and bounds tightening (5) in an extension of the recently developed CANON reformulation engine (2)
We conduct extensive comparative tests on a collection of 77 MIROPs from the standard test library MINLPLib (6)
It is found that using SCIP, reformulated MIQCPs can be solved with lower SGWM compared to solving the original MIROPs
Overall, these results provide strong evidence of the effectiveness of the quadratic reformulation approach for global optimization of MIPOPs and MIROPs and support its integration into the SCIP framework.

15:25 
Markó Horváth, Institute for Computer Science and Control (SZTAKI), Hungary
A twoechelon vehicle routing problem
In this talk we investigate a twoechelon vehicle routing problem where pickups and deliveries are planned simultaneously.
Pickup offerings of semifinished goods and delivery requests for finished goods may arrive throughout the planning horizon, each of them given by a location, a timewindow, a product type and quantity.
A fleet of distinct vehicles divided into multiple depots is used to transport semifinished goods to processing facilities, and then for transporting finished goods to customers.
Processing is not instantaneous, but each semifinished good has a lead time.
The goal is to simultaneously plan pickup and delivery routes such that all the problem constraints are respected and distinct operational and penalty costs are minimized.
We propose an exact branchandprice approach to solve the problem.
The solution approach is implemented in C++ using the SCIP Optimization Suite.
JohannTobias Schäg, TU Ilmenau
On the shoulders of giants  How SCIP infrastructure helps build a new open source MILP solver
Members of ZIB write publications, maintain and release open source software.
However their work goes beyond that.
The instances on miplib.zib.de and their presentation helped find usability and correctness problems with a new open source ILP solver called Exact.
Examples of this motivate having Papilo replace CoinUtils.
Contributions to Papilo to support the pseudo boolean optimization format are underway.
This opens up new and exiting opportunities such as improvements to presolving and inprocessing in Exact or turning Exact into an full fledged MILP solver. A brief genealogy of the ideas in Exact is given and pseudoboolean reasoning motivated on a toy problem MILP where branchandcut based solver show pathological performance. 
15:45  Coffeebreak 
16:15 
Thorsten Koch, Zuse Institute and TU Berlin
Progress in Mathematical Programming Solvers from 2001 to 2020 back to 1990
We report on a study that investigates the progress made in LP and MILP solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today
On average, we found out that for solving LP/MILP, the total speedup was about 180 and 1,000 times, respectively
However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time
We will report on how we measure performance and why it is very difficult to come up with one reasonable number
Furthermore, we excavate some data and recollections from the 1990s and put them into perspective
This will include notes on the early work on MILP at ZIB.
Mathieu Besancon, Zuse Institute Berlin
Convex mixedinteger optimization with FrankWolfe methods
Mixedinteger nonlinear optimization is a broad class of problems that feature combinatorial structures and nonlinearities
Typical exact methods combine a branchandbound scheme with relaxation and separation subroutines
We investigate the properties and advantages of erroradaptive firstorder methods based on the FrankWolfe algorithm for such problems, requiring only a gradient oracle for the objective function and linear optimization over the feasible set.
In particular, we will study the algorithmic consequences of optimizing the subproblem over the convex hull of the mixedinteger feasible set compared to solving the subproblems over continuous relaxation of the mixedinteger feasible set Given that the former approach requires a mixedinteger linear solver as an oracle at every iteration, we leverage generic and branchandbound specific structure reuse techniques to reduce the periteration computational burden. 
16:45 
Leon Eifler, Zuse Institute Berlin
Safe Verified Gomory Mixed Integer Cuts for Exact Rational MIP
We aim to solve mixed integer programs with rational input data exactly over the rational numbers, i.e., without any roundoff errors or error tolerances.
In this, a possible bottleneck that should be avoided whenever possible is to employ largescale symbolic computations.
In its place, it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds.
In this talk, we continue to leverage that paradigm by adding separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Sanjeeb, and Fukasawa in 2009.
Constraints are aggregated safely using approximate dual multipliers from an LP solve, and then the MIR procedure is applied to generate provably valid, although slightly weaker inequalities.
We generalize that approach to problem data that is not representable in floatingpoint arithmetic, add routines for controlling the encoding length, and show how the resulting cutting planes can be verified according to the VIPR certificate standard.
Liding Xu, Ecole Polytechnique, France
On a concept of a generic intersection cut callback
Intersection cut framework can generate valid linear inequalities for a nonconvex set $S$
The framework requires a corner polyhedron relaxation of $S$, and a convex $S$free set, which does not contain any point of $S$ in its interior
In this talk, I will review the recent development of intersection cuts in MINLPs (e.g
quadratic/polynomial programming and signomial programming), featuring the construction of a variety of $S$free sets
On the other hand, implementation of intersection cut requires much knowledge of a solver's data structure and numerical stability
Software engineering can help here, as the solver can encapsulate cut separation procedures and provides an intersection cut callback without need for symbolic representation of $S$
Then, the users only need to provide definingvariables, zero and firstorder oracle access to the $S$free set
I will also discuss some limitations of intersection cuts and open problems.

17:15 
Matthias Walter, University of Twente
Simple odd βcycle inequalities for binary polynomial optimization
The multilinear polytope arises naturally in binary polynomial optimization
Del Pia and Di Gregorio introduced the class of odd βcycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances
Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph
In the talk I will introduce a weaker version, called simple odd βcycle inequalities, and illustrate a strongly polynomialtime separation algorithm for arbitrary instances
These inequalities still have Chvátal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs
The talk is rounded up with computational results for the implementation in SCIP
Joint work with Alberto Del Pia.
Ksenia Bestuzheva, Zuse Institute Berlin
Strengthening dual bounds in branchandbound by SONC certificates
Nonnegativity certificates obtained by decomposing a polynomial as a sum of nonnegative circuit polynomials (SONC) can be used to compute tight bounds for polynomial optimization problems
We present a SONCbased relaxation method which we incorporate into SCIP's branchandbound algorithm
We discuss our implementation of SONC relaxations for constrained polynomial problems and describe a method that utilizes variable bounds for strengthening SONC relaxations.

17:45 
Closing 
18:00  Birthday Celebration at Gastraum Esskultur on campus, Takustr. 38/40, 14195 BerlinDahlem. 