@phdthesis{Eifler2024, author = {Eifler, Leon}, title = {Algorithms and Certificates for Exact Mixed Integer Programming}, doi = {https://doi.org/10.14279/depositonce-23941}, year = {2024}, abstract = {Mixed Integer Programming (MIP) is a powerful tool for solving optimization problems with discrete decisions. Although the problem class of mixed integer programs is NP-hard, MIP solvers have made significant progress in solving large-scale instances through decades of dedicated research and complex algorithmic improvements. In practice, virtually all algorithms to solve MIP problems are based on floating-point arithmetic due to its rapid computation times and robust numerical capabilities. Using error tolerances, MIP solvers avoid numerical issues and maintain a solution quality that is sufficient for most practical applications. There are, however, applications where exact solutions are required, such as when MIPs are employed as a tool in computer-assisted proofs. In such cases, exact, certified MIP solvers are a necessity. This thesis delves into the study and development of exact, certified mixed integer programming methods. The primary contribution of this thesis is an algorithmic framework for exact rational mixed integer programming. This framework incorporates safe dual bounding techniques, exact rational presolving, an exact repair step for heuristic solutions, and a novel exact Gomory mixed integer cut generator. We validate the effectiveness of our framework through experiments on a diverse set of benchmark instances. We take great care to measure the similarities and differences with corresponding techniques in the floating-point setting. Furthermore, we incorporate certification techniques into the framework to provide rigorous guarantees on the correctness of the computed solutions. We also provide a comprehensive algorithmic and computational study of the solver-independent verification of these certficates. We also present a framework for applying exact MIP as a tool for computer-assisted mathematics, using Chv{\´a}tals conjecture as an illustrative example. Another significant contribution of this thesis is a new algorithm for solving linear programs exactly. This algorithm combines two state-of-the-art techniques for exact linear programming: precision boosting and LP iterative refinement. Combining these techniques can significantly improve the performance of exact linear programming solvers, and we prove that the algorithm is theoretically guaranteed to terminate with an exact solution.}, language = {en} } @article{EiflerNicolasThouveninGleixner2024, author = {Eifler, Leon and Nicolas-Thouvenin, Jules and Gleixner, Ambros}, title = {Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization}, journal = {INFORMS Journal on Computing}, doi = {10.1287/ijoc.2023.0409}, year = {2024}, abstract = {This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: the speed of LP iterative refinement, in particular in the majority of cases when a double-precision floating-point solver is able to compute approximate solutions with small errors, and the robustness of precision boosting whenever extended levels of precision become necessary. We compare the practical performance of the resulting algorithm with both puremethods on a large set of LPs and mixed-integer programs (MIPs). The results show that the combined algorithm solves more instances than a pure LP iterative refinement approach, while being faster than pure precision boosting. When embedded in an exact branch-and-cut framework for MIPs, the combined algorithm is able to reduce the number of failed calls to the exact LP solver to zero, while maintaining the speed of the pure LP iterative refinement approach.}, language = {en} } @inproceedings{EiflerWitzigGleixner2024, author = {Eifler, Leon and Witzig, Jakob and Gleixner, Ambros}, title = {Branch and cut for partitioning a graph into a cycle of clusters}, volume = {14594}, booktitle = {Combinatorial Optimization. ISCO 2024}, doi = {10.1007/978-3-031-60924-4_8}, pages = {97 -- 108}, year = {2024}, abstract = {In this paper we study formulations and algorithms for the cycle clustering problem, a partitioning problem over the vertex set of a directed graph with nonnegative arc weights that is used to identify cyclic behavior in simulation data generated from nonreversible Markov state models. Here, in addition to partitioning the vertices into a set of coherent clusters, the resulting clusters must be ordered into a cycle such as to maximize the total net flow in the forward direction of the cycle. We provide a problem-specific binary programming formulation and compare it to a formulation based on the reformulation-linearization technique (RLT). We present theoretical results on the polytope associated with our custom formulation and develop primal heuristics and separation routines for both formulations. In computational experiments on simulation data from biology we find that branch and cut based on the problem-specific formulation outperforms the one based on RLT.}, language = {en} } @article{EiflerGleixner2024, author = {Eifler, Leon and Gleixner, Ambros}, title = {Safe and verified Gomory mixed integer cuts in a rational MIP framework}, volume = {34}, journal = {SIAM Journal on Optimization}, number = {1}, doi = {10.1137/23M156046X}, year = {2024}, abstract = {This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009 [INFORMS J. Comput., 21 (2009), pp. 641-649]. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5\% more instances to exact optimality and reduce solving times by 26.8\% on the MIPLIB 2017 benchmark test set.}, language = {en} } @misc{BolusaniBesanconBestuzhevaetal.2024, author = {Bolusani, Suresh and Besan{\c{c}}on, Mathieu and Bestuzheva, Ksenia and Chmiela, Antonia and Dion{\´i}sio, Jo{\~a}o and Donkiewicz, Tim and van Doornmalen, Jasper and Eifler, Leon and Ghannam, Mohammed and Gleixner, Ambros and Graczyk, Christoph and Halbig, Katrin and Hedtke, Ivo and Hoen, Alexander and Hojny, Christopher and van der Hulst, Rolf and Kamp, Dominik and Koch, Thorsten and Kofler, Kevin and Lentz, Jurgen and Manns, Julian and Mexi, Gioni and M{\"u}hmer, Erik and E. Pfetsch, Marc and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Turner, Mark and Vigerske, Stefan and Weninger, Dieter and Xu, Liding}, title = {The SCIP Optimization Suite 9.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-95528}, year = {2024}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver.}, language = {en} }