# Learning to Compare Nodes in Branch and Bound with Graph Neural Networks

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 43 references that are in the map.
- First posted on arXiv 30 Oct 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [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)
- [Learning to Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)
- [A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP](https://mlsanity.com/paper/2007.03948/) (2020)
- [Learning to Search via Retrospective Imitation](https://mlsanity.com/paper/1804.00846/) (2018)

## Built on by (most cited first, 30 of 31)

- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Towards Foundation Models for Mixed Integer Linear Programming](https://mlsanity.com/paper/2410.08288/) (2024)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [MILP-StuDio: MILP Instance Generation via Block Structure Decomposition](https://mlsanity.com/paper/2410.22806/) (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)
- [Learning to Configure Separators in Branch-and-Cut](https://mlsanity.com/paper/2311.05650/) (2023)
- [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)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming](https://mlsanity.com/paper/2401.17527/) (2024)
- [Deep Symbolic Optimization for Combinatorial Optimization: Accelerating Node Selection by Discovering Potential Heuristics](https://mlsanity.com/paper/2406.09740/) (2024)
- [Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning](https://mlsanity.com/paper/2310.11845/) (2023)
- [Multi-task Representation Learning for Mixed Integer Linear Programming](https://mlsanity.com/paper/2412.14409/) (2024)
- [Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling](https://mlsanity.com/paper/2502.15791/) (2025)
- [Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2401.10467/) (2024)
- [Reinforcement Learning for Node Selection in Branch-and-Bound](https://mlsanity.com/paper/2310.00112/) (2023)
- [Towards graph neural networks for provably solving convex optimization problems](https://mlsanity.com/paper/2502.02446/) (2025)
- [RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains](https://mlsanity.com/paper/2511.02331/) (2025)
- [Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming](https://mlsanity.com/paper/2503.15847/) (2025)
- [Solve Large-scale Unit Commitment Problems by Physics-informed Graph Learning](https://mlsanity.com/paper/2311.15216/) (2023)
- [Deep learning enhanced mixed integer optimization: Learning to reduce model dimensionality](https://mlsanity.com/paper/2401.09556/) (2024)
- [RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs](https://mlsanity.com/paper/2411.19517/) (2024)
- [Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs](https://mlsanity.com/paper/2310.14659/) (2023)
- [A Distance Metric for Mixed Integer Programming Instances](https://mlsanity.com/paper/2507.11063/) (2025)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)
- [Designing faster mixed integer linear programming algorithm via learning the optimal path](https://mlsanity.com/paper/2601.16056/) (2026)
- [Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks](https://mlsanity.com/paper/2603.19318/) (2026)
- [Graph-RHO: Critical-path-aware Heterogeneous Graph Network for Long-Horizon Flexible Job-Shop Scheduling](https://mlsanity.com/paper/2604.10073/) (2026)
- [Graph Neural Networks with Triangle-Based Messages for the Multicut Problem](https://mlsanity.com/paper/2605.13673/) (2026)

## Abstract (arXiv)

Branch-and-bound approaches in integer programming require ordering portions of the space to explore next, a problem known as node comparison. We propose a new siamese graph neural network model to tackle this problem, where the nodes are represented as bipartite graphs with attributes. Similar to prior work, we train our model to imitate a diving oracle that plunges towards the optimal solution. We evaluate our method by solving the instances in a plain framework where the nodes are explored according to their rank. On three NP-hard benchmarks chosen to be particularly primal-difficult, our approach leads to faster solving and smaller branch- and-bound trees than the default ranking function of the open-source solver SCIP, as well as competing machine learning methods. Moreover, these results generalize to instances larger than used for training. Code for reproducing the experiments can be found at https://github.com/ds4dm/learn2comparenodes.