# Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 62 references that are in the map.
- First posted on arXiv 28 May 2022.

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

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents](https://mlsanity.com/paper/1712.06560/) (2017)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Learning Montezuma's Revenge from a Single Demonstration](https://mlsanity.com/paper/1812.03381/) (2018)
- [Hindsight Credit Assignment](https://mlsanity.com/paper/1912.02503/) (2019)
- [Keeping Your Distance: Solving Sparse Reward Tasks Using Self-Balancing Shaped Rewards](https://mlsanity.com/paper/1911.01417/) (2019)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers](https://mlsanity.com/paper/2011.06069/) (2020)
- [Variance Reduction for Reinforcement Learning in Input-Driven Environments](https://mlsanity.com/paper/1807.02264/) (2018)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)

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

- [Lookback for Learning to Branch](https://mlsanity.com/paper/2206.14987/) (2022)
- [Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation](https://mlsanity.com/paper/2310.14161/) (2023)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [Accelerating process control and optimization via machine learning: A review](https://mlsanity.com/paper/2412.18529/) (2024)
- [Reinforcement Learning for Node Selection in Branch-and-Bound](https://mlsanity.com/paper/2310.00112/) (2023)
- [LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs](https://mlsanity.com/paper/2605.10401/) (2026)
- [UNSAT Solver Synthesis via Monte Carlo Forest Search](https://mlsanity.com/paper/2211.12581/) (2022)
- [Search Strategy Generation for Branch and Bound Using Genetic Programming](https://mlsanity.com/paper/2412.09444/) (2024)
- [Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization](https://mlsanity.com/paper/2511.09219/) (2025)
- [TreeDQN: Sample-Efficient Off-Policy Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/2306.05905/) (2023)
- [Modeling Churn in Recommender Systems with Aggregated Preferences](https://mlsanity.com/paper/2502.18483/) (2025)
- [Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching](https://mlsanity.com/paper/2511.21107/) (2025)
- [Network Aware Compute and Memory Allocation in Optically Composable Data Centres with Deep Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2211.02466/) (2022)
- [Partitioning Distributed Compute Jobs with Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2301.13799/) (2023)
- [Discounted Pseudocosts in MILP](https://mlsanity.com/paper/2407.06237/) (2024)
- [Churn-Aware Recommendation Planning under Aggregated Preference Feedback](https://mlsanity.com/paper/2507.04513/) (2025)
- [A Markov Decision Process for Variable Selection in Branch & Bound](https://mlsanity.com/paper/2510.19348/) (2025)
- [Designing faster mixed integer linear programming algorithm via learning the optimal path](https://mlsanity.com/paper/2601.16056/) (2026)
- [Reformulation-Contrastive Learning for Mixed Integer Programs](https://mlsanity.com/paper/2610.00730/) (2026)
- [Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2610.14835/) (2026)

## Abstract (arXiv)

Combinatorial optimisation problems framed as mixed integer linear programmes (MILPs) are ubiquitous across a range of real-world applications. The canonical branch-and-bound algorithm seeks to exactly solve MILPs by constructing a search tree of increasingly constrained sub-problems. In practice, its solving time performance is dependent on heuristics, such as the choice of the next variable to constrain ('branching'). Recently, machine learning (ML) has emerged as a promising paradigm for branching. However, prior works have struggled to apply reinforcement learning (RL), citing sparse rewards, difficult exploration, and partial observability as significant challenges. Instead, leading ML methodologies resort to approximating high quality handcrafted heuristics with imitation learning (IL), which precludes the discovery of novel policies and requires expensive data labelling. In this work, we propose retro branching; a simple yet effective approach to RL for branching. By retrospectively deconstructing the search tree into multiple paths each contained within a sub-tree, we enable the agent to learn from shorter trajectories with more predictable next states. In experiments on four combinatorial tasks, our approach enables learning-to-branch without any expert guidance or pre-training. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables, with ablations verifying that our retrospectively constructed trajectories are essential to achieving these results.