Transport, Don't Generate: Deterministic Geometric Flows for Combinatorial Optimization
This addresses the quadratic bottleneck in solving Euclidean Traveling Salesman Problems for researchers and practitioners in combinatorial optimization.
The paper tackles the computational inefficiency of diffusion models for Neural Combinatorial Optimization by proposing CycFlow, a deterministic transport-based framework that accelerates solving speed by up to three orders of magnitude while maintaining competitive optimality gaps.
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.