用结构约束替代梯度优化，让神经TSP求解更快更准
Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers
- 用结构感知投影替代梯度精修，直接生成合法路径
- 500城和1000城TSP平均最优率差距分别仅0.17%和0.31%
- 比现有方法快30%~40%，适合快速生成高质量解的场景
神经组合优化近年在欧几里得旅行商问题（TSP）上取得显著进展，采用扩散模型与一致性模型等生成式方法。当前最先进方法FT2T结合快速一致性预测与梯度推理精修，但梯度搜索计算开销大，且与可行解离散结构不一致。本文提出投影一致性推断（PCI），一种无需重训练的即插即用方案：从一致性模型输出中解码出合法哈密顿回路，并应用轻量级局部搜索（如2-opt）。在500城和1000城TSP上，PCI平均最优率差距（OG）分别为0.17%和0.31%，优于FT2T最佳设置（0.22%和0.36%），推理时间降低30%~40%。同时，PCI方差更低、内存占用更少，且能在快速生成中超越经典启发式算法LKH3。结果表明，结构感知的推理操作为神经TSP求解器提供了实用而合理的路径，可补充训练目标。
原文摘要 · Abstract (English)
Neural combinatorial optimization has recently achieved strong results on the Euclidean Traveling Salesman Problem (TSP) using generative models such as diffusion and consistency models. State-ofthe-art approaches like FT2T combine fast consistency-based prediction with gradient-based inference time refinement. However, gradient search often incurs significant computational overhead and may not align with the discrete structure of feasible solutions. We introduce Projected Consistency Inference (PCI), a plug-and-play, retraining-free alternative that replaces gradient refinement with structure-aware projections: PCI decodes valid Hamiltonian tours from the consistency model output and applies a lightweight local search (e.g., 2-opt). PCI achieves an average optimality gap (OG) of 0.17% on TSP with 500 cities, and 0.31% on TSP with 1000 cities, outperforming FT2T best settings (OG 0.22% and 0.36%, respectively) while reducing the inference time up to 30 to 40%. PCI also exhibits lower variance and memory usage, and can surpass classical heuristics such as LKH3 in rapid solution generation. Our results demonstrate that structure-aware inference time operations provide a practical and principled path for neural TSP solvers, complementing training time objectives.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。