New Learning Method Improves Traveling Salesman Problem Solutions

Current learning-based approaches for the Traveling Salesman Problem (TSP) often rely on surrogate representations, leaving much of the critical Hamiltonian structure to be resolved during the final decoding stage. This paper addresses that by proposing C2TSP, a novel unsupervised learning pipeline designed to directly learn a structurally meaningful latent object. C2TSP is built upon a connected-by-construction rooted 1-tree Gibbs family. It learns residual edge perturbations from unbiased TSP costs using implicit differentiation, incorporating a smoothed Held-Karp layer for degree balance and certificate-guided sharpening to enhance tour-like structures. Experimental results demonstrate that C2TSP not only achieves robust decoding performance but also preserves interpretable structural information, offering a more transparent and effective way to tackle TSP compared to methods that defer structural learning to later stages.