用学习方法动态剪枝图边，大幅加速大规模旅行商问题求解。
GES-TSP: Graph Edge Sparsification for TSP
- 基于几何结构与组合优化，自适应生成稀疏图
- 在MATILDA上剪掉95%边，解差距小于1%
- 通用性强，大实例剪枝率超99%，保优
求解大规模旅行商问题（TSP）的精确解计算成本高昂。现有图稀疏化方法多依赖固定启发式规则，未能充分利用实例特异性结构信息。本文提出基于学习的图边稀疏化方法GES，专用于欧氏空间下的TSP。通过融合几何结构信息与组合优化技术，该方法能为不同实例自适应生成稀疏图，显著压缩图规模并加快求解速度。实验表明，在MATILDA数据集上，本方法可剪除高达95%的边，且解与最优值的差距保持在1%以内。此外，该方法在TSPLIB基准测试中展现出强泛化能力：部分大规模实例中剪枝率超过99%，而最优性间隙仍低于1%。
原文摘要 · Abstract (English)
Solving large-scale instances of the Traveling Salesman Problem (TSP) exactly is computationally expensive. Researchers often employ graph sparsification methods to improve computational efficiency. Traditional sparsification methods typically rely on fixed heuristics and fail to fully exploit instance-specific structural information. In this paper, we propose Graph Edge Sparsification (GES), a learning-based sparsification approach for Euclidean TSP. By incorporating geometric structural information and combinatorial optimization technology, our proposed method adaptively generates a sparsification graph for different instances, significantly reducing the graph size and accelerating the solving process. Experimental results demonstrate that our sparsification method can prune up to 95% of edges on the MATILDA dataset, while keeping the solution gap within 1% of the optimal value. Moreover, our approach exhibits strong generalization capability on the TSPLIB benchmark.In some large-scale instances, the pruning rate exceeds 99%, while the optimality gap remains below 1%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。