Three enhancements for optimization-based bound tightening

Ambros M. Gleixner (), Timo Berthold (), Benjamin Müller () and Stefan Weltge ()
Additional contact information
Ambros M. Gleixner: Zuse Institute Berlin
Timo Berthold: Fair Isaac Germany GmbH, c/o Zuse Institute Berlin
Benjamin Müller: Zuse Institute Berlin
Stefan Weltge: Institute for Operations Research, ETH Zürich

Journal of Global Optimization, 2017, vol. 67, issue 4, No 2, 757 pages

Abstract: 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 efficient 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 beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering 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 that OBBT is most beneficial on hard instances, for which we observe a speedup of 17–19 % 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 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-016-0450-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:67:y:2017:i:4:d:10.1007_s10898-016-0450-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-016-0450-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().