在解决大规模旅行商问题（TSP）时，精确计算的复杂度非常高。研究人员通常采用图稀疏化方法以提高计算效率。传统的稀疏化方法通常依赖于固定的启发式，并未充分利用特定实例的结构信息。本文提出了一种基于学习的图边稀疏化方法（GES），针对欧几里得TSP进行优化。
我们的方法通过结合几何结构信息与组合优化技术，自适应地为不同实例生成稀疏化图，显著减少图的规模，加速求解过程。实验结果表明，我们的稀疏化方法在MATILDA数据集上可以修剪多达95%的边，同时保持解的最优值在1%以内。此外，我们的方法在TSPLIB基准测试中表现出强大的泛化能力。在某些大规模实例中，修剪率超过99%，而最优性差距则保持在1%以下。
博主点评： GES方法通过学习机制实现了针对特定实例的高效稀疏化，这一创新不仅提升了TSP求解的效率，同时也展示了如何将几何与组合优化结合应用在实际问题中，具有广泛的应用前景和理论价值。