Measuring the Impact of Branching Rules for Mixed-Integer Programming

Gerald Gamrath () and Christoph Schubert ()
Additional contact information
Gerald Gamrath: Zuse Institute Berlin
Christoph Schubert: Zuse Institute Berlin

A chapter in Operations Research Proceedings 2017, 2018, pp 165-170 from Springer

Abstract: Abstract 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.

Keywords: Mixed-integer programming; Branch-and-bound; Branching rule; Strong branch (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-89920-6_23

Ordering information: This item can be ordered from
http://www.springer.com/9783319899206

DOI: 10.1007/978-3-319-89920-6_23

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().