On Representing Linear Programs by Graph Neural Networks

2022/09/25 by Ziang Chen, Jialin Liu, Chen, Ziang +7 · 8 citations
Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and ELM #Neural Networks and Applications #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2209.12288

openalex publication_date 2022/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality
• ORGEval: Graph-Theoretic Evaluation of LLMs in Optimization Modeling
• Enforcing convex constraints in Graph Neural Networks
• Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices
• Unrolled Graph Neural Networks for Constrained Optimization
• HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs
• FORGE: Foundational Optimization Representations from Graph Embeddings
• Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming

Related

• Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems
• On Representing Mixed-Integer Linear Programs by Graph Neural Networks
• Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs
• A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming
• Optimizing over trained GNNs via symmetry breaking