A Machine Learning-Based Approximation of Strong Branching

Alejandro Marcos Alvarez (), Quentin Louveaux () and Louis Wehenkel ()
Additional contact information
Alejandro Marcos Alvarez: Department of Electrical Engineering and Computer Science, Université de Liège, Sart-Tilman B28, Liège, Belgium
Quentin Louveaux: Department of Electrical Engineering and Computer Science, Université de Liège, Sart-Tilman B28, Liège, Belgium
Louis Wehenkel: Department of Electrical Engineering and Computer Science, Université de Liège, Sart-Tilman B28, Liège, Belgium

INFORMS Journal on Computing, 2017, vol. 29, issue 1, 185-195

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 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0723 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:1:p:185-195

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().