TY - JOUR
T1 - Further results on an abstract model for branching and its application to mixed integer programming
AU - Anderson, Daniel
AU - Le Bodic, Pierre
AU - Morgan, Kerri
PY - 2021/11
Y1 - 2021/11
N2 - A key ingredient in branch and bound (B&B) solvers for mixed-integer programming (MIP) is the selection of branching variables since poor or arbitrary selection can affect the size of the resulting search trees by orders of magnitude. A recent article by Le Bodic and Nemhauser (Math Program 166(1–2):369–405, 2017) investigated variable selection rules by developing a theoretical model of B&B trees from which they developed some new, effective scoring functions for MIP solvers. In their work, Le Bodic and Nemhauser left several open theoretical problems, solutions to which could guide the future design of variable selection rules. In this article, we first solve many of these open theoretical problems. We then implement an improved version of the model-based branching rules in SCIP 6.0, a state-of-the-art academic MIP solver, in which we observe an 11 % geometric average time and node reduction on instances of the MIPLIB 2017 Benchmark Set that require large B&B trees.
AB - A key ingredient in branch and bound (B&B) solvers for mixed-integer programming (MIP) is the selection of branching variables since poor or arbitrary selection can affect the size of the resulting search trees by orders of magnitude. A recent article by Le Bodic and Nemhauser (Math Program 166(1–2):369–405, 2017) investigated variable selection rules by developing a theoretical model of B&B trees from which they developed some new, effective scoring functions for MIP solvers. In their work, Le Bodic and Nemhauser left several open theoretical problems, solutions to which could guide the future design of variable selection rules. In this article, we first solve many of these open theoretical problems. We then implement an improved version of the model-based branching rules in SCIP 6.0, a state-of-the-art academic MIP solver, in which we observe an 11 % geometric average time and node reduction on instances of the MIPLIB 2017 Benchmark Set that require large B&B trees.
KW - Algorithm analysis
KW - Branch and bound
KW - Branching rules
KW - Mixed-integer programming
UR - http://www.scopus.com/inward/record.url?scp=85089895216&partnerID=8YFLogxK
U2 - 10.1007/s10107-020-01556-4
DO - 10.1007/s10107-020-01556-4
M3 - Article
AN - SCOPUS:85089895216
SN - 0025-5610
VL - 190
SP - 811
EP - 841
JO - Mathematical Programming
JF - Mathematical Programming
ER -