A Markov Decision Process for Variable Selection in Branch & Bound

2025-10-22 · Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, Emmanuel Rachelson 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 performance of B&B solvers is the variable selection heuristic governing branching decisions. Recent contributions have sought to adapt reinforcement learning (RL) algorithms to the B&B setting to learn optimal branching policies, through Markov Decision Processes (MDP) inspired formulations, and ad hoc convergence theorems and algorithms. In this work, we introduce BBMDP, a principled vanilla MDP formulation for variable selection in B&B, allowing to leverage a broad range of RL algorithms for the purpose of learning optimal B\&B heuristics. Computational experiments validate our model empirically, as our branching agent outperforms prior state-of-the-art RL agents on four standard MILP benchmarks.

📄 PDF Abstract BibTeX arXiv:2510.19348

Code (0)

등록된 구현이 없습니다.

Tasks

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

Model-free Reinforcement Learning for Branching Markov Decision Processes

2021-06-12 · Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi 외

We study reinforcement learning for the optimal control of Branching Markov Decision Processes (BMDPs), a natural extension of (multitype) Branching Markov Chains (BMCs). The state of a (discrete-time) BMCs is a collecti…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning

2022-07-26 · Zeren Huang, WenHao Chen, Weinan Zhang, Chuhan Shi 외

Deriving a good variable selection strategy in branch-and-bound is essential for the efficiency of modern mixed-integer programming (MIP) solvers. With MIP branching data collected during the previous solution process, l…

Decision Making Reinforcement Learning (RL)Sequential Decision Making Variable Selection

Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms

2024-07-10 · Jayanth Bhargav, Mahsa Ghasemi, Shreyas Sundaram

Factored Markov Decision Processes (fMDPs) are a class of Markov Decision Processes (MDPs) in which the states (and actions) can be factored into a set of state (and action) variables and can be encoded compactly using a…

Sequential Knockoffs for Variable Selection in Reinforcement Learning

2023-03-24 · Tao Ma, Jin Zhu, Hengrui Cai, Zhengling Qi 외

In real-world applications of reinforcement learning, it is often challenging to obtain a state representation that is parsimonious and satisfies the Markov property without prior knowledge. Consequently, it is common pr…

reinforcement-learning Reinforcement Learning Variable Selection