Reference : A Supervised Machine Learning Approach to Variable Branching in Branch-And-Bound
E-prints/Working papers : First made available on ORBi
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/167559
A Supervised Machine Learning Approach to Variable Branching in Branch-And-Bound
English
Marcos Alvarez, Alejandro mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Louveaux, Quentin mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
Wehenkel, Louis mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
2014
No
[en] branch-and-bound ; variable branching ; supervised learning
[en] We present in this paper a new approach that uses supervised machine learning techniques to improve the performances of optimization algorithms in the context of mixed-integer programming (MIP). We focus on the branch-and-bound (B&B) algorithm, which is the traditional algorithm used to solve MIP problems. In B&B, variable branching is the key component that most conditions the efficiency of the optimization. Good branching strategies exist but are computationally expensive and usually hinder the optimization rather than improving it. Our approach consists in imitating the decisions taken by a supposedly good branching strategy, strong branching in our case, with a fast approximation. To this end, we develop a set of features describing the state of the ongoing optimization and show how supervised machine learning can be used to approximate the desired branching strategy. The approximated function is created by a supervised machine learning algorithm from a set of observed branching decisions taken by the target strategy. The experiments performed on randomly generated and standard benchmark (MIPLIB) problems show promising results.
http://hdl.handle.net/2268/167559

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
ecml.pdfAuthor preprint183.2 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.