@article{EiflerGleixner2021, author = {Eifler, Leon and Gleixner, Ambros}, title = {A Computational Status Update for Exact Rational Mixed Integer Programming}, journal = {Integer Programming and Combinatorial Optimization: 22th International Conference, IPCO 2021}, doi = {10.1007/978-3-030-73879-2_12}, year = {2021}, 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 6.6x over the original framework and 2.8 times as many instances solved within a time limit of two hours.}, language = {en} } @misc{EiflerGleixner2021, author = {Eifler, Leon and Gleixner, Ambros}, title = {A Computational Status Update for Exact Rational Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81298}, year = {2021}, 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 6.6x over the original framework and 2.8 times as many instances solved within a time limit of two hours.}, language = {en} } @misc{GamrathAndersonBestuzhevaetal.2020, 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}, year = {2020}, 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} } @article{GamrathGleixnerKochetal.2019, author = {Gamrath, Gerald and Gleixner, Ambros and Koch, Thorsten and Miltenberger, Matthias and Kniasew, Dimitri and Schl{\"o}gel, Dominik and Martin, Alexander and Weninger, Dieter}, title = {Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming}, volume = {37}, journal = {Journal of Computational Mathematics}, doi = {10.4208/jcm.1905-m2019-0055}, pages = {866 -- 888}, year = {2019}, abstract = {The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP.}, language = {en} } @inproceedings{BertholdGleixner2013, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover Branching}, volume = {7933}, booktitle = {Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013, Proceedings}, editor = {Bonifaci, Vincenzo and Demetrescu, Camil and Marchetti-Spaccamela, Alberto}, doi = {10.1007/978-3-642-38527-8_20}, pages = {212 -- 223}, year = {2013}, abstract = {In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred. Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule. We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved.}, language = {en} } @inproceedings{GleixnerWeltge2013, author = {Gleixner, Ambros and Weltge, Stefan}, title = {Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming}, volume = {7874}, booktitle = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013}, doi = {10.1007/978-3-642-38171-3_26}, pages = {355 -- 361}, year = {2013}, abstract = {Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints. These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times.}, language = {en} } @inproceedings{GleixnerSteffyWolter2012, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Improving the Accuracy of Linear Programming Solvers with Iterative Refinement}, booktitle = {ISSAC '12. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation}, doi = {10.1145/2442829.2442858}, pages = {187 -- 194}, year = {2012}, language = {en} } @inproceedings{SofranacGleixnerPokutta2021, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-Independent Measure of Progress for Linear Constraint Propagation}, volume = {210}, booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, doi = {10.4230/LIPIcs.CP.2021.52}, pages = {52:1 -- 52:17}, year = {2021}, abstract = {Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure -- independently of the algorithmic design -- the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance: (i) We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances. (ii) We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported.}, language = {en} } @misc{EiflerGleixnerPulaj2018, author = {Eifler, Leon and Gleixner, Ambros and Pulaj, Jonad}, title = {Chv{\´a}tal's Conjecture Holds for Ground Sets of Seven Elements}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70240}, year = {2018}, abstract = {We establish a general computational framework for Chv{\´a}tal's conjecture based on exact rational integer programming. As a result we prove Chv{\´a}tal's conjecture holds for all downsets whose union of sets contains seven elements or less. The computational proof relies on an exact branch-and-bound certificate that allows for elementary verification and is independent of the integer programming solver used.}, language = {en} } @article{RehfeldtHobbieSchoenheitetal.2022, author = {Rehfeldt, Daniel and Hobbie, Hannes and Sch{\"o}nheit, David and Koch, Thorsten and M{\"o}st, Dominik and Gleixner, Ambros}, title = {A massively parallel interior-point solver for LPs with generalized arrowhead structure, and applications to energy system models}, volume = {296}, journal = {European Journal of Operational Research}, number = {1}, doi = {10.1016/j.ejor.2021.06.063}, pages = {60 -- 71}, year = {2022}, abstract = {Linear energy system models are a crucial component of energy system design and operations, as well as energy policy consulting. If detailed enough, such models lead to large-scale linear programs, which can be intractable even for the best state-of-the-art solvers. This article introduces an interior-point solver that exploits common structures of energy system models to efficiently run in parallel on distributed-memory systems. The solver is designed for linear programs with doubly-bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. In order to handle the large number of linking constraints and variables commonly observed in energy system models, a distributed Schur complement preconditioner is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the solver PIPS-IPM. We evaluate the computational performance on energy system models with up to four billion nonzero entries in the constraint matrix—and up to one billion columns and one billion rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market-clearing. It has been widely applied in the literature on energy system analyses in recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models.}, language = {en} } @article{GleixnerSteffy2020, author = {Gleixner, Ambros and Steffy, Daniel}, title = {Linear Programming using Limited-Precision Oracles}, volume = {183}, journal = {Mathematical Programming}, number = {1-2}, doi = {10.1007/s10107-019-01444-6}, pages = {525 -- 554}, year = {2020}, abstract = {Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithmetic. In this paper we introduce the idea of a limited-precision LP oracle and study how such an oracle could be used within a larger framework to compute exact precision solutions to LPs. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. This work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.}, language = {en} }