Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm

2020-05-20 · Marc Etheve, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum

Mixed integer linear programs are commonly solved by Branch and Bound algorithms. A key factor of the efficiency of the most successful commercial solvers is their fine-tuned heuristics. In this paper, we leverage patterns in real-world instances to learn from scratch a new branching strategy optimised for 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 value function and a global metric of interest. In addition, we provide insights for adapting known RL techniques to the Branch and Bound setting, and present a new neural network architecture inspired from the literature. To our knowledge, it is the first time Reinforcement Learning has been used to fully optimise the branching strategy. Computational experiments show that our method is appropriate and able to generalise well to new instances.

📄 PDF Abstract BibTeX arXiv:2005.10026

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Variable Selection

A Markov Decision Process for Variable Selection in Branch & Bound

2025-10-22 · Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan 외 arxiv

Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and Bound (B&B). A key factor influencing the performanc…

Reinforcement Learning

TreeDQN: Learning to minimize Branch-and-Bound tree

2023-06-09 · Dmitry Sorokin, Alexander Kostin

Combinatorial optimization problems require an exhaustive search to find the optimal solution. A convenient approach to solving combinatorial optimization tasks in the form of Mixed Integer Linear Programs is Branch-and-…

Combinatorial Optimization reinforcement-learning Reinforcement Learning Variable Selection

Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends

2021-11-05 · Lingying Huang, Xiaomeng Chen, Wei Huo, Jiazheng Wang 외

In this paper, we surveyed the existing literature studying different approaches and algorithms for the four critical components in the general branch and bound (B&B) algorithm, namely, branching variable selection, node…

Variable Selection

Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization

2025-11-12 · Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan 외 arxiv

Mixed-Integer Linear Programming (MILP) lies at the core of many real-world combinatorial optimization (CO) problems, traditionally solved by branch-and-bound (B&B). A key driver influencing B&B solvers efficiency is the…

Reinforcement Learning

ReviBranch: Deep Reinforcement Learning for Branch-and-Bound with Revived Trajectories

2025-08-24 · Dou Jiabao, Nie Jiayi, Yihang Cheng, Jinwei Liu 외 arxiv

The Branch-and-bound (B&B) algorithm is the main solver for Mixed Integer Linear Programs (MILPs), where the selection of branching variable is essential to computational efficiency. However, traditional heuristics for b…

Computational Efficiency Reinforcement Learning