Learning to Approximate Uniform Facility Location via Graph Neural Networks

Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming.

Many real-world tasks, such as choosing warehouse locations, clustering data, designing supply chains, or summarizing large datasets, can be modeled as facility location problems. These problems ask where to open a limited set of “facilities” so that all clients can be served at low total cost, but finding the best solution is computationally difficult. Classical approximation algorithms are reliable because they come with worst-case guarantees, but they are often conservative and cannot adapt to patterns in real data. Neural networks can adapt to data, but they are often hard to train for discrete optimization problems and usually lack guarantees. This paper studies the uniform facility location problem and proposes a graph neural network that combines the strengths of both approaches. The model is fully differentiable and can be trained without optimal solutions, while its design mirrors classical approximation algorithms. Theoretically, the paper proves that the model can retain approximation guarantees and generalize to larger problem instances. Empirically, the learned model improves over classical approximation baselines, performs close to exact integer-programming solvers on synthetic data, and scales to much larger real-world city graphs. Overall, this work shows how classical algorithmic ideas can guide the design of trainable neural solvers that are both practical and theoretically grounded.