Search papers, labs, and topics across Lattice.
This study introduces C2TSP, an end-to-end unsupervised learning pipeline that learns tractable near-tour marginals for the Traveling Salesman Problem (TSP) by focusing on a structurally meaningful latent object rather than relying solely on final decoding. By employing a connected-by-construction rooted 1-tree Gibbs family, the method utilizes implicit differentiation to learn residual edge perturbations from unbiased TSP costs, while a smoothed Held鈥揔arp layer and certificate-guided sharpening enhance structural integrity. The results demonstrate that C2TSP not only achieves strong decoding performance but also retains interpretable structural information, with ablation studies confirming the benefits of its dual correction mechanisms.
Learning TSP through a structured latent object reveals critical Hamiltonian insights that improve both tour quality and interpretability.
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 \emph{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.
