TY - JOUR A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - A computational status update for exact rational mixed integer programming JF - Mathematical Programming N2 - 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. KW - Mixed integer programming KW - Exact computation KW - Rational arithmetic KW - Symbolic computations KW - Certificate of correctness Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:523-19019 SN - 0025-5610 SN - 1436-4646 VL - 197 IS - 2 SP - 793 EP - 812 PB - Springer Nature ER - TY - JOUR A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Vigerske, Stefan T1 - A computational study of perspective cuts JF - Mathematical Programming Computation N2 - 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. KW - Nonlinear programming KW - Perspective cuts KW - Mixed-integer nonlinear programming KW - Nonconvex optimization KW - Computational study Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:523-19020 SN - 1867-2949 SN - 1867-2957 VL - 15 IS - 4 SP - 703 EP - 731 PB - Springer Nature ER - TY - JOUR A1 - Müller, Benjamin A1 - Muñoz, Gonzalo A1 - Gasse, Maxime A1 - Gleixner, Ambros A1 - Lodi, Andrea A1 - Serrano, Felipe T1 - On generalized surrogate duality in mixed-integer nonlinear programming JF - Mathematical Programming N2 - 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. KW - Kombinatorische Optimierung KW - Surrogate relaxation KW - MINLP KW - Nonconvex optimization KW - 90-08 KW - 90C27 KW - 90C26 KW - Nichtkonvexe Optimierung KW - Nichtlineare Optimierung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:523-16741 SN - 0025-5610 SN - 1436-4646 VL - 192 IS - 1-2 SP - 89 EP - 118 PB - Springer Berlin Heidelberg ER - TY - JOUR A1 - Bolusani, Suresh A1 - Besançon, Mathieu A1 - Gleixner, Ambros A1 - Berthold, Timo A1 - D’Ambrosio, Claudia A1 - Muñoz, Gonzalo A1 - Paat, Joseph A1 - Thomopulos, Dimitri T1 - The MIP Workshop 2023 Computational Competition on reoptimization BT - The MIP workshop 2023 computational computational competition JF - Mathematical Programming Computation N2 - 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. KW - Mixed integer optimization KW - Reoptimization KW - Warm starting KW - Computational optimization KW - 90-08 KW - 90C11 KW - 90C57 Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:523-19804 SN - 1867-2949 SN - 1867-2957 VL - 16 IS - 2 SP - 255 EP - 266 PB - Springer Nature CY - Berlin/Heidelberg ER -