Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm

  • 2020-05-20 13:15:48
  • Marc Etheve, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum
  • 0

Abstract

Mixed integer linear programs are commonly solved by Branch and Boundalgorithms. A key factor of the efficiency of the most successful commercialsolvers is their fine-tuned heuristics. In this paper, we leverage patterns inreal-world instances to learn from scratch a new branching strategy optimisedfor a given problem and compare it with a commercial solver. We propose FMSTS,a novel Reinforcement Learning approach specifically designed for this task.The strength of our method lies in the consistency between a local valuefunction and a global metric of interest. In addition, we provide insights foradapting known RL techniques to the Branch and Bound setting, and present a newneural network architecture inspired from the literature. To our knowledge, itis the first time Reinforcement Learning has been used to fully optimise thebranching strategy. Computational experiments show that our method isappropriate and able to generalise well to new instances.

 

Quick Read (beta)

loading the full paper ...