Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems
Quick Answer
The C2TSP model introduces an end-to-end unsupervised learning pipeline for the Traveling Salesman Problem, focusing on learning a structurally meaningful latent object.
Quick Take
The C2TSP model introduces an end-to-end unsupervised learning pipeline for the Traveling Salesman Problem, focusing on learning a structurally meaningful latent object. By utilizing a connected-by-construction rooted 1-tree Gibbs family, it achieves strong decoding performance while maintaining interpretable structural information, enhancing both tour cost and tour-like structure through edge perturbation and certificate-guided sharpening.
Key Points
- C2TSP learns residual edge perturbations from unbiased TSP costs via implicit differentiation.
- A smoothed Held–Karp layer restores expected degree balance in the model.
- Certificate-guided sharpening enhances the connected distribution towards tour-like structures.
- Experiments demonstrate strong decoding performance with interpretable structural information.
- Ablation studies confirm improvements in tour cost and structure from edge perturbation.
Paper Resources
📖 Reader Mode
~2 min readAbstract: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.
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2607.12127 [cs.AI] |
| (or arXiv:2607.12127v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2607.12127 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Xinwu Qian [view email]
[v1]
Mon, 13 Jul 2026 20:21:08 UTC (91 KB)
— Originally published at arxiv.org
Want this in your inbox every morning?
Daily brief at your local 8am — bilingual EN/中文, free.
More from arXiv cs.AI
See more →The Emerging Paradigm of Geospatial Foundation Models: From Pre-Training to Agentic Reasoning
The paper introduces Geospatial Foundation Models (GeoFMs), AI/ML models pre-trained on extensive geospatial datasets, enabling domain experts to fine-tune them for specific tasks. This paradigm shift democratizes access to advanced AI/ML while ensuring security, and proposes a framework for cost-effective adaptation strategies. The vision of Agentic Geospatial Reasoning is also presented, where Large Language Models orchestrate GeoFMs to automate complex analytical workflows.