Analysis and Solution of LP and MILP Using Graph Neural Networks

This presentation focuses on the connection between GNNs (Graph Neural Networks) and mathematical optimization. We have recently found that, by defining an LP (Linear Programming) on a specific graph, GNNs can determine the feasibility of the LP problem and solve it with any desired precision. To extend this surprising result to MILP (Mixed Integer Linear Programming), we have to address the limitations of GNNs and preprocess the symmetry of a foldable MILP, after which GNNs can determine the feasibility of the MILP problem and solve it with any desired precision. These findings not only deepen our understanding of the expressive power of GNNs but also pave new avenues for the application of these deep learning models in addressing continuous and combinatorial optimization problems. In addition, by treating a certain first-order algorithm as a GNN, we obtain an upper bound on the size of GNN for LP.