TY - CHAP 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 T2 - Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020 N2 - The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-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 solver 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. Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-45771-6_25 SP - 322 EP - 337 ER - TY - GEN 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 N2 - The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-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 solver 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. T3 - ZIB-Report - 19-55 KW - surrogate relaxation KW - MINLP KW - nonconvex optimization Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75179 SN - 1438-0064 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. Y1 - 2022 U6 - https://doi.org/10.1007/s10107-021-01691-6 VL - 192 IS - 1 SP - 89 EP - 118 ER - TY - GEN A1 - Gamrath, Gerald A1 - Anderson, Daniel A1 - Bestuzheva, Ksenia A1 - Chen, Wei-Kun A1 - Eifler, Leon A1 - Gasse, Maxime A1 - Gemander, Patrick A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Halbig, Katrin A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Le Bodic, Pierre A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Miltenberger, Matthias A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Tawfik, Christine A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 7.0 N2 - 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. T3 - ZIB-Report - 20-10 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78023 SN - 1438-0064 ER - TY - CHAP A1 - Gasse, Maxime A1 - Bowly, Simon A1 - Cappart, Quentin A1 - Charfreitag, Jonas A1 - Charlin, Laurent A1 - Chételat, Didier A1 - Chmiela, Antonia A1 - Dumouchelle, Justin A1 - Gleixner, Ambros A1 - Kazachkov, Aleksandr M. A1 - Khalil, Elias A1 - Lichocki, Pawel A1 - Lodi, Andrea A1 - Lubin, Miles A1 - Maddison, Chris J. A1 - Christopher, Morris A1 - Papageorgiou, Dimitri J. A1 - Parjadis, Augustin A1 - Pokutta, Sebastian A1 - Prouvost, Antoine A1 - Scavuzzo, Lara A1 - Zarpellon, Giulia A1 - Yang, Linxin A1 - Lai, Sha A1 - Wang, Akang A1 - Luo, Xiaodong A1 - Zhou, Xiang A1 - Huang, Haohan A1 - Shao, Shengcheng A1 - Zhu, Yuanming A1 - Zhang, Dong A1 - Quan, Tao A1 - Cao, Zixuan A1 - Xu, Yang A1 - Huang, Zhewei A1 - Zhou, Shuchang A1 - Binbin, Chen A1 - Minggui, He A1 - Hao, Hao A1 - Zhiyu, Zhang A1 - Zhiwu, An A1 - Kun, Mao T1 - The Machine Learning for Combinatorial Optimization Competition (ML4CO): results and insights T2 - Proceedings of Conference on Neural Information Processing Systems Y1 - 2022 ER -