Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Measuring the impact of branching rules for mixed-integer programming

  • 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.
Author:Gerald GamrathORCiD, Christoph Schubert
Document Type:In Proceedings
Parent Title (German):Operations Research Proceedings 2017
First Page:165
Last Page:170
Publisher:Springer International Publishing
Year of first publication:2018
Page Number:6
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.