Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces Projected Consistency Inference (PCI), a novel approach for solving the Traveling Salesman Problem (TSP) that leverages structural constraints to enhance inference efficiency. By replacing traditional gradient-based refinement with structure-aware projections and a lightweight local search, PCI achieves superior optimality gaps of 0.17% and 0.31% for TSP instances with 500 and 1000 cities, respectively, while significantly reducing inference time by 30-40%. The method not only outperforms state-of-the-art techniques like FT2T but also shows improved variance and memory usage, marking a significant advancement in neural combinatorial optimization.
PCI achieves a remarkable reduction in inference time while delivering better optimality gaps than leading methods, reshaping expectations for neural TSP solvers.
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.