Content area
Full Text
J Glob Optim (2017) 67:731757
DOI 10.1007/s10898-016-0450-4
Ambros M. Gleixner1 Timo Berthold2
Benjamin Mller1 Stefan Weltge3
Received: 28 April 2015 / Accepted: 29 May 2016 / Published online: 17 June 2016 Springer Science+Business Media New York 2016
Abstract Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efcient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is benecial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efciency of OBBT: ltering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate
This work was supported by the Research Campus Modal Mathematical Optimization and Data Analysis Laboratories funded by the German Ministry of Education and Research (BMBF Grant 05M14ZAM). All responsibilty for the content of this publication is assumed by the authors.
Electronic supplementary material The online version of this article (doi:http://dx.doi.org/10.1007/s10898-016-0450-4
Web End =10.1007/s10898-016-0450-4 ) contains supplementary material, which is available to authorized users.
B Timo Berthold
Ambros M. Gleixner [email protected]
Benjamin Mller [email protected]
Stefan [email protected] Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany2 Fair Isaac Germany GmbH, c/o Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany3 Institute for Operations Research, ETH Zrich, Rmistrasse 101, 8092 Zrich, Switzerland
http://crossmark.crossref.org/dialog/?doi=10.1007/s10898-016-0450-4&domain=pdf
Web End = http://crossmark.crossref.org/dialog/?doi=10.1007/s10898-016-0450-4&domain=pdf
Web End = Three enhancements for optimization-based bound tightening
123
732 J Glob Optim (2017) 67:731757
that OBBT is most benecial on hard instances, for which we observe a speedup of 1719% on average. Most importantly, more instances can be solved when using OBBT.
Keywords MINLP Optimization-based bound tightening Optimality-based bound
tightening OBBT Propagation Bound tightening
1 Introduction