# On Representing Linear Programs by Graph Neural Networks

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

## Key facts

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

## Builds on (most cited first, 30 of 36)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [DeepOPF: A Deep Neural Network Approach for Security-Constrained DC Optimal Power Flow](https://mlsanity.com/paper/1910.14448/) (2019)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time](https://mlsanity.com/paper/2006.03750/) (2020)
- [Learning for DC-OPF: Classifying active sets using neural nets](https://mlsanity.com/paper/1902.05607/) (2019)
- [Lookback for Learning to Branch](https://mlsanity.com/paper/2206.14987/) (2022)

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

- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems](https://mlsanity.com/paper/2310.10603/) (2023)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [Neural incomplete factorization: learning preconditioners for the conjugate gradient method](https://mlsanity.com/paper/2305.16368/) (2023)
- [PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2406.01908/) (2024)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (2024)
- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [ORGEval: Graph-Theoretic Evaluation of LLMs in Optimization Modeling](https://mlsanity.com/paper/2510.27610/) (2025)
- [EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulations](https://mlsanity.com/paper/2502.14760/) (2025)
- [Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guarantees](https://mlsanity.com/paper/2410.11061/) (2024)
- [Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning](https://mlsanity.com/paper/2310.11845/) (2023)
- [DIG-MILP: a Deep Instance Generator for Mixed-Integer Linear Programming with Feasibility Guarantee](https://mlsanity.com/paper/2310.13261/) (2023)
- [Machine Learning Insides OptVerse AI Solver: Design Principles and Applications](https://mlsanity.com/paper/2401.05960/) (2024)
- [Towards graph neural networks for provably solving convex optimization problems](https://mlsanity.com/paper/2502.02446/) (2025)
- [An Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrolling](https://mlsanity.com/paper/2412.01051/) (2024)
- [Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks](https://mlsanity.com/paper/2310.07979/) (2023)
- [Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks](https://mlsanity.com/paper/2409.04495/) (2024)
- [Principled Data Augmentation for Learning to Solve Quadratic Programming Problems](https://mlsanity.com/paper/2506.01728/) (2025)
- [Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming](https://mlsanity.com/paper/2508.18742/) (2025)
- [FORGE: Foundational Optimization Representations from Graph Embeddings](https://mlsanity.com/paper/2508.20330/) (2025)
- [Enforcing convex constraints in Graph Neural Networks](https://mlsanity.com/paper/2510.11227/) (2025)
- [Network Interdiction Goes Neural](https://mlsanity.com/paper/2405.16409/) (2024)
- [Surrogate Interpretable Graph for Random Decision Forests](https://mlsanity.com/paper/2506.01988/) (2025)
- [Unrolled Graph Neural Networks for Constrained Optimization](https://mlsanity.com/paper/2509.17156/) (2025)
- [Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality](https://mlsanity.com/paper/2512.09355/) (2025)
- [On the Expressive Power of GNNs to Solve Linear SDPs](https://mlsanity.com/paper/2604.27786/) (2026)
- [Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks](https://mlsanity.com/paper/2605.07113/) (2026)

## 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.