On representing (mixed-integer) linear programs by graph neural networks

Speaker: Dr. Jialin Liu

From: UCF Department of Statistics & Data Science

Abstract

This presentation explores the connection between Graph Neural Networks (GNNs) and mathematical optimization. Our recent findings reveal that by defining a Linear Programming (LP) problem on a specific graph, GNNs can assess the feasibility of the LP and solve it to any desired level of precision. To extend this intriguing result to Mixed Integer Linear Programming (MILP), we need to overcome the inherent limitations of GNNs and preprocess the symmetry of a foldable MILP. After this, GNNs can determine the feasibility of the MILP and solve it with any desired precision. These discoveries not only enhance our understanding of GNNs' expressive capabilities but also open new pathways for applying these deep-learning models to both continuous and combinatorial optimization problems.

For more info, please follow this link.