mlsanityData to 7 Oct 2026

On Representing Linear Programs by Graph Neural Networks

arXiv 2209.12288 ↗First posted 25 Sep 2022cs.LG math.OCcited by 39

Not on the map. Why?

Abstract (arXiv)

Learning to optimize is a rapidly growing area that aims to solve optimization problems or improve existing optimization algorithms using machine learning (ML). In particular, the graph neural network (GNN) is considered a suitable ML model for optimization problems whose variables and constraints are permutation--invariant, for example, the linear program (LP). While the literature has reported encouraging numerical results, this paper establishes the theoretical foundation of applying GNNs to solving LPs. Given any size limit of LPs, we construct a GNN that maps different LPs to different outputs. We show that properly built GNNs can reliably predict feasibility, boundedness, and an optimal solution for each LP in a broad class. Our proofs are based upon the recently--discovered connections between the Weisfeiler--Lehman isomorphism test and the GNN. To validate our results, we train a simple GNN and present its accuracy in mapping LPs to their feasibilities and solutions.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). Builds on 36 of its 57 references that are in the map. First posted on arXiv 25 Sep 2022.

Builds on

36 of 57 references.

References · 36

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  4. 2018Attention, Learn to Solve Routing Problems!cited by 646
  5. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  6. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  7. 2019Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processingcited by 411
  8. 2019Provably Powerful Graph Networkscited by 385
  9. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  10. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  11. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  12. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
24 more
  1. 2021Learning to Optimize: A Primer and A Benchmarkcited by 206
  2. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  3. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  4. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  5. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  6. 2019On the Universality of Invariant Networkscited by 151
  7. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  8. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  9. 2020Hybrid Models for Learning to Branchcited by 95
  10. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  11. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 63
  12. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  13. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 58
  14. 2019DeepOPF: A Deep Neural Network Approach for Security-Constrained DC Optimal Power Flowcited by 50
  15. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 48
  16. 2020Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Timecited by 39
  17. 2019Learning for DC-OPF: Classifying active sets using neural netscited by 30
  18. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  19. 2022Lookback for Learning to Branchcited by 26
  20. 2015Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinementcited by 16
  21. 2021Learning Primal Heuristics for Mixed Integer Programscited by 14
  22. 2022An Improved Reinforcement Learning Algorithm for Learning to Branchcited by 14
  23. 2022Learning to Reformulate for Linear Programmingcited by 10
  24. 2019Solving L1-regularized SVMs and related linear programs: Revisiting the effectiveness of Column and Constraint Generationcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 7; 2024: 10; 2025: 14; 2026: 7.

39 papers.

Sort:

  1. 2024Position: Graph Foundation Models are Already Herecited by 84
  2. 2023Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problemscited by 24
  3. 2024Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programmingcited by 24
  4. 2022On Representing Mixed-Integer Linear Programs by Graph Neural Networkscited by 23
  5. 2023Neural incomplete factorization: learning preconditioners for the conjugate gradient methodcited by 18
  6. 2024Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programscited by 16
  7. 2025Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programmingcited by 16
  8. 2024PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programmingcited by 14
  9. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  10. 2023Are Graph Neural Networks Optimal Approximation Algorithms?cited by 10
  11. 2025EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulationscited by 9
  12. 2024Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guaranteescited by 8
27 more
  1. 2023Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learningcited by 7
  2. 2023DIG-MILP: a Deep Instance Generator for Mixed-Integer Linear Programming with Feasibility Guaranteecited by 7
  3. 2024Machine Learning Insides OptVerse AI Solver: Design Principles and Applicationscited by 7
  4. 2025ORGEval: Graph-Theoretic Evaluation of LLMs in Optimization Modelingcited by 7
  5. 2025Towards graph neural networks for provably solving convex optimization problemscited by 4
  6. 2023Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networkscited by 2
  7. 2024Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networkscited by 2
  8. 2024An Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrollingcited by 2
  9. 2025Principled Data Augmentation for Learning to Solve Quadratic Programming Problemscited by 2
  10. 2025Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programmingcited by 2
  11. 2025FORGE: Foundational Optimization Representations from Graph Embeddingscited by 2
  12. 2025Enforcing convex constraints in Graph Neural Networkscited by 2
  13. 2024Network Interdiction Goes Neuralcited by 1
  14. 2025Surrogate Interpretable Graph for Random Decision Forestscited by 1
  15. 2025Unrolled Graph Neural Networks for Constrained Optimizationcited by 1
  16. 2025Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Realitycited by 1
  17. 2026On the Expressive Power of GNNs to Solve Linear SDPscited by 1
  18. 2023On the Equivalence of Graph Convolution and Mixupcited by 0
  19. 2025Traffic Engineering in Large-scale Networks with Generalizable Graph Neural Networkscited by 0
  20. 2025HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programscited by 0
  21. 2025Feature Augmentation of GNNs for ILPs: Local Uniqueness Sufficescited by 0
  22. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0
  23. 2026Learning to Approximate Uniform Facility Location via Graph Neural Networkscited by 0
  24. 2026Covariance-Aware Transformers for Quadratic Programming and Decision Makingcited by 0
  25. 2026Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networkscited by 0
  26. 2026Bifurcation Models: Learning Set-Valued Solution Maps with Weight-Tied Dynamicscited by 0
  27. 2026Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Startscited by 0