Reference : A Machine Learning-Based Approximation of Strong Branching
Scientific journals : Article
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/198561
A Machine Learning-Based Approximation of Strong Branching
English
Marcos Alvarez, Alejandro mailto [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Louveaux, Quentin mailto [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation : Optimisation discrète >]
Wehenkel, Louis mailto [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Jan-2017
INFORMS Journal on Computing
INFORMS: Institute for Operations Research
29
1
185-195
Yes (verified by ORBi)
International
1091-9856
1526-5528
[en] branch-and-bound ; strong branching ; supervised learning
[en] 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 in order to take a branching decision. The experiments performed on randomly generated and MIPLIB problems show promising results.
http://hdl.handle.net/2268/198561
10.1287/ijoc.2016.0723

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
ijoc.pdfAuthor postprint261.81 kBView/Open

Additional material(s):

File Commentary Size Access
Open access
ijoc-appendices-1.pdf155.2 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.