A Machine Learning-Based Approximation of Strong Branching

作者：Alejandro Marcos Alvarez, Quentin Louveaux, Louis Wehenkel · 发表于：INFORMS journal on computing · 年份：2017 · DOI：10.1287/ijoc.2016.0723 · 被引用次数：177 · 研究领域：Machine Learning and Algorithms、Reliability and Maintenance Optimization、Complexity and Algorithms in Graphs

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.