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.
Citation
2016, Department of Electrical Engineering and Computer Science, Universite de Liege