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

Undercover: a primal MINLP heuristic exploring a largest sub-MIP

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-14631
  • We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Timo BertholdORCiD, Ambros GleixnerORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Large Neighborhood Search; Mixed-Integer Quadratically Constrained Programming; Mixed-Integer Nonlinear Programming; Nonconvex Optimization; Primal Heuristic
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C20 Quadratic programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C26 Nonconvex programming, global optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C30 Nonlinear programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C59 Approximation methods and heuristics
Datum der Erstveröffentlichung:06.02.2012
Schriftenreihe (Bandnummer):ZIB-Report (12-07)
ISSN:1438-0064
ZIB-Reportnummer:12-07
Verlagspublikation:Mathematical Programming
Preprint:urn:nbn:de:0297-zib-14631
DOI:https://doi.org/10.1007/s10107-013-0635-2
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.