Optimization Online


Online Learning for Strong Branching Approximation in Branch-and-Bound

Alejandro Marcos Alvarez(amarcos***at***ulg.ac.be)
Louis Wehenkel(l.wehenkel***at***ulg.ac.be)
Quentin Louveaux(q.louveaux***at***ulg.ac.be)

Abstract: 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.

Keywords: branch-and-bound, variable branching, online learning

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- Science and Engineering (Data-Mining )

Citation: 2016, Department of Electrical Engineering and Computer Science, Universite de Liege

Download: [PDF]

Entry Submitted: 01/26/2016
Entry Accepted: 01/26/2016
Entry Last Modified: 01/26/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society