Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 10 von 16
Zurück zur Trefferliste

Three Enhancements for Optimization-Based Bound Tightening

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-57803
  • 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% to 19% on average. Most importantly, more instances can be solved when using OBBT.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Ambros GleixnerORCiD, Timo BertholdORCiD, Benjamin MüllerORCiD, Stefan Weltge
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:MINLP; OBBT; bound tightening; optimality-based bound tightening; optimization-based bound tightening; propagation
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Klassifikation:G. Mathematics of Computing
Datum der Erstveröffentlichung:08.03.2016
Schriftenreihe (Bandnummer):ZIB-Report (15-16)
ISSN:1438-0064
Verlagspublikation:Journal of Global Optimization
DOI:https://doi.org/10.1007/s10898-016-0450-4
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.