Reference : Online Learning for Strong Branching Approximation in Branch-and-Bound
E-prints/Working papers : First made available on ORBi
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/192361
Online Learning for Strong Branching Approximation in Branch-and-Bound
English
Marcos Alvarez, Alejandro mailto [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Wehenkel, Louis 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 >]
2016
No
[en] branch-and-bound ; variable branching ; online learning
[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.
http://hdl.handle.net/2268/192361

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
online-var-branch.pdfAuthor preprint199.83 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.