Improving strong branching by propagation

  • Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Gerald Gamrath
Editor:Carla Gomes, Meinolf Sellmann
Document Type:Article
Parent Title (English):Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Volume:7874
First Page:347
Last Page:354
Series:Lecture Notes in Computer Science
Publisher:Springer Berlin Heidelberg
Year of first publication:2013
Preprint:urn:nbn:de:0297-zib-17701
DOI:https://doi.org/10.1007/978-3-642-38171-3_25