acceptodds
Under review as a conference paper at ICLR 2027

Classical Control Strength and Exact/Certified Anchors in Neural TSP Evaluation

Abstract

Across four separately controlled Euclidean TSP blocks spanning and uniform/clustered spatial generators, fixed-start nearest-neighbor construction lies roughly 17–25% above the exact or certified optimization anchor, whereas the specified audited local-search controls lie roughly 1.2–3.6% above it. The clustered protocol and primary endpoint were fixed before the 50,000-step training runs, with the held-out evaluation sets sampled only afterward. The clustered replication reproduces this separation at both sizes. This replicated separation shows how comparator strength changes the scale on which comparisons between learned and classical methods are interpreted; interpretation also depends on the selected checkpoint, inference multiplicity, and the form of the optimization anchor. We use common-instance evaluation, independently recomputed float64 objectives, exact float64 Held–Karp anchors at TSP20, and certified float64 optimum intervals from exact scaled-integer Concorde solves at TSP50. Across both tested distributions, the selected local POMO model has the smaller gap at , whereas audited 2-opt has the smaller gap at . Because the blocks use separately trained models and different inference/search protocols, this observation is descriptive and does not support a causal scaling claim or a ranking of method families.

Primary area:
optimization
Keywords:
neural combinatorial optimization, traveling salesman problem, neural routing, evaluation methodology, classical heuristics, exact optimization, certified optimization

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_G4sCOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper highlights how baseline strength and the choice of “optimal anchor” can substantially affect neural TSP evaluation. The authors compare nearest neighbor, 2-opt local search, and AM/POMO on common TSP instances under uniform and clustered distributions. They find that local search provides a much stronger baseline than nearest neighbor, while the relative performance of POMO and 2-opt varies with instance size. The results are protocol-specific descriptive comparisons rather than causal rankings.

Critical strengths

None

Critical weaknesses

I do not consider this a complete research paper.

1) The motivation is insufficient to support a research contribution. The paper argues that baseline strength and the choice of the “optimal anchor” can substantially affect neural TSP evaluation. In my view, this is largely obvious and does not constitute a meaningful research question. Moreover, TSP methods are typically evaluated by their gap to strong references such as Concorde or LKH, rather than by ranking. Thus, the paper’s central motivation is not convincing.

2) The experimental study is also quite limited. It focuses on small-scale instances and only a narrow set of comparable methods, making it difficult to support the broader claims.

3) The paper is unnecessarily difficult to read due to awkward writing and poor formatting. I also could not understand the Reproducibility section, which appears insufficiently substantiated and, to me, contains claims that are difficult to verify from the paper.

Questions for authors

I would like to clearly understand the purpose behind this study and the authors’ motivation for conducting it. I need a clear and well-justified research motivation.

Reviewer_BCxcOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper is extremely poorly written, and the terminology used is far outside the standards of the ML/NCO community.

Despite careful reading, it is very hard to follow: sentences often repetitive, disconnected from the context, and the purpose of the study is difficult to understand.

To be taken seriously, this work would need to be completely rewritten before being submitted for review.

As far as can be understood from the manuscript, the authors analyze how a neural model (POMO) performs compared with nearest-neighbor and 2-opt baselines on small TSP instances. Since TSP20 and TSP50 can be solved exactly (the authors themselves use Held–Karp and Concorde), this question has little value. In the NCO community, exact solutions are routinely reported as the reference for instances of this size, so it is unclear why nearest-neighbor and 2-opt gaps matter at all. The question might be meaningful for large-scale TSP, where exact solutions are unavailable, but that would require substantially more effort and completely different methodology.

Critical strengths

None

Critical weaknesses

(1) The paper is extremely unclear and hard to follow, and it falls below the standards of conferences even less rigorous than ICLR.

(2) The topic of this research is too naive and completely uninteresting.

Questions for authors

Given how unclear the manuscript is, it is hard to pose meaningful questions to the authors.

My only remark is that I do not understand the rationale for repeating the same sentences, phrases, and even whole paragraphs many times across the paper.

For example:

  1. The second paragraph of the introduction is nearly identical to the abstract.
  2. The paragraphs about the 3-opt budget in Section 4 and Section 8 are copy-pasted with only minor changes.
  3. The sentence “The held-out evaluation sets were sampled only after checkpoint selection was complete” is repeated at least 8 times.
  4. “The clustered protocol and primary endpoint were fixed before the 50,000-step training runs” is repeated about 6 times.
  5. The statement that the models were trained for 50,000 steps appears roughly 10 times.

This list could be much longer; there are dozens of similar examples.

Reviewer_3tj5OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents an empirical evaluation of learned and classical solvers for Euclidean TSP with 20 and 50 nodes, using uniform and clustered instance distributions. It compares locally trained AM and POMO models with fixed-start nearest neighbor, 2-opt, and bounded sampled 3-opt, using Held–Karp optima or Concorde-derived certified intervals as references. The principal finding is that nearest neighbor exhibits approximately 17–25% optimality gaps, whereas the local-search controls achieve approximately 1.2–3.6%. The paper also reports a size-dependent ordering between its selected POMO models and 2-opt, while explicitly restricting this observation to the evaluated configurations.

Critical strengths

Common-instance comparisons, independent float64 objective recomputation, permutation-validity checks, and local-optimum audits for 2-opt are sensible controls. The distinction between exact TSP20 references and quantization-derived TSP50 optimum intervals is clearly documented (§3 and Appendix B).

Critical weaknesses

1.The central contribution is insufficiently substantial.

The principal result is that local search produces considerably better tours than fixed-start nearest-neighbor construction. The paper itself acknowledges that strong baselines and transparent evaluation are established principles (§1). Demonstrating this separation across four small settings provides limited new insight into neural combinatorial optimization. The manuscript does not identify a concrete conclusion from existing neural-TSP evaluations that changes under its controls, or provide an explanatory analysis of the observed neural/classical differences. The novelty and significance relative to the evaluation literature discussed in §2 remain inadequately established.

2.The experimental scope is too restricted.

All experiments concern two-dimensional Euclidean TSP with only 20 or 50 nodes and two synthetic generators. There are no larger instances, established external benchmark datasets, or additional routing problems. Separately training models for every size/distribution combination also provides no evidence about transfer. A TSP-focused study can be valuable, but the combination of small problem sizes, limited distributional coverage, and shallow analysis substantially limits the significance of this particular study. The number of held-out instances does not compensate for the narrow range of settings.

3.The learned baselines are insufficiently validated, and lack advanced neural solver baselines.

The local AM and POMO configurations are explicitly not exact reproductions of the original training recipes. In particular, AM has approximately 21.62% and 30.48% gaps on uniform and clustered TSP50, respectively (Table 2). These results warrant a careful investigation of training adequacy and implementation choices. The manuscript provides neither learning curves nor comparisons with verified reference checkpoints, and Appendix A omits important architecture and optimizer settings. Consequently, the neural/classical ordering is difficult to interpret beyond the particular trained models. The reported results do not establish whether the observed gaps reflect adequately trained baselines.

4.The comparisons do not establish practical competitiveness.

AM uses single-start decoding, POMO uses 20 or 50 starts, and the classical methods operate under different search budgets (§§4–5). No measured runtimes or solution-quality-versus-time curves are provided. Although these differences are acknowledged, the experiments cannot determine performance at comparable computational cost. The classical comparator set is also limited to NN and relatively simple local-search controls; a stronger heuristic such as the cited Lin–Kernighan implementation would make the evaluation more informative. The initialization of 2-opt and sampled 3-opt should also be specified explicitly.

5.The available artifacts do not support the emphasis on auditability.

Section 10 states that the release excludes checkpoints, raw per-instance data, logs, and environments, with some artifacts only planned for future release. Hashes and manifests record provenance but cannot substitute for the underlying materials needed to verify the results. This is a consequential limitation for a paper whose contribution relies heavily on controlled, independently auditable evaluation.

6.The presentation is repetitive and poorly prioritized.

The same gap ranges, checkpoint-selection procedure, and qualifications about scaling and method-family rankings recur throughout the abstract, introduction, results, discussion, and conclusion. Meanwhile, the comprehensive four-block results table appears only in Appendix C. The manuscript devotes considerable space to repeated procedural statements while giving insufficient attention to the unresolved scientific question and the interpretation of the findings. Consolidating these statements and bringing the central results into the main text would improve clarity, but substantial additional analysis would still be needed.

Questions for authors

1.What specific scientific conclusion does this study establish beyond the acknowledged importance of strong baselines? Can the authors identify an existing neural-TSP conclusion that changes when evaluated using their proposed controls?

2.Can the authors provide complete training configurations, learning curves, and comparisons with reference implementations or checkpoints, particularly to explain the large AM gaps on TSP50?

3.How do the conclusions change under comparable inference-time budgets and with stronger classical heuristics? What initial tours are used for 2-opt and sampled 3-opt, and are these methods applied sequentially?

4.Do the observations remain informative on substantially larger TSP instances and established benchmark datasets? Which additional experiments would distinguish effects of training configuration, inference multiplicity, and instance size?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.