Exploring the Potential of Graph Neural Networks-based Methods for General Linear Programs

Linear Programming (LP) and Integer Programming (IP) problems have been pivotal in optimization processes, finding applications across diverse industries like resource management, finance, and logistics. It is also used for internet network traffic optimization. Traditionally, LP solvers have consistently provided optimal solutions for problems formulated linearly. However, with more data and larger problems to solve, these LP solvers become computationally heavy and time-consuming. One solution is to provide better close-to-optimal initial solutions for these solvers, which previously many heuristics have attempted. Recently, researchers have successfully trained Graph Neural Networks to infer close-to-optimal initial solutions as a quick start for specific LP/IP problem types. Instead, this paper explores the potential of GNN models to predict close-to-optimal initial solutions for diverse problems. Specifically, the Smart Initial Basis (SIB), Learn To Pivot (LTP), and Interior-Point Message-passing GNN (IPMGNN) were investigated. Furthermore, an interactive website was developed releasing these models for readers to experiment with. A video demonstration can be accessed https://www.youtube.com/watch?v=7hCr92SnNak&ab_channel=boomer2boom, the repository for the website is open-sourced https://github.com/boomer3boom/Exploring-the-Potential-of-Graph-Neural-Networks-based-Methods-for-General-Linear-Program-Website-, and the model learning code is open-sourced https://github.com/boomer3boom/Exploring-the-Potential-of-Graph-Neural-Networks-based-Methods-for-General-Linear-Program.