​​Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems

guest post by Chendi Qian, Didier Chételat, Christopher Morris

📜 Paper: arxiv (accepted to AISTATS 2024)

🛠️ Code: https://github.com/chendiqian/IPM_MPNN

Recent research shows growing interest in training message-passing graph neural networks (MPNNs) to mimic classical algorithms, particularly for solving linear optimization problems (LPs). For example, in integer linear optimization, state-of-the-art solvers rely on the branch-and-bound algorithm, in which one must repeatedly select variables, subdividing the search space. The best-known heuristic for variable selection is known as strong branching which entails solving LPs to score the variables. This heuristic is too computationally expensive to use in practice. However, in recent years, a collection of works, e.g., Gasse et al. (2019), have proposed using MPNNs to imitate strong branching with impressive success. However, it remained to be seen why such approaches work.

Hence, our paper explores the intriguing possibility of MPNNs approximating general LPs by interpreting various interior-point methods (IPMs) as MPNNs with specific architectures and parameters. We prove that standard MPNN steps can emulate a single iteration of the IPM algorithm on the LP’s tripartite graph representation. This theoretical insight suggests that MPNNs may succeed in LP solving by effectively imitating IPMs.

Despite our theoretical model, our empirical results indicate that MPNNs with fewer layers can approximate the output of practical IPMs for LP solving. Empirically, our approach reduces solving times compared to a state-of-the-art LP solver and other neural network-based methods. Our study enhances the theoretical understanding of data-driven optimization using MPNNs and highlights the potential of MPNNs as efficient proxies for solving LPs.