On Representing Linear Programs by Graph Neural Networks

Understand

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.