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

CREATORPaul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, Emmanuel Rachelson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19348

Browse the full library · About the Tower of Babel