Eprint first made available on ORBi (E-prints, working papers and research blog)
A Supervised Machine Learning Approach to Variable Branching in Branch-And-Bound
Marcos Alvarez, Alejandro; Louveaux, Quentin; Wehenkel, Louis
2014
 

Files


Full Text
ecml.pdf
Author preprint (187.6 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
branch-and-bound; variable branching; supervised learning
Abstract :
[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.
Disciplines :
Computer science
Author, co-author :
Marcos Alvarez, Alejandro ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Louveaux, Quentin ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
Wehenkel, Louis  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Language :
English
Title :
A Supervised Machine Learning Approach to Variable Branching in Branch-And-Bound
Publication date :
2014
Available on ORBi :
since 15 May 2014

Statistics


Number of views
987 (4 by ULiège)
Number of downloads
1197 (6 by ULiège)

Bibliography


Similar publications



Contact ORBi