Pith. sign in

REVIEW 5 major objections 5 minor 44 references

Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers

T0 review · 5 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For MCTS-based TSP solvers, tuning the search matters as much as the heatmap, and a parameter-free k-nearest-neighbor prior can match learned heatmaps.

desk verdict A useful, transparent evaluation study showing MCTS tuning dominates heatmap choice, but the headline 'surpass' claim needs variance estimates before it is treated as definitive. read the letter →

arxiv 2411.09238 v2 pith:TFPJYFRB submitted 2024-11-14 cs.LG

Xuanhao Pan , Chenguang Wang , Chaolong Ying , Ye Xue , Tianshu Yu This is my paper · ORCID
classification cs.LG MSC 90C2768T20
keywords travelingsalesmanproblemMonteCarloTreeSearchheatmapk-nearestneighborhyperparametertuningcombinatorialoptimizationgeneralization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to show that in the 'heatmap + Monte Carlo Tree Search' recipe for the traveling salesman problem, the search component has been undervalued. It argues that MCTS hyperparameter settings can change solution quality by tens of percentage points, and that per-heatmap tuning is required before heatmap methods are compared fairly. It introduces GT-Prior, a parameter-free heatmap that assigns each edge a probability from the empirical distribution of k-nearest-neighbor ranks in optimal tours. With an optimally tuned MCTS, GT-Prior matches or beats learned heatmaps such as DIFUSCO: 0.50% versus 0.33% gap at TSP-500, 0.85% versus 0.53% at TSP-1000, and 2.13% versus 2.36% at TSP-10000. The paper's point is that heatmap sophistication is not the main driver of performance, so evaluation should balance learning and search.

What carries the argument

The load-bearing object is GT-Prior, a parameter-free heatmap defined by $P^N_{ij} = \hat{P}_N(k_{ij})$, where $k_{ij}$ is the rank of city $j$ among city $i$'s neighbors by Euclidean distance and $\hat{P}_N(\cdot)$ is the averaged empirical distribution of nearest-neighbor ranks in optimal tours. This heatmap carries the argument by supplying edge probabilities that are cheap to compute, scale-independent, and transferable across instance sizes and distributions. The other essential mechanism is the MCTS hyperparameter tuning pipeline: a grid search over six parameters (Alpha, Beta, Max_Depth, Max_Candidate_Num, Param_H, and Use_Heatmap) run separately for each heatmap, so that comparisons isolate heatmap quality from search configuration. The paper uses SHAP value analysis to attribute performance changes to individual hyperparameters, showing that parameters like Max_Candidate_Num and Use_Heatmap have large, context-dependent effects.

What would settle it

Re-run the TSP-10000 comparison with several tuning seeds and many fresh test instances, reporting confidence intervals for each method's mean gap; if GT-Prior's 2.13% gap is not statistically below DIFUSCO's 2.36%, the 'match or surpass' claim collapses. Alternatively, if tuning MCTS on the test distribution instead of a small uniform tuning set changes the ranking of the methods, the protocol-transfer assumption fails.

Watch

Extended reading notes

Core claim

The central claim is that in the 'Heatmap + MCTS' paradigm, the configuration of the MCTS search component is a dominant, often decisive factor for solution quality, and that a simple heatmap built from a k-nearest-neighbor prior can rival or surpass complex learned heatmaps when the search is tuned properly. The paper derives GT-Prior from the empirical observation that, in optimal Euclidean TSP tours, the next city is almost always among a city's closest neighbors: the probability that the optimal edge connects to one of the top-5 nearest neighbors exceeds 94%, and the top-10 exceed 99%, with little variation across problem scale or distribution. GT-Prior sets each edge probability to the empirical frequency of that neighbor rank, requiring no learning phase. When combined with MCTS hyperparameters tuned per heatmap, GT-Prior achieves 0.50%, 0.85%, and 2.13% optimality gaps on TSP-500, TSP-1000, and TSP-10000, respectively, and it shows minimal performance degeneration when scaled up or shifted to clustered, explosion, implosion, and TSPLIB instances. The paper also shows that even a 'Zero' heatmap that gives no edge guidance improves from a 5.49% gap to 1.06% on TSP-1000 simply through MCTS tuning, underscoring how much of the reported performance in this line of work comes from search rather than learned priors.

