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 |
Preprint: | urn:nbn:de:0297-zib-64722 |
DOI: | https://doi.org/10.1007/978-3-319-89920-6_23 |