# Lookback for Learning to Branch

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

## Key facts

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

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [Learning to Select Cuts for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2105.13645/) (2021)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)
- [Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories](https://mlsanity.com/paper/2205.14345/) (2022)
- [Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch](https://mlsanity.com/paper/2206.06965/) (2022)

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

- [Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model](https://mlsanity.com/paper/2302.00244/) (2023)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems](https://mlsanity.com/paper/2310.10603/) (2023)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [MILP-StuDio: MILP Instance Generation via Block Structure Decomposition](https://mlsanity.com/paper/2410.22806/) (2024)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (2024)
- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods](https://mlsanity.com/paper/2406.06954/) (2024)
- [Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation](https://mlsanity.com/paper/2310.14161/) (2023)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2404.12638/) (2024)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [From Large Language Models and Optimization to Decision Optimization CoPilot: A Research Manifesto](https://mlsanity.com/paper/2402.16269/) (2024)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming](https://mlsanity.com/paper/2401.17527/) (2024)
- [Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning](https://mlsanity.com/paper/2310.11845/) (2023)
- [Machine Learning Insides OptVerse AI Solver: Design Principles and Applications](https://mlsanity.com/paper/2401.05960/) (2024)
- [Taking the human out of decomposition-based optimization via artificial intelligence: Part II. Learning to initialize](https://mlsanity.com/paper/2310.07082/) (2023)
- [Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems](https://mlsanity.com/paper/2310.09686/) (2023)
- [Taking the human out of decomposition-based optimization via artificial intelligence: Part I. Learning when to decompose](https://mlsanity.com/paper/2310.07068/) (2023)
- [Code Retrieval for MILP Instance Generation](https://mlsanity.com/paper/2505.11526/) (2025)
- [A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention](https://mlsanity.com/paper/2601.04509/) (2026)
- [FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming](https://mlsanity.com/paper/2507.23390/) (2025)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)
- [Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching](https://mlsanity.com/paper/2604.00094/) (2026)
- [Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2610.14835/) (2026)

## Abstract (arXiv)

The expressive and computationally inexpensive bipartite Graph Neural Networks (GNN) have been shown to be an important component of deep learning based Mixed-Integer Linear Program (MILP) solvers. Recent works have demonstrated the effectiveness of such GNNs in replacing the branching (variable selection) heuristic in branch-and-bound (B&B) solvers. These GNNs are trained, offline and on a collection of MILPs, to imitate a very good but computationally expensive branching heuristic, strong branching. Given that B&B results in a tree of sub-MILPs, we ask (a) whether there are strong dependencies exhibited by the target heuristic among the neighboring nodes of the B&B tree, and (b) if so, whether we can incorporate them in our training procedure. Specifically, we find that with the strong branching heuristic, a child node's best choice was often the parent's second-best choice. We call this the "lookback" phenomenon. Surprisingly, the typical branching GNN of Gasse et al. (2019) often misses this simple "answer". To imitate the target behavior more closely by incorporating the lookback phenomenon in GNNs, we propose two methods: (a) target smoothing for the standard cross-entropy loss function, and (b) adding a Parent-as-Target (PAT) Lookback regularizer term. Finally, we propose a model selection framework to incorporate harder-to-formulate objectives such as solving time in the final models. Through extensive experimentation on standard benchmark instances, we show that our proposal results in up to 22% decrease in the size of the B&B tree and up to 15% improvement in the solving times.