用确定性点迁移替代随机生成，极速求解旅行商问题
Transport, Don't Generate: Deterministic Geometric Flows for Combinatorial Optimization
- 用向量场直接移动坐标点至圆形排列，跳过逐边去噪
- 求解速度比顶尖扩散模型快3个数量级，最优性差距相当
- 适合追求高速求解的组合优化场景，尤其适合大尺度实例
神经组合优化近年多依赖扩散模型，将欧式旅行商问题（TSP）视为生成 $N \times N$ 热图的随机任务。本文提出CycFlow框架，以确定性点迁移取代迭代边去噪。该方法学习一个与实例相关的向量场，将输入的二维坐标连续运输至标准圆排列，再通过角度排序从 $2N$ 维表示中恢复最优路径。借助数据相关流匹配，避免了边评分带来的二次复杂度瓶颈，转而采用线性坐标动态。相比当前最优扩散基线，求解速度提升高达三个数量级，同时保持竞争力的最优性差距。
原文摘要 · Abstract (English)
Recent advances in Neural Combinatorial Optimization (NCO) have been dominated by diffusion models that treat the Euclidean Traveling Salesman Problem (TSP) as a stochastic $N \times N$ heatmap generation task. In this paper, we propose CycFlow, a framework that replaces iterative edge denoising with deterministic point transport. CycFlow learns an instance-conditioned vector field that continuously transports input 2D coordinates to a canonical circular arrangement, where the optimal tour is recovered from this $2N$ dimensional representation via angular sorting. By leveraging data-dependent flow matching, we bypass the quadratic bottleneck of edge scoring in favor of linear coordinate dynamics. This paradigm shift accelerates solving speed by up to three orders of magnitude compared to state-of-the-art diffusion baselines, while maintaining competitive optimality gaps.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。