Eprint first made available on ORBi (E-prints, working papers and research blog)
Online Learning for Strong Branching Approximation in Branch-and-Bound
Marcos Alvarez, Alejandro; Wehenkel, Louis; Louveaux, Quentin
2016
 

Files


Full Text
online-var-branch.pdf
Author preprint (204.62 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
branch-and-bound; variable branching; online learning
Abstract :
[en] We present an online learning approach to variable branching in branch-and-bound for mixed-integer linear problems. Our approach consists in learning strong branching scores in an online fashion and in using them to take branching decisions. More specifically, numerical scores are used to rank the branching candidates. If, for a given variable, the learned approximation is deemed reliable, then the score for that variable is computed thanks to the learned function. If the approximation is not reliable yet, the real strong branching score is used instead. The scores that are computed through the real strong branching procedure are fed to the online learning algorithm in order to improve the approximated function. The experiments show promising results.
Disciplines :
Computer science
Author, co-author :
Marcos Alvarez, Alejandro ;  Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Wehenkel, Louis  ;  Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Louveaux, Quentin ;  Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation : Optimisation discrète
Language :
English
Title :
Online Learning for Strong Branching Approximation in Branch-and-Bound
Publication date :
2016
Available on ORBi :
since 26 January 2016

Statistics


Number of views
533 (10 by ULiège)
Number of downloads
499 (3 by ULiège)

Bibliography


Similar publications



Contact ORBi