- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
Authors propose an unsupervised learning pipeline for solving the traveling salesperson problem. Ideally, one would like to learn Gibbs distribution over Hamiltonian cycles, which is computationally intractable. Therefore, one would like to consider a tractable surrogate which captures some of the structure of the Hamiltonian cycles.
Authors consider Gibbs distribution over 1-trees -- an object frequently used in the classical TSP heuristics, which can be seen as a tractable surrogate. Any TSP tour is a 1-tree, but a 1-tree is a tour only if all its vertices have degree equal to 2. However, they resemble tours much better than arbitrary heatmaps, as they are connected. To make produced 1-trees resemble tours even more, they add additional terms based on the classical Held-Karp dual ensuring that the expected degree of each vertex is 2.
In empirical evaluation, authors show that the outputs of their model really resemble tours (connected and degrees close to 2). They also show performance improvements over previous works.
Critical strengths
- I like the idea of unsupervised learning steered towards structured surrogates motivated by theory. Likely, incorporating theoretical knowledge about TSP in the learning pipelines will be needed for further progress.
- performance improvements compared to the existing models are well visible in the empirical experiments
- I appreciate that the authors considered also non-euclidean TSP instances, as the euclidean ones have very little structure and, moreover, the classical methods solve them very well.
Critical weaknesses
- I find the comparison with the previous models somewhat dubious in the case of non-euclidean datasets, as the other models (due to their design) are run without access to the real distance matrix. I wonder if it would be better to present only the numbers corresponding to the model proposed in this paper.
Questions for authors
I see the overlap with the optimal tour in table 1. I am wondering what is the effect of the decoder here, since the decoder can deviate from the original heatmap when turning it into a tour. What would be the (weighted) coverage of the original heatmap?
2 comments
thank you for your response. Similarly to Reviewer RWSX, I like the method proposed in your paper. Since I am not an experimentalist I consider this method your main contribution and I maintain my score. However, it would surely help to clarify the issues in the experimental section with RWSX.
Summary of our response. We thank the reviewer for the constructive comments. We first summarize our responses to the two questions and then respond in detail:
Response to the non-Euclidean comparison (W1): We accept the suggestion and will keep only the C2TSP numbers in the main text.
Response to the effect of the decoder (Q1): The decoder has little effect, because the learned marginal already covers almost the same Concorde-tour edges as the decoded tour.
(W1) Should only the C2TSP numbers be reported on non-Euclidean instances?
We agree and will keep only the C2TSP numbers in the main text, moving the baseline numbers to the appendix and summarizing the comparison in words, since the baselines cannot access the distance matrix. This change does not weaken our design advantage: every C2TSP component, including edge-perturbation learning, HK equilibration, and certificate-guided sharpening, operates directly on the edge costs. Adding distance-matrix features to the baselines or retraining them on non-Euclidean instances would not necessarily remove this gap, because learning from a general cost structure remains difficult without a cost-aware algorithmic design.
(Q1) What is the effect of the decoder on the coverage in Table 1?
The decoder has little effect on coverage: the top-n edges of the learned marginal recover 87.80% of the Concorde-tour edges (82.87% cost-weighted), almost the same as the 87.51% (83.57%) recovered by the decoded tour in Table 1 (Table R1). The reason is that the structured MAP decoder (Appendix D) builds tours from MAP rooted 1-trees of the learned distribution and only repairs their degree defects, so it preserves the learned structure.
Table R1: Coverage of Concorde-tour edges on TSP-50 (P+S): top-n marginal edges versus the decoded tour.
We hope these responses address the reviewer's concerns, and we are happy to answer any further questions during the discussion period.