Load-bearing premise

The conclusions rest on the assumption that the MCTS hyperparameters selected on a small tuning set of uniform instances remain appropriate on the unseen test instances and the other distributions, and that the reported gap differences between methods are larger than run-to-run and instance-to-instance noise.

Editorial extensions

If this is right

  • Per-heatmap MCTS tuning should become standard practice in this line of research, since default MCTS settings can produce misleading rankings of heatmap methods.
  • Researchers should report a tuned non-informative baseline: a Zero heatmap already reaches 0.66% gap on TSP-500 and 1.06% on TSP-1000 after tuning, so a learned heatmap should be measured against it.
  • Because the k-nearest-neighbor locality property holds across scales and distributions, restricting candidate edges to a small k-NN neighborhood is a principled way to sparsify heatmap-guided search.
  • GT-Prior's near-zero degeneration when moving from TSP-500 to TSP-10000 or from uniform to clustered data establishes that simple structural priors are a strong generalization baseline for Euclidean TSP.
  • The comparison protocol introduced here, with dedicated tuning for each heatmap and a parameter-free prior as reference, provides a reusable template for fair evaluation of future heatmap models.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If MCTS tuning is as powerful as the paper reports, some of the performance gains attributed to new learned heatmaps in prior literature may actually come from differences in search configuration; re-benchmarking under a standardized tuned-search pipeline could reorder published rankings.
  • A practical extension would be a hyperparameter recommender that predicts near-optimal MCTS settings from instance features and heatmap statistics, replacing exhaustive grid search while preserving the tuned-search comparison protocol.
  • Because GT-Prior is parameter-free and costs nothing at inference, it doubles as an economic sanity check: a learned heatmap should beat it by a margin that justifies the cost of training and heatmap generation.
  • The stability of the k-nearest-neighbor prior across distributions suggests that similar locality-based priors could serve as strong baselines for other Euclidean geometric optimization problems, such as vehicle routing variants.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper evaluates the "Heatmap + MCTS" paradigm for Euclidean TSP. It argues that MCTS hyperparameter configuration is a dominant, under-appreciated performance factor, and that a simple k-nearest-neighbor-based heatmap, called GT-Prior, combined with tuned MCTS can match or outperform sophisticated learned heatmaps such as DIFUSCO. The evaluation covers TSP-500, TSP-1000, and TSP-10000, multiple synthetic distributions, and TSPLIB instances. The proposed evaluation pipeline tunes MCTS hyperparameters separately for each heatmap via grid search over 864 configurations and reports performance as optimality gap against Concorde or LKH-3 references. The main quantitative support is Table 1, where GT-Prior achieves 0.50%, 0.85%, and 2.13% gaps versus DIFUSCO's 0.33%, 0.53%, and 2.36%, and Section 4.2, where tuning improves the Zero heatmap from 5.49% to 1.06% on TSP-1000.

Significance. If the claims are statistically supported, the paper would make a useful field-level contribution: it would show that default MCTS configurations are often far from optimal and that fair heatmap comparison requires per-heatmap search tuning. The concrete deliverables are valuable: code, exact per-instance TSPLIB results, full hyperparameter tables, and separate tuning/test splits. The paper also makes a falsifiable prediction that a simple distance-derived prior is competitive with learned heatmaps under tuned search. However, the central same-distribution claims rest on point estimates without variance or significance information, and the GT-Prior is not parameter-free in the sense claimed because its probability mass function is fitted to Concorde/LKH optimal tours. The cross-distribution numbers in Table 3 are surprising and unexplained. The potential contribution is substantial, but the current evidence is not yet rigorous enough for the headline conclusions.

