@misc{GamrathAndersonBestuzhevaetal., author = {Gamrath, Gerald and Anderson, Daniel and Bestuzheva, Ksenia and Chen, Wei-Kun and Eifler, Leon and Gasse, Maxime and Gemander, Patrick and Gleixner, Ambros and Gottwald, Leona and Halbig, Katrin and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and Le Bodic, Pierre and Maher, Stephen J. and Matter, Frederic and Miltenberger, Matthias and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Tawfik, Christine and Vigerske, Stefan and Wegscheider, Fabian and Weninger, Dieter and Witzig, Jakob}, title = {The SCIP Optimization Suite 7.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78023}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders' decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders' decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.}, language = {en} } @misc{GleixnerEiflerGallyetal., author = {Gleixner, Ambros and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gemander, Patrick and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Vigerske, Stefan and Weninger, Dieter and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 5.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66297}, abstract = {This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 \% faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 \% faster overall and 23 \% faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.}, language = {en} } @misc{GleixnerBastubbeEifleretal., author = {Gleixner, Ambros and Bastubbe, Michael and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Schubert, Christoph and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Walter, Matthias and Wegscheider, Fabian and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 6.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69361}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders' decomposition in a generic framework. GCG's detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders' framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.}, language = {en} } @article{GleixnerGottwaldHoen, author = {Gleixner, Ambros and Gottwald, Leona and Hoen, Alexander}, title = {PaPILO: A Parallel Presolving Library for Integer and Linear Programming with Multiprecision Support}, series = {INFORMS Journal on Computing}, volume = {35}, journal = {INFORMS Journal on Computing}, number = {6}, doi = {10.1287/ijoc.2022.0171}, pages = {1329 -- 1341}, abstract = {Presolving has become an essential component of modern mixed integer program (MIP) solvers, both in terms of computational performance and numerical robustness. In this paper, we present PaPILO, a new C++ header-only library that provides a large set of presolving routines for MIP and linear programming problems from the literature. The creation of PaPILO was motivated by the current lack of (a) solver-independent implementations that (b) exploit parallel hardware and (c) support multiprecision arithmetic. Traditionally, presolving is designed to be fast. Whenever necessary, its low computational overhead is usually achieved by strict working limits. PaPILO's parallelization framework aims at reducing the computational overhead also when presolving is executed more aggressively or is applied to large-scale problems. To rule out conflicts between parallel presolve reductions, PaPILO uses a transaction-based design. This helps to avoid both the memory-intensive allocation of multiple copies of the problem and special synchronization between presolvers. Additionally, the use of Intel's Threading Building Blocks library aids PaPILO in efficiently exploiting recursive parallelism within expensive presolving routines, such as probing, dominated columns, or constraint sparsification. We provide an overview of PaPILO's capabilities and insights into important design choices.}, language = {en} } @misc{D'AndreagiovanniGleixner, author = {D'Andreagiovanni, Fabio and Gleixner, Ambros}, title = {Towards an accurate solution of wireless network design problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59010}, abstract = {The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models.}, language = {en} } @inproceedings{MexiBesanconBolusanietal., author = {Mexi, Gioni and Besan{\c{c}}on, Mathieu and Bolusani, Suresh and Chmiela, Antonia and Hoen, Alexander and Gleixner, Ambros}, title = {Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization}, series = {Proceedings of Conference of the Society for Operations Research in Germany}, booktitle = {Proceedings of Conference of the Society for Operations Research in Germany}, language = {en} } @article{BestuzhevaBesanconChenetal., author = {Bestuzheva, Ksenia and Besan{\c{c}}on, Mathieu and Chen, Wei-Kun and Chmiela, Antonia and Donkiewicz, Tim and Doornmalen, Jasper and Eifler, Leon and Gaul, Oliver and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Leona and Graczyk, Christoph and Halbig, Katrin and Hoen, Alexander and Hojny, Christopher and Hulst, Rolf and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Matter, Frederic and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc and Rehfeldt, Daniel and Schlein, Steffan and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Sofranac, Boro and Turner, Mark and Vigerske, Stefan and Wegscheider, Fabian and Wellner, Philipp and Weninger, Dieter and Witzig, Jakob}, title = {Enabling research through the SCIP optimization suite 8.0}, series = {ACM Transactions on Mathematical Software}, volume = {49}, journal = {ACM Transactions on Mathematical Software}, number = {2}, doi = {10.1145/3585516}, pages = {1 -- 21}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP's main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP's application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP.}, language = {en} } @article{EiflerGleixner, author = {Eifler, Leon and Gleixner, Ambros}, title = {A computational status update for exact rational mixed integer programming}, series = {Mathematical Programming}, volume = {197}, journal = {Mathematical Programming}, doi = {10.1007/s10107-021-01749-5}, pages = {793 -- 812}, abstract = {The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours.}, language = {en} } @inproceedings{GasseBowlyCappartetal., author = {Gasse, Maxime and Bowly, Simon and Cappart, Quentin and Charfreitag, Jonas and Charlin, Laurent and Ch{\´e}telat, Didier and Chmiela, Antonia and Dumouchelle, Justin and Gleixner, Ambros and Kazachkov, Aleksandr M. and Khalil, Elias and Lichocki, Pawel and Lodi, Andrea and Lubin, Miles and Maddison, Chris J. and Christopher, Morris and Papageorgiou, Dimitri J. and Parjadis, Augustin and Pokutta, Sebastian and Prouvost, Antoine and Scavuzzo, Lara and Zarpellon, Giulia and Yang, Linxin and Lai, Sha and Wang, Akang and Luo, Xiaodong and Zhou, Xiang and Huang, Haohan and Shao, Shengcheng and Zhu, Yuanming and Zhang, Dong and Quan, Tao and Cao, Zixuan and Xu, Yang and Huang, Zhewei and Zhou, Shuchang and Binbin, Chen and Minggui, He and Hao, Hao and Zhiyu, Zhang and Zhiwu, An and Kun, Mao}, title = {The Machine Learning for Combinatorial Optimization Competition (ML4CO): results and insights}, series = {Proceedings of Conference on Neural Information Processing Systems}, booktitle = {Proceedings of Conference on Neural Information Processing Systems}, language = {en} } @misc{BolusaniBesanconBestuzhevaetal., 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}, 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} } @inproceedings{GhannamGleixner, author = {Ghannam, Mohammed and Gleixner, Ambros}, title = {Hybrid genetic search for dynamic vehicle routing with time windows}, series = {Proceedings of Conference of the Society for Operations Research in Germany}, booktitle = {Proceedings of Conference of the Society for Operations Research in Germany}, language = {en} } @article{EiflerGleixner, author = {Eifler, Leon and Gleixner, Ambros}, title = {Safe and verified Gomory mixed integer cuts in a rational MIP framework}, series = {SIAM Journal on Optimization}, volume = {34}, journal = {SIAM Journal on Optimization}, number = {1}, doi = {10.1137/23M156046X}, 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} } @inproceedings{HoenOertelGleixneretal., author = {Hoen, Alexander and Oertel, Andy and Gleixner, Ambros and Nordstr{\"o}m, Jakob}, title = {Certifying MIP-based presolve reductions for 0-1 integer linear programs}, series = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024}, volume = {14742}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024}, doi = {10.1007/978-3-031-60597-0_20}, abstract = {It is well known that reformulating the original problem can be crucial for the performance of mixed-integer programming (MIP) solvers. To ensure correctness, all transformations must preserve the feasibility status and optimal value of the problem, but there is currently no established methodology to express and verify the equivalence of two mixed-integer programs. In this work, we take a first step in this direction by showing how the correctness of MIP presolve reductions on - integer linear programs can be certified by using (and suitably extending) the VeriPB tool for pseudo-Boolean proof logging. Our experimental evaluation on both decision and optimization instances demonstrates the computational viability of the approach and leads to suggestions for future revisions of the proof format that will help to reduce the verbosity of the certificates and to accelerate the certification and verification process further.}, language = {en} } @article{BolusaniBesanconGleixneretal., author = {Bolusani, Suresh and Besan{\c{c}}on, Mathieu and Gleixner, Ambros and Berthold, Timo and D'Ambrosio, Claudia and Mu{\~n}oz, Gonzalo and Paat, Joseph and Thomopulos, Dimitri}, title = {The MIP workshop 2023 computational competition on reoptimization}, series = {Mathematical Programming Computation}, volume = {16}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-024-00256-w}, pages = {255 -- 266}, abstract = {This paper describes the computational challenge developed for a computational competition held in 2023 for the 20th anniversary of the Mixed Integer Programming Workshop. The topic of this competition was reoptimization, also known as warm starting, of mixed integer linear optimization problems after slight changes to the input data for a common formulation. The challenge was to accelerate the proof of optimality of the modified instances by leveraging the information from the solving processes of previously solved instances, all while creating high-quality primal solutions. Specifically, we discuss the competition's format, the creation of public and hidden datasets, and the evaluation criteria. Our goal is to establish a methodology for the generation of benchmark instances and an evaluation framework, along with benchmark datasets, to foster future research on reoptimization of mixed integer linear optimization problems.}, language = {en} } @inproceedings{EiflerWitzigGleixner, author = {Eifler, Leon and Witzig, Jakob and Gleixner, Ambros}, title = {Branch and cut for partitioning a graph into a cycle of clusters}, series = {Combinatorial Optimization. ISCO 2024}, volume = {14594}, booktitle = {Combinatorial Optimization. ISCO 2024}, doi = {10.1007/978-3-031-60924-4_8}, 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} } @inproceedings{GhannamMexiLametal., author = {Ghannam, Mohammed and Mexi, Gioni and Lam, Edward and Gleixner, Ambros}, title = {Branch and price for the length-constrained cycle partition problem}, series = {Proceedings of INFORMS Optimization Society Conference}, booktitle = {Proceedings of INFORMS Optimization Society Conference}, language = {en} }