Meet the expert event at Ghent University: Symmetry Handling in Mathematical Programming Solving - Jasper van Doornmalen

When? 24/02/2025, 11h30 - 14h00

Where? Faculty of Economics and Business Administration, Ghent University. Auditorium 2.2, campus Hoveniersberg, Tweekerkenstraat 2, 9000 Ghent, Belgium.

What? The faculty of Economics and Business Administration at Ghent University organizes a meet the expert event on “Symmetry Handling in Mathematical Programming Solving”. The event consists of a presentation by dr. Jasper van Doornmalen (see abstract below) and concludes with a sandwich lunch. While this event is tailored to PhD students, we encourage all researchers that work with mathematical programming solvers to participate. The event is free of charge, but registration is necessary before 19/02 (https://forms.gle/NMuWdkyVQidJRQJx6). This event is sponsored by the doctoral schools of Ghent University.

Hope to welcome you soon!

David Van Bulck, Dries Goossens

Abstract.

Many optimization problems are solved in an effective and fast way with modern general-purpose mathematical programming solvers such as Gurobi, CPLEX, SCIP, BARON and OR-Tools. These solvers are complex pieces of machinery, consisting of many carefully designed components to improve the performance. Over the years, these tools have seen massive algorithmic improvements, which allows for solving larger optimization problems that were previously deemed impractical.

One component of mathematical programming solvers is symmetry handling. In a standard branch-and-bound context where symmetries are not exploited, it is possible that many symmetrically equivalent problems are solved in each sub-problem. This means that if many symmetries are present, the effect of branching is diminished. Therefore, to solve highly symmetric problems effectively, it is crucial to handle symmetries. This presentation outlines the problem with symmetries in mathematical programs via a simple application, and show how these can be handled in a straightforward way.

 The presentation consists of three parts:

Part 1 is an introduction to techniques and tools for solving mathematical programs.

* First, what are symmetries in mathematical programming (in particular, in mixed-integer linear programming), how can they be recognized, how do they slow down solving problems, and how they can be handled. Various examples are revisited.

* Second, propagation techniques for tightening the feasible region in branch-and-bound subproblems are introduced. It is discussed what propagation techniques are, and how they can be implemented in the open-source mathematical programming solver SCIP.

* Third, it is briefly discussed how a simple propagation-based symmetry handling constraint can be handled.

* Then, various well-known and practical symmetry handling methods are discussed, in particular those that found its way in commonly-used mixed-integer programming solvers.

Part 2 focuses on the results of the paper "A Unified Framework for Symmetry Handling” (van Doornmalen, J., Hojny, C. A unified framework for symmetry handling. Math. Program. (2024). https://doi.org/10.1007/s10107-024-02102-2). The concept of symmetries in mathematical programs is formalized, and it is shown how this can be handled via a generalized symmetry handling constraint. The paper shows that many of these existing methods can be generalized from the binary setting to arbitrary variable domains, and shows when symmetry handling methods can be applied at the same time. It is discussed how this is implemented in the open-source mathematical programming solver SCIP, leading to beneficial results when comparing to the former implementation.

Part 3 offers the possibility to ask questions either right after the presentation, or during the sandwich lunch.