major comments (5)
  1. [§3.3, Table 1, Section 4.2] No variance estimates, confidence intervals, or significance tests are reported anywhere. The TSP-10000 tuning set contains only 16 instances, and the selected configuration is the best average gap over 864 grid combinations. This selection process is vulnerable to winner's-curse: the best-of-864 average on 16 instances can be a lucky configuration that does not transfer to the test set. The same-distribution claim that GT-Prior 'surpasses' DIFUSCO rests on 2.13% versus 2.36% in Table 1, a 0.23 percentage-point difference that could flip under resampling. I ask for paired bootstrap or nested resampling across instances and repeated MCTS runs, reporting standard errors and tuning-to-test degradation, before the 'match or surpass' statement can be accepted.
  2. [§5.1, Eq. (5)-(7), Appendix K] GT-Prior is described as 'parameter-free', but its distribution P_N(k) is an empirical histogram fitted to Concorde and LKH-3 optimal tours on uniform instances. This means the uniform benchmark partially measures transfer of a ground-truth-fitted distribution, not a purely assumption-free prior. The authors disclose the fitting in Appendix K and Figure 3, but the term 'parameter-free' is misleading and the comparison against learned heatmaps is not an apples-to-apples test of 'no learning'. I recommend either renaming this as an empirical prior with zero trainable parameters or adding an ablation using a fixed geometric prior (e.g., P(k) proportional to 1/k) to show that the specific fitted shape is not the source of the gains.
  3. [Table 3] The cross-distribution results are internally surprising and undermine the generalization narrative as presented. GT-Prior achieves 2.13% gap on uniform TSP-10000 (Table 1) but 0.35% on clustered, 0.93% on explosion, and 0.58% on implosion TSP-10000 instances (Table 3). SoftDist similarly shows 2.94% on uniform but 0.33% on implosion. If these numbers are correct, the paper should explain the mechanism: does the uniform-tuned MCTS configuration transfer much better to non-uniform instances, or do the distribution-specific optimal tour lengths make the gap denominator more forgiving? As written, the table suggests either a large unmodeled interaction or a reporting inconsistency. At minimum, per-instance results and the specific MCTS configurations used for each distribution row should be provided.
  4. [§5.2, Section 3.5, footnote 1] The 'Zero' heatmap is described as providing no edge guidance, but when Use_Heatmap is set to False the MCTS still uses Euclidean distance for candidate set construction. The text in Section 5.2 says the Zero heatmap relies on 'distance for candidate selection', which is itself a form of guidance. This makes the Zero baseline a distance-based candidate set, not a no-information control, and weakens the claim that tuned MCTS alone achieves 0.66% on TSP-500. Please clarify exactly what information the Zero baseline receives and how it differs from a truly uninformative uniform candidate set.
  5. [Appendix F, Table 7] The row 'Tuned on TSPLIB' tunes MCTS hyperparameters on the same TSPLIB instances used for evaluation, so it is an in-sample tuning result rather than a generalization result. The paper does label this row clearly, but the abstract's claim of strong performance on 'established real-world TSPLIB benchmarks' should not be read as out-of-distribution generalization. I recommend moving 'Tuned on TSPLIB' out of the generalization table or explicitly stating in the main text that these are optimistic in-sample upper bounds.
minor comments (5)
  1. [§4.1, Figure 1] The text says Max_Candidate_Num has a 'strong, often positive, impact' and then concludes that reducing the candidate set size can improve quality, but a positive SHAP value indicates longer tours, i.e., worse performance. The causal direction should be stated explicitly to avoid confusion.
  2. [Figure 2] The caption calls these box plots, but the text describes green circles, red crosses, and blue stars. The figure appears to overlay point markers on distributions; the caption should describe the actual plot elements.
  3. [Appendix G, Table 11] The table says 'Bolded configurations indicate default settings from prior works', but the bold formatting is not visible in the text. Please mark the defaults explicitly, for example with a footnote.
  4. [Section 3.5] The description of test sets says they are 'sourced from Fu et al. [9]', but the number of test instances and the exact instance seeds are not stated. Please add instance counts and seed-generation details to the appendix for reproducibility.
  5. [Section 4.2] The phrase 'crippling 91.31%' is unnecessarily strong and not supported by the quantitative framing used elsewhere. Consider replacing it with a neutral statement such as 'a 91.31% gap'.

