mlsanityData to 14 Oct 2026

Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems

arXiv 2310.10603 ↗First posted 16 Oct 2023cs.LG cs.AI cs.NEcited by 24

Not on the map. Why?

Abstract (arXiv)

Recently, machine learning, particularly message-passing graph neural networks (MPNNs), has gained traction in enhancing exact optimization algorithms. For example, MPNNs speed up solving mixed-integer optimization problems by imitating computational intensive heuristics like strong branching, which entails solving multiple linear optimization problems (LPs). Despite the empirical success, the reasons behind MPNNs' effectiveness in emulating linear optimization remain largely unclear. Here, we show that MPNNs can simulate standard interior-point methods for LPs, explaining their practical success. Furthermore, we highlight how MPNNs can serve as a lightweight proxy for solving LPs, adapting to a given problem instance distribution. Empirically, we show that MPNNs solve LP relaxations of standard combinatorial optimization problems close to optimality, often surpassing conventional solvers and competing approaches in solving time.

Key facts. Cited by 24 papers in the map (data through 14 Oct 2026). Builds on 26 of its 63 references that are in the map. First posted on arXiv 16 Oct 2023.

Builds on

26 of 63 references.

References · 26

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2018How Powerful are Graph Neural Networks?cited by 4,393
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  7. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  8. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  9. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 754
  10. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  11. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  12. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
14 more
  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  2. 2020DeeperGCN: All You Need to Train Deeper GCNscited by 250
  3. 2020Solving Mixed Integer Programs Using Neural Networkscited by 182
  4. 2021End-to-End Constrained Optimization Learning: A Surveycited by 157
  5. 2019Neural Execution of Graph Algorithmscited by 121
  6. 2020Hybrid Models for Learning to Branchcited by 95
  7. 2020Parameterizing Branch-and-Bound Search Trees to Learn Branching Policiescited by 63
  8. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 49
  9. 2021Learning to Schedule Heuristics in Branch-and-Boundcited by 46
  10. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  11. 2022Lookback for Learning to Branchcited by 27
  12. 2023Machine Learning for Cutting Planes in Integer Programming: A Surveycited by 20
  13. 2019A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programscited by 13
  14. 2022Learning to Reformulate for Linear Programmingcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 9; 2025: 8; 2026: 7.

24 papers.

Sort:

By area:

  1. 2024Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programmingcited by 24
  2. 2024PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programmingcited by 17
  3. 2024Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programscited by 16
  4. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  5. 2024Transformers meet Neural Algorithmic Reasonerscited by 13
  6. 2024Dual Lagrangian Learning for Conic Optimizationcited by 11
  7. 2024Future Directions in the Theory of Graph Machine Learningcited by 6
  8. 2024Dual Interior Point Optimization Learningcited by 4
  9. 2024NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPscited by 4
  10. 2025Towards graph neural networks for provably solving convex optimization problemscited by 4
  11. 2025Learning to accelerate distributed ADMM using graph neural networkscited by 3
  12. 2025Principled Data Augmentation for Learning to Solve Quadratic Programming Problemscited by 2
12 more
  1. 2025Understanding Generalization in Node and Link Predictioncited by 2
  2. 2025Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimizationcited by 2
  3. 2025A Note on Graphon-Signal Analysis of Graph Neural Networkscited by 1
  4. 2025Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Realitycited by 1
  5. 2026On the Expressive Power of GNNs to Solve Linear SDPscited by 1
  6. 2026Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networkscited by 1
  7. 2025Traffic Engineering in Large-scale Networks with Generalizable Graph Neural Networkscited by 0
  8. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0
  9. 2026Learning to Approximate Uniform Facility Location via Graph Neural Networkscited by 0
  10. 2026Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Startscited by 0
  11. 2026FunL2O: LLM-Guided Feature Function Design for Learning to Optimizecited by 0
  12. 2026Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programmingcited by 0