Further results on an abstract model for branching and its application to mixed integer programming
- PDF / 537,289 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 212 Views
Series A
Further results on an abstract model for branching and its application to mixed integer programming Daniel Anderson1
· Pierre Le Bodic2 · Kerri Morgan3
Received: 3 September 2019 / Accepted: 20 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract 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. Keywords Branch and bound · Mixed-integer programming · Algorithm analysis · Branching rules Mathematics Subject Classification 90C11 · 68Q25
Daniel Anderson and Kerri Morgan: Work completed in part while the author was employed at Monash University.
B
Daniel Anderson [email protected] Pierre Le Bodic [email protected] Kerri Morgan [email protected]
1
Computer Science Department, Carnegie Mellon University, Pittsburgh, USA
2
Faculty of Information Technology, Monash University, Caulfield, Australia
3
School of Information Technology, Faculty of Science, Engineering & Built Environment, Deakin University, Geelong, Australia
123
D. Anderson et al.
1 Introduction Modern mixed-integer programming (MIP) solvers and many other combinatorial optimisation technologies are driven by the branch and bound (B&B) method [18]. In MIP solvers, B&B consists in solving a linear program (LP) relaxation of the MIP and recursively splitting the domains of integer variables whose values are fractional in the solution to the relaxation. The choice of fractional variable to branch on can drastically affect the size of the resulting search trees, potentially leading to orders of magnitude variations in solving time. Modern branching rules prefer branching on variables that most improve the dual bound at the created children, and thus, for the purpose of ranking them, reduce candidate variables to couples of values corresponding to their estimated dual gap improvements. The analysis and application of these couples of improvements, or so called branching tuples for n-ary branching, is studied extensively in the context of Satisfiability by Kullman [17], where it is shown that their quality can be essentially described by a s
Data Loading...