Circularity Check

1 steps flagged · score 4.0 of 10

GT-Prior's 'parameter-free' heatmap is an empirical histogram fitted to Concorde/LKH-3 optimal tours on the same uniform distribution later used for evaluation, making the uniform-benchmark match/surpass claim partially a re-statement of fitted statistics; cross-distribution results remain independent.

  1. fitted input called prediction [Section 5.1, Eqs. (5)-(7); Appendix K; Table 1]
    "To formalize this, we analyzed (near-)optimal solutions for uniform TSP instances of varying sizes (TSP-500, TSP-1000 using Concorde; TSP-10000 using LKH-3). ... The averaged empirical distribution ˆPN (k) = 1/|I| Σ nI_k/N is shown in Figure 3. ... P^N_ij = ˆPN (kij) ... Importantly, this heatmap is parameter-free and scale-independent, thus requiring no tuning or learning phase."

    The GT-Prior heatmap is, by construction, the empirical histogram of k-nearest-neighbor ranks in optimal tours (Eqs. 5-7), with the fitted probabilities tabulated in Appendix K. Table 1 then reports GT-Prior's optimality gaps on uniform test instances of the same sizes and distribution used to estimate that histogram. The 'prediction' that GT-Prior matches or surpasses learned heatmaps on uniform TSP is therefore an in-distribution evaluation of a ground-truth-fitted quantity, not a test of a parameter-free first-principles prior. The label 'parameter-free' refers only to the absence of gradient-trained weights; the distribution itself was fitted to optimal-solution statistics, making the uniform-benchmark result partly a restatement of the fitting data.

full rationale

The paper's central methodological contribution is a well-executed, per-heatmap MCTS tuning pipeline, and the finding that MCTS configuration strongly affects solution quality is supported by independent experiments (Figure 2, Tables 1, 10) and does not reduce to any fitted input. The main circularity concern is confined to GT-Prior: although advertised as 'parameter-free', its heatmap values are estimated from Concorde/LKH-3 optimal tours on uniform instances (Section 5.1, Appendix K), and Table 1 evaluates exactly that same uniform distribution. Consequently, the headline claim that a simple prior can match or surpass learned heatmaps is partially a self-comparison on the fitting distribution. However, the paper also demonstrates genuine generalization across distributions and TSPLIB instances, where the uniform-fitted prior is applied out-of-distribution; those results are not circular. No load-bearing self-citation, imported uniqueness theorem, or ansatz-smuggling was found. Overall, the circularity is partial and localized, warranting a score of 4 rather than a higher score.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

Everything the central claim rests on that the reader didn't pay for upstream: GT-Prior's empirical PMF (fitted to optimal tours), per-heatmap MCTS configurations (fitted by grid search), and the domain assumptions of transfer, faithful reproduction of third-party heatmaps, and LKH-3-based ground truth. No invented entities are introduced; GT-Prior is a constructed heatmap baseline, not a postulated physical or conceptual entity.

