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

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

## 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 (most cited first, 26 of 26)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [Learning to Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [Lookback for Learning to Branch](https://mlsanity.com/paper/2206.14987/) (2022)
- [Machine Learning for Cutting Planes in Integer Programming: A Survey](https://mlsanity.com/paper/2302.09166/) (2023)
- [A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs](https://mlsanity.com/paper/1912.08112/) (2019)
- [Learning to Reformulate for Linear Programming](https://mlsanity.com/paper/2201.06216/) (2022)

## Built on by (most cited first, 24 of 24)

- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [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)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Transformers meet Neural Algorithmic Reasoners](https://mlsanity.com/paper/2406.09308/) (2024)
- [Dual Lagrangian Learning for Conic Optimization](https://mlsanity.com/paper/2402.03086/) (2024)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Dual Interior Point Optimization Learning](https://mlsanity.com/paper/2402.02596/) (2024)
- [NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs](https://mlsanity.com/paper/2410.03720/) (2024)
- [Towards graph neural networks for provably solving convex optimization problems](https://mlsanity.com/paper/2502.02446/) (2025)
- [Learning to accelerate distributed ADMM using graph neural networks](https://mlsanity.com/paper/2509.05288/) (2025)
- [Principled Data Augmentation for Learning to Solve Quadratic Programming Problems](https://mlsanity.com/paper/2506.01728/) (2025)
- [Understanding Generalization in Node and Link Prediction](https://mlsanity.com/paper/2507.00927/) (2025)
- [Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization](https://mlsanity.com/paper/2511.09219/) (2025)
- [A Note on Graphon-Signal Analysis of Graph Neural Networks](https://mlsanity.com/paper/2508.18564/) (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)
- [Traffic Engineering in Large-scale Networks with Generalizable Graph Neural Networks](https://mlsanity.com/paper/2503.24203/) (2025)
- [Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs](https://mlsanity.com/paper/2602.10031/) (2026)
- [Learning to Approximate Uniform Facility Location via Graph Neural Networks](https://mlsanity.com/paper/2602.13155/) (2026)
- [Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts](https://mlsanity.com/paper/2605.09382/) (2026)
- [FunL2O: LLM-Guided Feature Function Design for Learning to Optimize](https://mlsanity.com/paper/2607.27389/) (2026)
- [Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming](https://mlsanity.com/paper/2610.01546/) (2026)

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