Let's SCIP it! A workshop to celebrate 20 years of Solving Constraint Integer Programs

Programme

The scientific programme is scheduled for 9:30am-6: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 Two-stage Stochastic Programming”

Domenico Salvagnin, Università di Padova:
“A fix-propagate-repair 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:

Tobias Achterberg, Gurobi Optimization
Marc Pfetsch, TU Darmstadt
Thorsten Koch, Zuse Institute and TU Berlin
Mathieu Besancon, Zuse Institute Berlin
Ksenia Bestuzheva, Zuse Institute Berlin
Antonia Chmiela, Zuse Institute Berlin
James Cussens, University of Bristol
Jasper van Doornmalen, TU Eindhoven
Christoph Graczyk, Zuse Institute Berlin
Leon Eifler, Zuse Institute Berlin
Christopher Hojny, TU Eindhoven
Markó Horváth, Institute for Computer Science and Control (SZTAKI), Hungary
Tanuj Karia, Imperial College London
Edward Lam, Monash University
Daniel Rehfeldt, Zuse Institute Berlin
Johann-Tobias Schäg, TU Ilmenau
Matthias Walter, University of Twente
Liding Xu, Ecole Polytechnique, France

For details, titles, and abstracts, please see the schedule below.

The day will be concluded by a birthday celebration at Gastraum Esskultur starting at 6:00pm.

Contact

Registration closed on October 6th.

The workshop will be free of charge. For any questions contact us at scip20workshop@zib.de.

Rules for the event

Make sure to be tested negative for covid-19 the morning of the workshop. There will also be some self-test kits available in front of the building of Zuse Institute.
Wear a mask when possible and follow the general hygiene rules.

Venue

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 non-parallel sessions will be in KL 29/235.

Zoom stream lecture hall: https://zib-de.zoom.us/j/86016095453
Zoom stream seminar room: https://zib-de.zoom.us/j/88981821881

Please see your personal e-mail where you can attend physically.

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).

Organizers

Ambros Gleixner, Zuse Institute and HTW Berlin
Marc Pfetsch, TU Darmstadt
Sebastian Pokutta, Zuse Institute and TU Berlin
Franziska Schlösser, Zuse Institute Berlin

Schedule

To see the abstract of a talk, please click on its title.

Zoom stream lecture hall: https://zib-de.zoom.us/j/86016095453
Zoom stream seminar room: https://zib-de.zoom.us/j/88981821881

Time	Lecture hall Seminar room
09:00	Registration
09:30	Opening
09:45	Tobias Achterberg, Gurobi Optimization SCIP Origins slides. 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 slides. TBA
10:30	Coffeebreak
10:45	Merve Bodur, University of Toronto Methodological Advances in Two-stage Stochastic Programming slides. Stochastic programming is a useful framework for dealing with uncertainty and integrality requirements in optimization problems. In this talk, we focus on two-stage stochastic integer programs (2SIPs), in particular their sample average approximations which yield computationally challenging mixed-integer programming (MIP) models. For various classes of 2SIPs, we review commonly used decomposition approaches (most notably logic-based 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 second-stage problems, (ii) machine learning to learn the recourse value functions as well as cut selection/generation, and (iii) MIP-based 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 slides. Symmetries are well-known to deteriorate the performance of branch-and-bound 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 Branch-price-and-cut for Bayesian network structure learning slides. Bayesian network structure learning (BNSL) is an NP-hard 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 SCIP-based 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 slides. This talk discusses how to build state-of-the-art combinatorial optimization solvers based on SCIP First, we introduce the solver SCIP-Jack, which can handle Steiner tree and 14 related network optimization problems Second, we introduce the QUBO and MaxCut solver QBOWL For SCIP-Jack 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 data-driven subroutines based on machine learning or reinforcement learning within mixed-integer programming solvers We present a small case study on learning to branch using reinforcement learning on the combinatorial structures of a high-level problem description instead of on the variables and constraints of a mixed-integer 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 state-of-the-art solver SCIP in terms of optimality gap and dual integral.
12:45	Lunch
13:45	Domenico Salvagnin, Università di Padova A fix-propagate-repair heuristic for Mixed Integer Programming slides. We describe a diving heuristic framework based on constraint propagation for mixed integer linear programs. The proposed approach is an extension of the common fix-and-propagate 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 LP-free: 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 branch-and-bound 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 symresack-constraints; (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 Quadratic-Free Sets Over the last decades, the performance of state-of-the-art MIP solvers has significantly improved. However, non-convex 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 quadratic-free 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 non-trivial 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 Orthogonality-Based Cut Selection Cutting planes are an important element in reducing the solving time of mixed-integer 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 Mixed-Integer Polynomial Programs (MIPOPs) to global optimality by developing and implementing an algorithm to generate Mixed-Integer 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 Mixed-Integer Rational Programs (MIROPs), reformulating them as MIQCPs (3) We discuss the development of a formal and systematic methodology to implement quadratic reformulation alongside pre-processing 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 two-echelon vehicle routing problem In this talk we investigate a two-echelon vehicle routing problem where pickups and deliveries are planned simultaneously. Pickup offerings of semi-finished goods and delivery requests for finished goods may arrive throughout the planning horizon, each of them given by a location, a time-window, a product type and quantity. A fleet of distinct vehicles divided into multiple depots is used to transport semi-finished goods to processing facilities, and then for transporting finished goods to customers. Processing is not instantaneous, but each semi-finished 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 branch-and-price approach to solve the problem. The solution approach is implemented in C++ using the SCIP Optimization Suite. Johann-Tobias 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 pre-solving and in-processing in Exact or turning Exact into an full fledged MILP solver. A brief genealogy of the ideas in Exact is given and pseudo-boolean reasoning motivated on a toy problem MILP where branch-and-cut 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 slides. 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 speed-up 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 mixed-integer optimization with Frank-Wolfe methods Mixed-integer nonlinear optimization is a broad class of problems that feature combinatorial structures and nonlinearities Typical exact methods combine a branch-and-bound scheme with relaxation and separation subroutines We investigate the properties and advantages of error-adaptive first-order methods based on the Frank-Wolfe 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 mixed-integer feasible set compared to solving the subproblems over continuous relaxation of the mixed-integer feasible set Given that the former approach requires a mixed-integer linear solver as an oracle at every iteration, we leverage generic and branch-and-bound specific structure reuse techniques to reduce the per-iteration computational burden.
16:45	Leon Eifler, Zuse Institute Berlin Safe Verified Gomory Mixed Integer Cuts for Exact Rational MIP slides. 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 large-scale 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 floating-point 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 slides. 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 defining-variables, zero- and first-order 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 slides. 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 polynomial-time 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 branch-and-bound by SONC certificates slides. 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 SONC-based relaxation method which we incorporate into SCIP's branch-and-bound 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 Berlin-Dahlem.

Supported by