free parameters (2)
  • GT-Prior empirical PMF P_N(k) = Provided in Appendix K (e.g., TSP-500 first entries: 0.440, 0.256, 0.133, 0.073 for k=1..4)
    The per-rank probability vector is an empirical histogram fitted to Concorde and LKH-3 optimal tours over 16-128 uniform instances. The paper calls this parameter-free, but the PMF shape is a fitted constant per scale and distribution.
  • MCTS hyperparameters (Alpha, Beta, Max_Depth, Max_Candidate_Num, Param_H, Use_Heatmap) = One 6-tuple per heatmap and scale; selected values in Table 13 (e.g., GT-Prior TSP-500: Alpha=0, Beta=10, H=5, MCN=5…
    Selected by grid search over 864 combinations on tuning sets (128 instances for TSP-500/1000, 16 for TSP-10000), picking the best average optimality gap. These data-fitted settings are load-bearing for the headline comparisons.
assumptions (4)
  • domain assumption The k-NN locality distribution measured on optimal tours of uniform instances transfers across problem scales and distributions.
    GT-Prior is built from Eq. (5)-(7) using the PMF estimated from TSP-500/1000/10000 uniform instances; Tables 2 and 3 test this transfer and empirically support it.
  • domain assumption The canonical Fu et al. [9] MCTS implementation and the third-party heatmaps sourced via Xia et al. [37] faithfully represent the compared methods.
    All learning-based heatmaps are run on the authors' MCTS setup; defaults are taken from Fu et al. Section 3.5 sources pretrained models from original authors. If the implementation or defaults misrepresent any method, the comparisons are compromised.
  • domain assumption Concorde and LKH-3 tour lengths serve as ground truth for gap computation at all scales.
    TSP-10000 gaps are computed against LKH-3 near-optimal tours rather than proven optima (Section 3.5), so reported low gaps partly reflect LKH-3's own accuracy.
  • domain assumption Grid-searched best-average-gap configurations on small tuning sets generalize to test instances of the same distribution.
    Sections 3.3 and 4.2 select one configuration per heatmap per scale from 864 candidates on 16-128 tuning instances; no tuning-set-to-test-set gap or variance is reported.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers." pith.science (2026). https://pith.science/paper/TFPJYFRB

@misc{pith2026241109238,
  author       = {Pith},
  title        = {Pith review of: Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TFPJYFRB}},
  note         = {Machine review of arXiv:2411.09238}
}
abstract

The ``Heatmap + Monte Carlo Tree Search (MCTS)'' paradigm has recently emerged as a prominent framework for solving the Travelling Salesman Problem (TSP). While considerable effort has been devoted to enhancing heatmap sophistication through advanced learning models, this paper rigorously examines whether this emphasis is justified, critically assessing the relative impact of heatmap complexity versus MCTS configuration. Our extensive empirical analysis across diverse TSP scales, distributions, and benchmarks reveals two pivotal insights: 1) The configuration of MCTS strategies significantly influences solution quality, underscoring the importance of meticulous tuning to achieve optimal results and enabling valid comparisons among different heatmap methodologies. 2) A rudimentary, parameter-free heatmap based on the intrinsic $k$-nearest neighbor structure of TSP instances, when coupled with an optimally tuned MCTS, can match or surpass the performance of more sophisticated, learned heatmaps, demonstrating robust generalizability on problem scale and distribution shift. To facilitate rigorous and fair evaluations in future research, we introduce a streamlined pipeline for standardized MCTS hyperparameter tuning. Collectively, these findings challenge the prevalent assumption that heatmap complexity is the primary determinant of performance, advocating instead for a balanced integration and comprehensive evaluation of both learning and search components within this paradigm. Our code is available at: https://github.com/LOGO-CUHKSZ/rethink_mcts_tsp.

Figures

Figures reproduced from arXiv: 2411.09238 by the authors.

