Article ID: | iaor2017291 |
Volume: | 29 |
Issue: | 1 |
Start Page Number: | 185 |
End Page Number: | 195 |
Publication Date: | Feb 2017 |
Journal: | INFORMS Journal on Computing |
Authors: | Louveaux Quentin, Wehenkel Louis, Alvarez Alejandro Marcos |
Keywords: | programming: branch and bound, learning, heuristics, decision |
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.