mlsanityData to 7 Oct 2026

Exact Combinatorial Optimization with Graph Convolutional Neural Networks

arXiv 1906.01629 ↗First posted 4 Jun 2019cs.LG math.OC stat.MLcited by 313

Not on the map. Why?

Abstract (arXiv)

Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose a new graph convolutional neural network model for learning branch-and-bound variable selection policies, which leverages the natural variable-constraint bipartite graph representation of mixed-integer linear programs. We train our model via imitation learning from the strong branching expert rule, and demonstrate on a series of hard problems that our approach produces policies that improve upon state-of-the-art machine-learning methods for branching and generalize to instances significantly larger than seen during training. Moreover, we improve for the first time over expert-designed branching rules implemented in a state-of-the-art solver on large problems. Code for reproducing all the experiments can be found at https://github.com/ds4dm/learn2branch.

Key facts. Cited by 313 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 37; 2022: 59; 2023: 49; 2024: 55; 2025: 62; 2026: 51.

313 papers.

Sort:

By area:

  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  2. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  3. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  4. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
  5. 2021The Transformer Network for the Traveling Salesman Problemcited by 59
  6. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 58
  7. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  8. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 55
  9. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  10. 2021Learning to Select Cuts for Efficient Mixed-Integer Programmingcited by 48
  11. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 48
  12. 2021Learning to Schedule Heuristics in Branch-and-Boundcited by 45
38 more
  1. 2022Learning to branch with Tree MDPscited by 45
  2. 2022A Survey for Solving Mixed Integer Programming via Machine Learningcited by 44
  3. 2023Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Modelcited by 44
  4. 2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 42
  5. 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 41
  6. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  7. 2022The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insightscited by 39
  8. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  9. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  10. 2022SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networkscited by 36
  11. 2021Learning Large Neighborhood Search Policy for Integer Programmingcited by 35
  12. 2024Diffusion Models as Constrained Samplers for Optimization with Unknown Constraintscited by 33
  13. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  14. 2022Learning to Compare Nodes in Branch and Bound with Graph Neural Networkscited by 30
  15. 2024Towards Foundation Models for Mixed Integer Linear Programmingcited by 30
  16. 2025CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimizationcited by 28
  17. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  18. 2021A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphscited by 26
  19. 2022Lookback for Learning to Branchcited by 26
  20. 2022Adaptive Cut Selection in Mixed-Integer Linear Programmingcited by 25
  21. 2023Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problemscited by 24
  22. 2024Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programmingcited by 24
  23. 2022On Representing Mixed-Integer Linear Programs by Graph Neural Networkscited by 23
  24. 2022Augment with Care: Contrastive Learning for Combinatorial Problemscited by 22
  25. 2022A Deep Reinforcement Learning Framework For Column Generationcited by 21
  26. 2023A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availabilitycited by 21
  27. 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
  28. 2022Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectoriescited by 19
  29. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 19
  30. 2023Machine Learning for Cutting Planes in Integer Programming: A Surveycited by 19
  31. 2024A Survey of Optimization-based Task and Motion Planning: From Classical To Learning Approachescited by 19
  32. 2021Deep Graph Matching under Quadratic Constraintcited by 18
  33. 2021Towards Efficient Graph Convolutional Networks for Point Cloud Handlingcited by 18
  34. 2021Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networkscited by 18
  35. 2022Learning to Control Local Search for Combinatorial Optimizationcited by 18
  36. 2023Machine Learning for Large-Scale Optimization in 6G Wireless Networkscited by 18
  37. 2025Pareto Set Learning for Multi-Objective Reinforcement Learningcited by 18
  38. 2022Affinity-Aware Graph Networkscited by 17

50 most cited of 313 All 313 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2020Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
  2. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
  3. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
  4. 2025Learning Branching Policies for MILPs with Proximal Policy Optimization
  5. 2019Learning chordal extensions
  6. 2026Which Algorithms Can Graph Neural Networks Learn?
  7. 2026Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization
  8. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization