用图神经网络学着近似解决设施选址问题，既快又准还带理论保证。
Learning to Approximate Uniform Facility Location via Graph Neural Networks
- 设计可微分的图网络，融合经典算法思想，无需训练监督
- 实测性能超越传统近似算法，接近整数规划解
- 适合需要快速、可靠且可解释解的优化场景
神经网络，尤其是消息传递神经网络（MPNN），正被广泛用作难解组合优化问题的启发式方法。然而，许多基于学习的方法依赖监督、强化学习或梯度估计器，导致计算成本高、训练不稳定或缺乏理论保证。经典近似算法虽有最坏情况下的保证，但不可微，无法适应自然输入分布中的结构。我们通过均匀设施选址（UniFL）问题研究这一权衡，该问题在聚类、摘要生成、物流和供应链中有广泛应用。我们提出一种完全可微的MPNN，融入近似算法原理，无需求解器监督或离散松弛。该模型具有可证明的近似保证，实验上优于标准近似算法，显著缩小与整数线性规划解的差距。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。