mlsanityData to 14 Oct 2026

Learning Branching Policies for MILPs with Proximal Policy Optimization

arXiv 2511.12986 ↗First posted 17 Nov 2025cs.LG cs.AI math.OCcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Branch-and-Bound (B&B) is the dominant exact solution method for Mixed Integer Linear Programs (MILP), yet its exponential time complexity poses significant challenges for large-scale instances. The growing capabilities of machine learning have spurred efforts to improve B&B by learning data-driven branching policies. However, most existing approaches rely on Imitation Learning (IL), which tends to overfit to expert demonstrations and struggles to generalize to structurally diverse or unseen instances. In this work, we propose Tree-Gate Proximal Policy Optimization (TGPPO), a novel framework that employs Proximal Policy Optimization (PPO), a Reinforcement Learning (RL) algorithm, to train a branching policy aimed at improving generalization across heterogeneous MILP instances. Our approach builds on a parameterized state space representation that dynamically captures the evolving context of the search tree. Empirical evaluations show that TGPPO often outperforms existing learning-based policies in terms of reducing the number of nodes explored and improving p-Primal-Dual Integrals (PDI), particularly in out-of-distribution instances. These results highlight the potential of RL to develop robust and adaptable branching strategies for MILP solvers.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 5 of its 16 references that are in the map. First posted on arXiv 17 Nov 2025.

Builds on

5 of 16 references.

References · 5

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  3. 2020Parameterizing Branch-and-Bound Search Trees to Learn Branching Policiescited by 63
  4. 2022Learning to branch with Tree MDPscited by 45
  5. 2022An Improved Reinforcement Learning Algorithm for Learning to Branchcited by 14

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2022Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories
  2. 2025A Markov Decision Process for Variable Selection in Branch & Bound
  3. 2025Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization
  4. 2022Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning
  5. 2022Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
  6. 2024CAMBranch: Contrastive Learning with Augmented MILPs for Branching
  7. 2025CORL: Reinforcement Learning of MILP Policies Solved via Branch and Bound
  8. 2024SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch