Graph-Constrained Diffusion with Progressive Distillation for Traveling Salesman Problem

Abstract

Diffusion models have shown strong promise for neural combinatorial optimization, yet existing approaches define the forward noising process over a fully connected graph, discarding the sparse topological structure inherent to the Traveling Salesman Problem (TSP), and their multi-step inference incurs prohibitive latency. We address these two limitations through a pair of complementary models. First, we propose GCDTSP, a graph-constrained diffusion model that replaces the topology-agnostic uniform transition matrix with an instance-dependent graph Laplacian-based heat-kernel transition matrix, so that the evolution of the edge-valued state is governed by the topology of each TSP instance; a feasibility constraint loss combining degree conservation, symmetry, and locality priors further guides the GatedGCN denoising network toward valid Hamiltonian cycles. GCDTSP outperforms autoregressive baselines and prior diffusion solvers under greedy decoding, and generalizes zero-shot to real-world TSPLIB instances. Building upon GCDTSP, we introduce GCDTSP-D, a progressive distillation framework that iteratively halves the required denoising steps via teacher–student parameter inheritance, combined with a cosine noise schedule that concentrates inference capacity in the constraint-sensitive low-noise regime. GCDTSP-D attains an approximately 37× speedup on TSP50 with a favorable quality–speed trade-off, and on the larger TSP500 benchmark even surpasses its teacher in both solution quality and speed.