A Machine Learning-Based Approximation of Strong Branching
Alejandro Marcos Alvarez, Quentin Louveaux, Louis Wehenkel
INFORMS Journal on Computing · 2017 · Volume 29 · Issue 1
Abstract
We present in this paper a new generic approach to variable branching in branch and bound for mixed-integer linear problems. Our approach consists in imitating the decisions taken by a good branching strategy, namely strong branching, with a fast approximation. This approximated function is created by a machine learning technique from a set of observed branching decisions taken by strong branching. The philosophy of the approach is similar to reliability branching. However, our approach can catch more complex aspects of observed previous branchings to take a branching decision. The experiments performed on randomly generated and MIPLIB problems show promising results.
Keywords
branch and bound, variable branching, strong branching, supervised machine learning
Enable JavaScript for citation tools and additional paper interactions.