GES-TSP：TSP 的图边稀疏化

arXiv:2607.09708v1 公告类型：新 摘要：精确解决旅行商问题（TSP）的大规模实例在计算上是昂贵的。研究人员经常采用图稀疏化方法来提高计算效率。传统的稀疏化方法通常依赖于固定的启发式方法，无法充分利用特定于实例的结构信息。在本文中，我们提出了图边缘稀疏化（GES），这是一种基于学习的欧几里德 TSP 稀疏化方法。通过结合几何结构信息和组合优化技术，我们提出的方法自适应地生成不同实例的稀疏图，显着减小图的大小并加速求解过程。实验结果表明，我们的稀疏化方法可以修剪 MATILDA 数据集上高达 95% 的边缘，同时将解差距保持在最佳值的 1% 以内。此外，我们的方法在 TSPLIB 基准上表现出很强的泛化能力。在一些大规模实例中，剪枝率超过 99%，而最优性差距保持在 1% 以下。