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 -