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

From feasibility to improvement to proof: three phases of solving mixed-integer programs

  • Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points.
Metadaten
Verfasserangaben:Timo BertholdORCiD, Gregor HendelORCiD, Thorsten KochORCiD
Dokumentart:Artikel
Titel des übergeordneten Werkes (Englisch):Optimization Methods and Software
Band:33
Ausgabe / Heft:3
Erste Seite:499
Letzte Seite:517
Verlag:Taylor & Francis
Datum der Erstveröffentlichung:10.10.2017
Preprint:urn:nbn:de:0297-zib-61607
DOI:https://doi.org/10.1080/10556788.2017.1392519
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.