Benjamin Müller, Gonzalo Muñoz, Maxime Gasse, Ambros Gleixner, Andrea Lodi and Felipe Serrano
Article (2021)
|
Published Version Terms of Use: Creative Commons Attribution . Download (1MB) |
Cite this document: | Müller, B., Muñoz, G., Gasse, M., Gleixner, A., Lodi, A. & Serrano, F. (2021). On generalized surrogate duality in mixed-integer nonlinear programming. Mathematical Programming, 2021, p. 1-30. doi:10.1007/s10107-021-01691-6 |
---|
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.
Uncontrolled Keywords
Surrogate relaxation, MINLP, Nonconvex optimization
![]() |
|
Subjects: |
2700 Technologie de l'information > 2713 Algorithmes 2700 Technologie de l'information > 2714 Mathématiques de l'informatique |
---|---|
Department: | Département de mathématiques et de génie industriel |
Research Center: | Autre |
Funders: | Research Campus MODAL, Institute for Data Valorization - Postdoctoral Fellowship |
Grant number: | 05M14ZAM, 05M20ZBM |
Date Deposited: | 24 Mar 2022 10:33 |
Last Modified: | 25 Mar 2022 01:20 |
PolyPublie URL: | https://publications.polymtl.ca/9256/ |
![]() |
|
Journal Title: | Mathematical Programming (vol. 2021) |
---|---|
Publisher: | Springer Nature |
Official URL: | https://doi.org/10.1007/s10107-021-01691-6 |
Statistics
Total downloads
Downloads per month in the last year
Origin of downloads
Dimensions