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

Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-72653
  • We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Daniel AndersonORCiD, Gregor HendelORCiD, Pierre Le BodicORCiD, Jan Merlin Viernickel
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Mixed-Integer Programming solvers; Progress measures; Restart; tree-size estimates
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Datum der Erstveröffentlichung:26.02.2019
Schriftenreihe (Bandnummer):ZIB-Report (19-11)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.