@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}, number = {2}, publisher = {Springer Nature}, issn = {0025-5610}, doi = {10.1007/s10107-021-01749-5}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:523-19019}, 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} } @article{BestuzhevaGleixnerVigerske, author = {Bestuzheva, Ksenia and Gleixner, Ambros and Vigerske, Stefan}, title = {A computational study of perspective cuts}, series = {Mathematical Programming Computation}, volume = {15}, journal = {Mathematical Programming Computation}, number = {4}, publisher = {Springer Nature}, issn = {1867-2949}, doi = {10.1007/s12532-023-00246-4}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:523-19020}, pages = {703 -- 731}, abstract = {The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time.}, subject = {Nonlinear programming}, language = {en} } @article{MuellerMunozGasseetal., author = {M{\"u}ller, Benjamin and Mu{\~n}oz, Gonzalo and Gasse, Maxime and Gleixner, Ambros and Lodi, Andrea and Serrano, Felipe}, title = {On generalized surrogate duality in mixed-integer nonlinear programming}, series = {Mathematical Programming}, volume = {192}, journal = {Mathematical Programming}, number = {1-2}, publisher = {Springer Berlin Heidelberg}, issn = {0025-5610}, doi = {10.1007/s10107-021-01691-6}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:523-16741}, pages = {89 -- 118}, abstract = {The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global ϵ-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments.}, subject = {Kombinatorische Optimierung}, 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}, number = {2}, publisher = {Springer Nature}, address = {Berlin/Heidelberg}, issn = {1867-2949}, doi = {10.1007/s12532-024-00256-w}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:523-19804}, pages = {255 -- 266}, abstract = {This paper describes the computational challenge developed for a computational competition held in 2023 for the 20thanniversary 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} }