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

Improving strong branching by propagation

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-17701
  • Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Gerald GamrathORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:branch-and-bound; branching rule; domain propagation; mixed-integer programming; strong branching
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Datum der Erstveröffentlichung:21.12.2012
Schriftenreihe (Bandnummer):ZIB-Report (12-46)
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.