A Machine Learning-Based Approximation of Strong Branching

A Machine Learning-Based Approximation of Strong Branching

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: branch and bound, learning, heuristics, decision
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.

Reviews

Required fields are marked *. Your email address will not be published.