mlsanityData to 14 Oct 2026

Learning to branch with Tree MDPs

arXiv 2205.11107 ↗First posted 23 May 2022cs.LG math.OCcited by 45

Not on the map. Why?

Abstract (arXiv)

State-of-the-art Mixed Integer Linear Program (MILP) solvers combine systematic tree search with a plethora of hard-coded heuristics, such as the branching rule. The idea of learning branching rules from data has received increasing attention recently, and promising results have been obtained by learning fast approximations of the strong branching expert. In this work, we instead propose to learn branching rules from scratch via Reinforcement Learning (RL). We revisit the work of Etheve et al. (2020) and propose tree Markov Decision Processes, or tree MDPs, a generalization of temporal MDPs that provides a more suitable framework for learning to branch. We derive a tree policy gradient theorem, which exhibits a better credit assignment compared to its temporal counterpart. We demonstrate through computational experiments that tree MDPs improve the learning convergence, and offer a promising framework for tackling the learning-to-branch problem in MILPs.

Key facts. Cited by 45 papers in the map (data through 14 Oct 2026). Builds on 12 of its 36 references that are in the map. First posted on arXiv 23 May 2022.

Builds on

12 of 36 references.

References · 12

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  4. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  5. 2020Solving Mixed Integer Programs Using Neural Networkscited by 182
  6. 2020Hybrid Models for Learning to Branchcited by 95
  7. 2020Parameterizing Branch-and-Bound Search Trees to Learn Branching Policiescited by 63
  8. 2021Learning to Schedule Heuristics in Branch-and-Boundcited by 46
  9. 2020Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solverscited by 43
  10. 2020Reinforcement Learning for Variable Selection in a Branch and Bound Algorithmcited by 29
  11. 2021A Theoretical and Computational Analysis of Full Strong-Branchingcited by 13
  12. 2018Cuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman Problemcited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 10; 2024: 10; 2025: 15; 2026: 6.

45 papers.

Sort:

By area:

  1. 2023Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Modelcited by 45
  2. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  3. 2024Towards Foundation Models for Mixed Integer Linear Programmingcited by 31
  4. 2022Lookback for Learning to Branchcited by 27
  5. 2024Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programmingcited by 24
  6. 2022On Representing Mixed-Integer Linear Programs by Graph Neural Networkscited by 23
  7. 2024Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programscited by 16
  8. 2025Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programmingcited by 16
  9. 2023Learning to Configure Separators in Branch-and-Cutcited by 14
  10. 2023Promoting Generalization for Exact Solvers via Adversarial Instance Augmentationcited by 12
  11. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  12. 2024Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programmingcited by 12
33 more
  1. 2025FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimizationcited by 11
  2. 2024CAMBranch: Contrastive Learning with Augmented MILPs for Branchingcited by 10
  3. 2023Symbolic Regression via Control Variable Genetic Programmingcited by 9
  4. 2024SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branchcited by 9
  5. 2025Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Schedulingcited by 7
  6. 2023Online Learning for Scheduling MIP Heuristicscited by 6
  7. 2022Local Branching Relaxation Heuristics for Integer Linear Programscited by 4
  8. 2025Towards graph neural networks for provably solving convex optimization problemscited by 4
  9. 2022UNSAT Solver Synthesis via Monte Carlo Forest Searchcited by 3
  10. 2023Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solvercited by 3
  11. 2025STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimizationcited by 3
  12. 2023BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problemscited by 2
  13. 2024AlphaMapleSAT: An MCTS-based Cube-and-Conquer SAT Solver for Hard Combinatorial Problemscited by 2
  14. 2025Conversation Forests: The Key to Fine Tuning Large Language Models for Multi-Turn Medical Conversations is Branchingcited by 2
  15. 2025Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimizationcited by 2
  16. 2023Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branchingcited by 1
  17. 2023TreeDQN: Sample-Efficient Off-Policy Reinforcement Learning for Combinatorial Optimizationcited by 1
  18. 2025Modeling Churn in Recommender Systems with Aggregated Preferencescited by 1
  19. 2025Solve Smart, Not Often: Policy Learning for Costly MILP Re-solvingcited by 1
  20. 2025Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branchingcited by 1
  21. 2026A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attentioncited by 1
  22. 2024Subsampled Ensemble Can Improve Generalization Tail Exponentiallycited by 0
  23. 2024Discounted Pseudocosts in MILPcited by 0
  24. 2025Churn-Aware Recommendation Planning under Aggregated Preference Feedbackcited by 0
  25. 2025FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programmingcited by 0
  26. 2025Collab-Solver: Collaborative Solving Policy Learning for Mixed-Integer Linear Programmingcited by 0
  27. 2025A Markov Decision Process for Variable Selection in Branch & Boundcited by 0
  28. 2025Learning Branching Policies for MILPs with Proximal Policy Optimizationcited by 0
  29. 2026Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branchingcited by 0
  30. 2026DiBS: Diffusion-Informed Branch Selectioncited by 0
  31. 2026SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programmingcited by 0
  32. 2026BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolutioncited by 0
  33. 2026OPTS-TTPO: Enhancing Finite-Sample Policy-Gradient Learning with Tree Searchcited by 0