This research investigates the success of message-passing graph neural networks (MPNNs) in solving linear optimization problems. The authors demonstrate that MPNNs can mimic standard interior-point methods for these problems, which explains their practical success. They also show that MPNNs can act as a lightweight proxy for solving linear optimization problems, adapting to the distribution of a given problem instance. Empirical evidence suggests that MPNNs solve LP relaxations of standard combinatorial optimization problems close to optimality, often outperforming traditional solvers and competing approaches in terms of solving time.
Publication date: 17 Oct 2023
Project Page: Not provided
Paper: https://arxiv.org/pdf/2310.10603
