mlsanityData to 7 Oct 2026

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

arXiv 2210.16934 ↗First posted 30 Oct 2022cs.LG cs.AIcited by 30

Not on the map. Why?

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.

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

Builds on

11 of 43 references.

References · 11

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  4. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  5. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  6. 2020Hybrid Models for Learning to Branchcited by 95
  7. 2020Parameterizing Branch-and-Bound Search Trees to Learn Branching Policiescited by 62
  8. 2021Learning to Schedule Heuristics in Branch-and-Boundcited by 45
  9. 2020Reinforcement Learning for Variable Selection in a Branch and Bound Algorithmcited by 28
  10. 2020A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIPcited by 16
  11. 2018Learning to Search via Retrospective Imitationcited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 12; 2025: 6; 2026: 5.

30 papers.

Sort:

By area:

  1. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  2. 2024Towards Foundation Models for Mixed Integer Linear Programmingcited by 30
  3. 2024Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programmingcited by 24
  4. 2024MILP-StuDio: MILP Instance Generation via Block Structure Decompositioncited by 17
  5. 2025Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programmingcited by 16
  6. 2024Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methodscited by 15
  7. 2023Learning to Configure Separators in Branch-and-Cutcited by 14
  8. 2023Promoting Generalization for Exact Solvers via Adversarial Instance Augmentationcited by 12
  9. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  10. 2024Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Processcited by 11
  11. 2024Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programmingcited by 8
  12. 2024Deep Symbolic Optimization for Combinatorial Optimization: Accelerating Node Selection by Discovering Potential Heuristicscited by 8
18 more
  1. 2023Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learningcited by 7
  2. 2025Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Schedulingcited by 7
  3. 2024Multi-task Representation Learning for Mixed Integer Linear Programmingcited by 6
  4. 2024Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learningcited by 5
  5. 2023Reinforcement Learning for Node Selection in Branch-and-Boundcited by 4
  6. 2025Towards graph neural networks for provably solving convex optimization problemscited by 4
  7. 2025RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domainscited by 3
  8. 2025Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programmingcited by 2
  9. 2023Solve Large-scale Unit Commitment Problems by Physics-informed Graph Learningcited by 1
  10. 2024Deep learning enhanced mixed integer optimization: Learning to reduce model dimensionalitycited by 1
  11. 2024RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programscited by 1
  12. 2023Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programscited by 0
  13. 2025A Distance Metric for Mixed Integer Programming Instancescited by 0
  14. 2026Imitation Learning for Combinatorial Optimisation under Uncertaintycited by 0
  15. 2026Designing faster mixed integer linear programming algorithm via learning the optimal pathcited by 0
  16. 2026Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networkscited by 0
  17. 2026Graph-RHO: Critical-path-aware Heterogeneous Graph Network for Long-Horizon Flexible Job-Shop Schedulingcited by 0
  18. 2026Graph Neural Networks with Triangle-Based Messages for the Multicut Problemcited by 0