EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3804. Certifying Symmetry Handling Reductions in Integer Programming

Invited abstract in session WB-30: Specialized Optimization Algorithms, stream Software for Optimization.

Wednesday, 10:30-12:00
Room: 064 (building: 208)

Authors (first author is the speaker)

1. Jasper van Doornmalen
Department of Mathematics and Computer Science, Eindhoven University of Technology
2. Leon Eifler
Zuse-Institute Berlin (ZIB)
3. Ambros Gleixner
HTW Berlin
4. Christopher Hojny
TU Eindhoven

Abstract

Modern solvers for mathematical optimization problems are complex pieces of software. They usually make use of a combination of solution methods. Though the correctness of these methods is often proven on paper, with today's tools it seems prohibitively difficult to verify that they are implemented correctly in complex software. Even thoroughly tested state-of-the-art solvers used by many are not immune to bugs and numerical issues. We present a proof system allowing for establishing correctness of results produced by optimization algorithms. Particular focus is placed on mixed-integer programming (MIP), extending on work for binary programs by Bogaerts, Gocht, McCreesh, and Nordström (2022). Our proof sytsem covers a broad range of MIP solving techniques, including cutting planes, presolving, and symmetry handling.

Keywords

Status: accepted

Back to the list of papers