Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems
Researchers have introduced C2TSP, a breakthrough unsupervised learning pipeline for the Traveling Salesman Problem (TSP). By focusing on learning structurally meaningful latent objects rather than relying solely on the final decoding stage, C2TSP opens up new possibilities for AI-driven combinatorial optimization.
Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems
Learning-based methods for the traveling salesman problem (TSP) are often evaluated through the tours produced after decoding or search, but the learned object itself frequently lives in a surrogate space such as heatmaps, assignments, construction policies, or search-guidance scores. This hides the fundamental question: what Hamiltonian structure has actually been learned before decoding?
In this study, we directly answer this question by learning TSP through a structurally meaningful latent object, rather than leaving most of the Hamiltonian structure to the final decoding stage. Based on a connected-by-construction rooted 1-tree Gibbs family, we propose an end-to-end unsupervised learning pipeline called C2TSP.
The pipeline learns residual edge perturbations from unbiased TSP cost through implicit differentiation. For structural correction, a smoothed Held--Karp layer restores expected degree balance, while certificate-guided sharpening further pushes the connected distribution toward more tour-like structures.
Experiments show that C2TSP yields strong decoding performance while preserving interpretable structural information. Ablations further verify that edge perturbation and certificate-guided sharpening jointly improve both tour cost and tour-like structure.
Source: arXiv cs.AI Recent