Figure 1
Figure 1. Beeswarm plots of SHAP values for three different heatmaps. MD: [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Box plots of the optimality gap (%) for various heatmap sources, scales and MCTS settings. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Empirical distribution of k-nearest neighbor selection in optimal TSP tours The k-nearest prior in TSP posits that optimal tour edges predominantly connect a city to one of its clos￾est neighbors. This empirical observation has been implicitly used in constructing sparse graph inputs for learning models [9, 31, 25], yet its direct use as a primary heatmap source has been less explored. To elucidate the k-nearest pri… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Beeswarm plots of SHAP values for six methods across different TSP sizes. [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: Beeswarm plots of SHAP values for the UTSP heatmap across different TSP sizes. [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]
Figure 6
Figure 6. Figure 6: Representative TSPLIB instances visualization. [PITH_FULL_IMAGE:figures/full_fig_p022_6.png]
Figure 7
Figure 7. Figure 7: Empirical distribution of k-nearest neighbor in optimal TSP tours of different distributions [PITH_FULL_IMAGE:figures/full_fig_p023_7.png]
Figure 8
Figure 8. Figure 8: Impact of search time on solver performance across different hyperparameter configurations. [PITH_FULL_IMAGE:figures/full_fig_p024_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 24 canonical work pages

  1. [1]

    Certification of an optimal tsp tour through 85,900 cities

    David L Applegate, Robert E Bixby, Vašek Chvátal, William Cook, Daniel G Espinoza, Marcos Goycoolea, and Keld Helsgaun. Certification of an optimal tsp tour through 85,900 cities. Operations Research Letters, 37(1):11–15, 2009

    work page 2009

  2. [2]

    Neural combina- torial optimization with reinforcement learning

    Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016

    arXiv 2016

  3. [3]

    Learning generalizable models for vehicle routing problems via knowledge distillation

    Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. Advances in Neural Information Processing Systems, 35:31226–31238, 2022

    2022

  4. [4]

    Learning to perform local rewriting for combinatorial optimization

    Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in neural information processing systems, 32, 2019

    2019

  5. [5]

    Simulation-guided beam search for neural combinatorial optimization

    Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tierney, and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:8760–8772, 2022

    work page 2022

  6. [6]

    Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning

    Paulo R d O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian conference on machine learning, pages 465–480. PMLR, 2020

    work page 2020

  7. [7]

    Learning heuristics for the tsp by policy gradient

    Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings 15 , pages 170–181....

    work page 2018

  8. [8]

    Invit: A generalizable routing problem solver with invariant nested view transformer

    Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. Invit: A generalizable routing problem solver with invariant nested view transformer. arXiv preprint arXiv:2402.02317, 2024

    arXiv 2024

Show all 44 references
  1. [9]

    Generalize a small pre-trained model to arbitrarily large tsp instances

    Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 7474–7482, 2021

    2021

  2. [10]

    An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems

    Keld Helsgaun. An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966–980, 2017

    2017

  3. [11]

    Efficient active search for combinatorial optimization problems

    André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. arXiv preprint arXiv:2106.05126, 2021

    2021 arXiv

  4. [12]

    Graph neural network guided local search for the traveling salesperson problem

    Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:2110.05291, 2021

    2021 arXiv

  5. [13]

    An efficient graph convolutional network technique for the travelling salesman problem

    Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019

    1906 arXiv

  6. [14]

    Learning combinatorial optimization algorithms over graphs

    Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017

    2017

  7. [15]

    Learning collaborative policies to solve np-hard routing problems

    Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34:10418–10430, 2021. 10

    2021

  8. [16]

    Sym-nco: Leveraging symmetricity for neural combinatorial optimization

    Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:1936– 1949, 2022

    1936

  9. [17]

    Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019

    Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019

    2019

  10. [18]

    Pomo: Policy optimization with multiple optima for reinforcement learning

    Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21188–21198, 2020

    2020

  11. [19]

    Matrix encoding networks for neural combinatorial optimization

    Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Informa- tion Processing Systems, 34:5138–5149, 2021

    2021

  12. [20]

    Smac3: A versatile bayesian optimization package for hyperparameter optimization

    Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter. Smac3: A versatile bayesian optimization package for hyperparameter optimization. Journal of Machine Learning Research, 23(54):1–9, 2022

    2022

  13. [21]

    Multi-task learning for routing problem with cross-problem zero-shot generalization

    Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1898–1908, 2024

    1908

  14. [22]

    A unified approach to interpreting model predictions

    Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In I. Guyon, U. V . Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30 , pages 4765–4774. Curran Associa...

    2017

  15. [23]

    Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M

    Scott M. Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M. Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. Nature Machine Intelligence , 2(1): 2522–5839, 2020

    2020

  16. [24]

    Combinatorial opti- mization by graph pointer networks and hierarchical reinforcement learning

    Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial opti- mization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv:1911.04936, 2019

    1911 arXiv

  17. [25]

    Unsupervised learning for solving the travelling salesman problem

    Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems, 36, 2024

    2024

  18. [26]

    A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem.INFORMS Journal on Computing, 25(2):346–363, 2013

    Yuichi Nagata and Shigenobu Kobayashi. A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem.INFORMS Journal on Computing, 25(2):346–363, 2013

    2013

  19. [27]

    H-tsp: Hierarchically solving the large-scale traveling salesman problem

    Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, and Jiang Bian. H-tsp: Hierarchically solving the large-scale traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9345–9353, 2023

    2023

  20. [28]

    A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems

    Bo Peng, Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In Artificial Intelligence Algorithms and Applications: 11th International Symposium, ISICA 2019, Guangzhou, China, November 16–17, 2019,...

    2019

  21. [29]

    Dimes: A differentiable meta solver for combinatorial optimization problems

    Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35: 25531–25546, 2022

    2022

  22. [30]

    Tsplib—a traveling salesman problem library

    Gerhard Reinelt. Tsplib—a traveling salesman problem library. ORSA journal on computing, 3 (4):376–384, 1991

    1991

  23. [31]

    Difusco: Graph-based diffusion solvers for combinatorial optimization

    Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural Information Processing Systems, 36:3706–3731, 2023. 11

    2023

  24. [32]

    Pointer networks

    Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015

    2015

  25. [33]

    Efficient training of multi-task combinarotial neural solver with multi-armed bandits

    Chenguang Wang and Tianshu Yu. Efficient training of multi-task combinarotial neural solver with multi-armed bandits. arXiv preprint arXiv:2305.06361, 2023

    2023 arXiv

  26. [34]

    A game-theoretic approach for improving generalization ability of tsp solvers

    Chenguang Wang, Yaodong Yang, Oliver Slumbers, Congying Han, Tiande Guo, Haifeng Zhang, and Jun Wang. A game-theoretic approach for improving generalization ability of tsp solvers. arXiv preprint arXiv:2110.15105, 2021

    2021 arXiv

  27. [35]

    Asp: Learn a universal neural solver! IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024

    Chenguang Wang, Zhouliang Yu, Stephen McAleer, Tianshu Yu, and Yaodong Yang. Asp: Learn a universal neural solver! IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024

    2024

  28. [36]

    Learning improvement heuristics for solving routing problems

    Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE transactions on neural networks and learning systems, 33(9):5057–5069, 2021

    2021

  29. [37]

    Position: Rethinking post-hoc search-based neural approaches for solving large-scale traveling salesman problems

    Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoc search-based neural approaches for solving large-scale traveling salesman problems. In Proceedings of the 41st International Conference on Machine Learning, pages 54178–...

    2024

  30. [38]

    Glop: Learning global partition and local construction for solving large-scale routing problems in real-time

    Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20284–2...

    2024

  31. [39]

    Towards omni-generalizable neural methods for vehicle routing problems

    Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learning, pages 42769–42789. PMLR, 2023

    2023

  32. [40]

    Mvmoe: Multi-task vehicle routing solver with mixture-of-experts

    Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. arXiv preprint arXiv:2405.01029, 2024. 12 A Additional Related Works Approaches using machine learning to address the Travelling ...

    2024 arXiv

  33. [41]

    Sparsification: Retaining only the top-5 values for each row, setting all others to a significantly negative number

  34. [42]

    DIFUSCO DIFUSCO also generates a sparse heatmap based on the k-NN subgraph (k = 50 for TSP-500, k = 100 for larger scales)

    Adaptive softmax: Iteratively applying a temperature-scaled softmax function with gradual temperature reduction until the minimum non-zero probability exceeds a predefined threshold. DIFUSCO DIFUSCO also generates a sparse heatmap based on the k-NN subgraph (k = 50 for TSP-500...

  35. [43]

    For TSP-500 and TSP-1000: A single step integrating Euclidean distances, thresholding, and symmetrization

  36. [44]

    b) The same process as used for smaller instances

    For TSP-10000: Two steps are applied sequentially: a) Additional supervision using a greedy decoding strategy followed by 2-opt heuristics. b) The same process as used for smaller instances. 13 Table 4: Performance Degeneration for Different Methods with and without Postproces...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.