Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.19348 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912664010096640 |
|---|---|
| author | Strang, Paul Alès, Zacharie Bissuel, Côme Juan, Olivier Kedad-Sidhoum, Safia Rachelson, Emmanuel |
| author_facet | Strang, Paul Alès, Zacharie Bissuel, Côme Juan, Olivier Kedad-Sidhoum, Safia Rachelson, Emmanuel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19348 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Markov Decision Process for Variable Selection in Branch & Bound Strang, Paul Alès, Zacharie Bissuel, Côme Juan, Olivier Kedad-Sidhoum, Safia Rachelson, Emmanuel Machine Learning 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. |
| title | A Markov Decision Process for Variable Selection in Branch & Bound |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2510.19348 |