Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers
2026-06-08 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors propose a new method called Projected Consistency Inference (PCI) to improve solving the Traveling Salesman Problem using neural networks. Instead of using slow gradient-based techniques to refine solutions, PCI uses a smart projection step that ensures valid routes and applies a simple local improvement method. This approach is faster, uses less memory, and produces slightly better or comparable results than previous leading methods, even beating some classical heuristics in quick solution quality. Their work shows that incorporating the problem's structure during inference can help neural solvers work better without extra training.
Traveling Salesman ProblemNeural Combinatorial OptimizationConsistency ModelsGradient-based InferenceProjected Consistency Inference2-opt Local SearchHamiltonian ToursOptimality GapInference Time OptimizationClassical Heuristics
Authors
Mickaël Basson, Philippe Preux
Abstract
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.