A Markov Decision Process for Variable Selection in Branch & Bound
Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, Emmanuel Rachelson · 2025
Read A Markov Decision Process for Variable Selection in Branch & Bound by Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, Emmanuel Rachelson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19348.txt.
Description
Paul Strang and five co-authors formulate variable selection in branch and bound as a standard Markov decision process, giving reinforcement learning a clean footing in integer programming solvers. Branch and bound solves hard combinatorial problems, and which variable it branches on strongly shapes how fast the search finishes.
Earlier learning approaches used custom formulations and one-off convergence results. The new BBMDP model is deliberately plain, so a broad range of reinforcement learning algorithms can be applied to learn branching policies. Experiments validate the model, opening solver tuning to the standard toolbox of sequential decision research.
Catalog record
| CREATOR | Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, Emmanuel Rachelson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-19348