# Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch

arXiv: https://arxiv.org/abs/2206.06965 · HTML: https://mlsanity.com/paper/2206.06965/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 40 references that are in the map.
- First posted on arXiv 14 Jun 2022.

## Builds on (most cited first, 13 of 13)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers](https://mlsanity.com/paper/2011.06069/) (2020)
- [Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero](https://mlsanity.com/paper/1905.11623/) (2019)
- [Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning](https://mlsanity.com/paper/1809.03359/) (2018)
- [Cuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman Problem](https://mlsanity.com/paper/1805.01415/) (2018)
- [ML4CO-KIDA: Knowledge Inheritance in Dataset Aggregation](https://mlsanity.com/paper/2201.10328/) (2022)
- [ML4CO: Is GCNN All You Need? Graph Convolutional Neural Networks Produce Strong Baselines For Combinatorial Optimization Problems, If Tuned and Trained Properly, on Appropriate Data](https://mlsanity.com/paper/2112.12251/) (2021)

## Built on by (most cited first, 12 of 12)

- [Lookback for Learning to Branch](https://mlsanity.com/paper/2206.14987/) (2022)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [Generative AI and Process Systems Engineering: The Next Frontier](https://mlsanity.com/paper/2402.10977/) (2024)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [DISeR: Designing Imaging Systems with Reinforcement Learning](https://mlsanity.com/paper/2309.13851/) (2023)
- [Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks](https://mlsanity.com/paper/2311.13843/) (2023)
- [Revisiting Space Mission Planning: A Reinforcement Learning-Guided Approach for Multi-Debris Rendezvous](https://mlsanity.com/paper/2409.16882/) (2024)
- [Deep Sensitivity Analysis for Objective-Oriented Combinatorial Optimization](https://mlsanity.com/paper/2403.00016/) (2024)
- [Towards Interpreting Multi-Objective Feature Associations](https://mlsanity.com/paper/2403.00017/) (2024)
- [Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching](https://mlsanity.com/paper/2511.21107/) (2025)
- [Discounted Pseudocosts in MILP](https://mlsanity.com/paper/2407.06237/) (2024)
- [Optimization of Link Configuration for Satellite Communication Using Reinforcement Learning](https://mlsanity.com/paper/2501.08220/) (2025)

## Abstract (arXiv)

Branch-and-bound is a systematic enumerative method for combinatorial optimization, where the performance highly relies on the variable selection strategy. State-of-the-art handcrafted heuristic strategies suffer from relatively slow inference time for each selection, while the current machine learning methods require a significant amount of labeled data. We propose a new approach for solving the data labeling and inference latency issues in combinatorial optimization based on the use of the reinforcement learning (RL) paradigm. We use imitation learning to bootstrap an RL agent and then use Proximal Policy Optimization (PPO) to further explore global optimal actions. Then, a value network is used to run Monte-Carlo tree search (MCTS) to enhance the policy network. We evaluate the performance of our method on four different categories of combinatorial optimization problems and show that our approach performs strongly compared to the state-of-the-art machine learning and heuristics based methods.