<  Back to the Polytechnique Montréal portal

On generalized surrogate duality in mixed-integer nonlinear programming

Benjamin Müller, Gonzalo Muñoz, Maxime Gasse, Ambros Gleixner, Andrea Lodi, Felipe Serrano

Article (2021)

Open Acess document in PolyPublie and at official publisher
[img]
Preview
Open Access to the full text of this document
Published Version
Terms of Use: Creative Commons Attribution
Download (600kB)
Show abstract
Hide abstract

Abstract

The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global -optimality with spatial branch and bound is a tight, computationallytractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solverscan often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, weexploit 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 andchallenges 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 thealgorithm's ability to generate strong dual bounds through extensive computational experiments.

Uncontrolled Keywords

Surrogate relaxation, MINLP, Nonconvex optimization

Subjects: 2700 Information technology > 2713 Algorithms
2700 Information technology > 2714 Mathematics of computing
Department: Department of Mathematics and Industrial Engineering
Research Center: Other
Funders: Research Campus MODAL, Institute for Data Valorization - Postdoctoral Fellowship
Grant number: 05M14ZAM, 05M20ZBM
PolyPublie URL: https://publications.polymtl.ca/9256/
Journal Title: Mathematical Programming (vol. 2021)
Publisher: Springer Nature
DOI: 10.1007/s10107-021-01691-6
Official URL: https://doi.org/10.1007/s10107-021-01691-6
Date Deposited: 24 Mar 2022 10:33
Last Modified: 11 Nov 2022 13:36
Cite in APA 7: 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, 1-30. https://doi.org/10.1007/s10107-021-01691-6

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Dimensions

Repository Staff Only

View Item View Item