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

Measuring the impact of branching rules for mixed-integer programming

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-64722
  • Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Gerald GamrathORCiD, Christoph Schubert
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:branch-and-bound; branching rule; mixed-integer programming; strong branching
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-08 Computational methods
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B40 Search theory
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
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] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Datum der Erstveröffentlichung:27.07.2017
Schriftenreihe (Bandnummer):ZIB-Report (17-34)
ISSN:1438-0064
Verlagspublikation:Appeared in: Operations Reseach Proceedings 2017 (2018) pp 165-170
DOI:https://doi.org/10.1007/978-3-319-89920-6_23
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.