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

Estimating the Size of Branch-And-Bound Trees

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-78144
  • This paper investigates the estimation of the size of Branch-and-Bound (B&B) trees for solving mixed-integer programs. We first prove that the size of the B&B tree cannot be approximated within a factor of~2 for general binary programs, unless P equals NP. Second, we review measures of the progress of the B&B search, such as the gap, and propose a new measure, which we call leaf frequency. We study two simple ways to transform these progress measures into B&B tree size estimates, either as a direct projection, or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using Machine Learning techniques, which yields more precise estimates than any individual measure. The best method we have identified uses all individual measures as features of a random forest model. In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B&B tree sizes within a factor of 3 on the set of unseen test instances even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor 2 over the entire search on each out of six additional sets of homogeneous instances we have tested. All techniques are available in version 7 of the branch-and-cut framework SCIP.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Gregor HendelORCiD, Daniel AndersonORCiD, Pierre Le BodicORCiD, Marc PfetschORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:branch and bound; forecasting; machine learning; mixed integer programming
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Datum der Erstveröffentlichung:03.04.2020
Schriftenreihe (Bandnummer):ZIB-Report (20-02)
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.