mlsanityData to 14 Oct 2026

On Representing Mixed-Integer Linear Programs by Graph Neural Networks

arXiv 2210.10759 ↗First posted 19 Oct 2022cs.LG math.OCcited by 23

Not on the map. Why?

Abstract (arXiv)

While Mixed-integer linear programming (MILP) is NP-hard in general, practical MILP has received roughly 100--fold speedup in the past twenty years. Still, many classes of MILPs quickly become unsolvable as their sizes increase, motivating researchers to seek new acceleration techniques for MILPs. With deep learning, they have obtained strong empirical results, and many results were obtained by applying graph neural networks (GNNs) to making decisions in various stages of MILP solution processes. This work discovers a fundamental limitation: there exist feasible and infeasible MILPs that all GNNs will, however, treat equally, indicating GNN's lacking power to express general MILPs. Then, we show that, by restricting the MILPs to unfoldable ones or by adding random features, there exist GNNs that can reliably predict MILP feasibility, optimal objective values, and optimal solutions up to prescribed precision. We conducted small-scale numerical experiments to validate our theoretical findings.

Key facts. Cited by 23 papers in the map (data through 14 Oct 2026). Builds on 25 of its 46 references that are in the map. First posted on arXiv 19 Oct 2022.

Builds on

25 of 46 references.

References · 25

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  4. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  5. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  6. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  7. 2020Random Features Strengthen Graph Neural Networkscited by 186
  8. 2020Solving Mixed Integer Programs Using Neural Networkscited by 182
  9. 2019Reinforcement Learning for Integer Programming: Learning to Cutcited by 111
  10. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  11. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  12. 2020Hybrid Models for Learning to Branchcited by 95
13 more
  1. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 69
  2. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 64
  3. 2020Parameterizing Branch-and-Bound Search Trees to Learn Branching Policiescited by 63
  4. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 61
  5. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 49
  6. 2021Learning to Select Cuts for Efficient Mixed-Integer Programmingcited by 48
  7. 2022Learning to branch with Tree MDPscited by 45
  8. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  9. 2022Lookback for Learning to Branchcited by 27
  10. 2015Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinementcited by 16
  11. 2021Learning Primal Heuristics for Mixed Integer Programscited by 14
  12. 2022An Improved Reinforcement Learning Algorithm for Learning to Branchcited by 14
  13. 2022Learning to Use Local Cutscited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 6; 2025: 10; 2026: 4.

23 papers.

Sort:

By area:

  1. 2024Towards Foundation Models for Mixed Integer Linear Programmingcited by 31
  2. 2023A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availabilitycited by 21
  3. 2023Neural incomplete factorization: learning preconditioners for the conjugate gradient methodcited by 18
  4. 2024Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programscited by 16
  5. 2025Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programmingcited by 16
  6. 2023Promoting Generalization for Exact Solvers via Adversarial Instance Augmentationcited by 12
  7. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  8. 2025EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulationscited by 9
  9. 2024NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPscited by 4
  10. 2025When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approachcited by 3
  11. 2024Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networkscited by 2
  12. 2025Principled Data Augmentation for Learning to Solve Quadratic Programming Problemscited by 2
11 more
  1. 2025Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programmingcited by 2
  2. 2025FORGE: Foundational Optimization Representations from Graph Embeddingscited by 2
  3. 2025HGCN2SP: Hierarchical Graph Convolutional Network for Two-Stage Stochastic Programmingcited by 2
  4. 2024Deep Reinforcement Learning for Traveling Purchaser Problemscited by 1
  5. 2025MILP-SAT-GNN: Yet Another Neural SAT Solvercited by 1
  6. 2025Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Realitycited by 1
  7. 2026A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attentioncited by 1
  8. 2026On the Expressive Power of GNNs to Solve Linear SDPscited by 1
  9. 2026Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networkscited by 1
  10. 2025Feature Augmentation of GNNs for ILPs: Local Uniqueness Sufficescited by 0
  11. 2026A Weisfeiler-Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programscited by 0