Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem

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

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

Pith's one-line read DEITSP claims that a single denoising forward pass, followed by alternating noise re-addition and removal, yields near-optimal TSP solutions with far less inference time than prior diffusion-based solvers.

desk verdict Fast NAR diffusion TSP solver with strong empirical claims, but Algorithm 2's inference loop is specified using the ground-truth tour a0; that must be fixed before the results can be trusted. read the letter →

arxiv 2501.13767 v1 pith:J7J3H3QH submitted 2025-01-23 cs.LG

Mingzhao Wang , You Zhou , Zhiguang Cao , Yubin Xiao , Xuan Wu , Wei Pang , Yuan Jiang , Hui Yang
show 2 more authors
Peng Zhao Yuanshu Li
This is my paper · ORCID
classification cs.LG
keywords TravelingSalesmanProblemdiffusionmodelsnon-autoregressivecombinatorialoptimizationgraphtransformerself-consistencynoiseschedulingzero-shotgeneralization
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

DEITSP claims that a Traveling Salesman Problem solver does not need a long Markov-chain denoising process: a network trained to map any noised version of the optimal tour's adjacency matrix back to that matrix in one forward pass can already produce near-optimal heatmaps, and greedily decoding those heatmaps with 2-opt yields tours competitive with much slower autoregressive and diffusion baselines. The paper argues this works because the network is trained with a self-consistency objective across noise levels, so one denoising step is meaningful at any noise intensity, and because a dual-modality graph transformer lets six layers fuse node and edge information efficiently. It adds an inference loop that alternates noise removal with controlled noise re-addition under a decreasing inverse-function schedule, collecting several decoded tours and returning the shortest; this turns extra compute directly into better solutions. The reported consequence is that DEITSP reaches 0.00 to 0.10 percent gaps to Concorde on TSP20-100, generalizes zero-shot to TSP200-1000 and to real-world and TSPLIB instances, and does so with 7 to 28 times faster inference than strong diffusion and transformer baselines. If the claims hold, the method offers a practical knob: one iteration for speed, more iterations for quality.

What carries the argument

The load-bearing object is the trained one-step denoiser $\theta(a_t,g)$, a dual-modality graph transformer that takes node coordinates, a noisy adjacency matrix, and a time-step embedding, and outputs edge heatmaps $\tilde{a}_0$. A discrete categorical diffusion process with transition matrix $Q_t$, parameterized by noise rates $\beta_t$, creates noisy states $a_t \sim \mathrm{Cate}(a_0 \bar{Q}_t)$, and self-consistency training enforces $\theta(a_{t+k},g)=\theta(a_t,g)=a_0$ across paired noise levels, with the squared term $\lambda\|\theta(a_{t+k},g)-\theta(a_t,g)\|^2$ in Eq. (3). At inference the same network is reused in an alternating add/remove loop: uniform noise is denoised to a heatmap, a decreasing inverse-function schedule $\tau_i$ chooses how much noise to add back, each denoised heatmap is greedily decoded with 2-opt, and the best tour among all decoded candidates is returned. The dual-modality graph transformer carries the feature extraction: edge features and node features are updated in separate mixing modules and fused through attention, allowing multi-hop information flow with only six layers.

What would settle it

On a fixed set of TSP500 instances with known Concorde optima, run DEITSP with one iteration and with sixteen iterations and record the gap of every greedy-decoded candidate: if the one-iteration heatmap decodes to a gap far above the reported 2.15 percent, or if adding fifteen more candidates does not lower the gap toward that figure, the claim that one-step denoising is the source of solution quality would be refuted. An even sharper check is to remove 2-opt entirely and see whether single-step denoising plus greedy decoding alone can stay within a few percent of optimal on TSP100.

Watch

Extended reading notes

Core claim

DEITSP treats TSP solution generation as edge classification: each edge of the tour is a Bernoulli variable, and the network is trained to predict the adjacency matrix of the optimal tour from a noised version of it. The training loss combines two cross-entropy terms tying the network's output to the Concorde ground truth at two noise levels with a self-consistency term that forces the outputs from different noise levels to agree, so a single forward pass can denoise from any point on the noise trajectory. At inference, the model starts from uniform noise, denoises in one step, greedily decodes a feasible tour, then repeatedly re-adds noise at schedule-controlled levels and denoises again, collecting every decoded tour and returning the shortest. The paper reports that this beats all sixteen neural baselines on TSP20-100 solution quality, achieves the best or second-best results on TSP200-1000 while being far faster than tree-search methods, and outperforms baselines on real-world country maps and TSPLIB instances.

Load-bearing premise

The load-bearing premise is that a network trained on TSP100 instances with Concorde-optimal adjacency matrices as targets, seeing only synthetically noised versions of those matrices, learns a single-step denoiser that stays accurate enough for greedy-plus-2-opt decoding when the test size grows to 1000 nodes or the node distribution shifts to real-world maps.

Editorial extensions

If this is right

  • With 16 iteration steps, DEITSP reaches tour-length gaps of 0.00%, 0.01%, and 0.10% to Concorde on TSP20, TSP50, and TSP100, while a single iteration step still beats every learning-based baseline in wall-clock time.
  • Trained on TSP100 and applied zero-shot, DEITSP gets the best gaps on TSP200 (0.40%) and TSP500 (2.15%) and the second-best gap on TSP1000 (3.68%), with the leading method's better result coming from a Monte-Carlo-tree-search solver that is far slower.
  • On real-world country maps and TSPLIB instances, DEITSP with 16 iterations achieves the lowest average gap among neural baselines: 0.85% on Japan, 1.89% on USA, 2.30% on Burma, and 0.78% on the 26 TSPLIB instances.
  • The ablation shows that the alternating add/remove iteration beats standard DDIM sampling: DEITSP's 1-step result outperforms DDIM's 10-step result, and DEITSP's 5-step result outperforms DDIM's 50-step result.
  • Users can choose 1, 4, or 16 iterations to trade a few seconds or minutes for better tours, because the same network is reused and each extra denoising pass adds one more candidate solution to the set.

Reading between the lines

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

  • An implication the authors leave implicit is that the alternating add/remove loop is effectively a randomized local-search restart mechanism: each noise level seeds a different greedy tour, so solution quality should track the diversity of the decoded candidates rather than the accuracy of any one denoising pass; a reader could test this by comparing DEITSP with 16 iterations against 16 independen
  • Because the supervised target is the Concorde optimal tour at the training size, the method's ceiling is tied to the availability of exact labels; a natural extension, not explored in the paper, is to replace the cross-entropy terms with an unsupervised or policy-gradient cost so the same one-step denoiser can be trained on TSP sizes where exact labels are unavailable.
  • The decreasing inverse-function noise schedule is motivated by the sparsity of TSP optimal adjacency matrices; the same sparse-solution argument applies to other permutation problems with Hamiltonian-cycle structure, such as vehicle routing or the quadratic assignment problem, so transferring the schedule and the candidate-collection loop to those settings is a concrete testable next step.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes DEITSP, a non-autoregressive diffusion-based solver for two-dimensional Euclidean TSP. The method trains a dual-modality graph transformer to denoise corrupted adjacency matrices in a single step, using a consistency loss that ties predictions across noise levels. At inference, DEITSP iteratively adds and removes noise according to a custom schedule, aggregates the predicted heatmaps, and decodes them greedily with 2-opt to select the best tour. Experiments compare DEITSP against 16 neural baselines and Concorde on TSP20-1000, TSPLIB instances, and country-level real-world maps, claiming superior solution quality and inference speed, as well as zero-shot generalization to larger and non-uniform instances.

Significance. If the central claim holds, DEITSP would be a valuable NAR solver: single-step denoising plus iterative exploration provides a favorable solution-quality/latency trade-off, and the reported zero-shot generalization to TSP200-1000, TSPLIB, and real-world maps is practically relevant. The paper's strengths include extensive benchmarking, clear ablations of the network and iteration strategy, a public code release, and a genuine attempt to address the exploration problem in diffusion-based CO solvers. However, the inference pseudocode's use of ground-truth optimal tours makes the headline claim conditional on a clarification or correction; this issue is load-bearing for the paper's main contribution.

major comments (4)
  1. [Section 3.4, Algorithm 2, line 7] Algorithm 2 specifies the test-time inference procedure, but line 7 samples a_t from Cate(a_t; p = a0 Q_t), where a0 is the ground-truth optimal tour used in training (Algorithm 1, line 3). At test time a0 is unknown, so the pseudocode as written gives the solver oracle access to the optimum. This contradicts the accompanying text in Section 3.4.1, which says the method adds noise to the denoised data from the previous time step. If the released code follows the pseudocode, the reported results in Tables 1-3 and Table 6 are not from a deployable solver; if the code instead uses the predicted heatmap (e.g., sampling from tilde_a0 Q_t), the pseudocode must be corrected and the reported results confirmed to match that corrected procedure. This issue is central to the paper's empirical claim and must be resolved before the results can be interpreted.
  2. [Section 4.1, Table 1] Several baselines are marked with a dagger (TRANSFORMER, CNN_Transformer, ELG, NAR4TSP) and are tested on TSP20/50 using pre-trained TSP50 weights provided by the original papers. Using TSP50-trained weights on TSP20 puts these baselines at a systematic disadvantage, which is not acknowledged in the main comparison. This weakens the claim that DEITSP outperforms all neural baselines on TSP20. Please either run these baselines with models trained on the same TSP20 distribution or clearly state this limitation in the experimental protocol and in the conclusions drawn from Table 1.
  3. [Tables 1-3 and Table 4] The central empirical claims are based on mean performance over a single run: no standard deviations, no number of seeds, and no statistical significance tests are reported. Several key comparisons involve very small gap differences (e.g., DEITSP(16 Iter) at 0.01% versus Sym-NCO at 0.04% on TSP50, or 0.10% versus 0.12% on TSP100), which may be within run-to-run noise. Please report means and standard deviations over at least five seeds for DEITSP and for the closest baselines, so the claimed improvements are not attributable to randomness.
  4. [Section 4.5, Figure 4 and Eq. (3)] The inverse-function schedule with c_i in [0.25, 1.5] is selected after comparing schedules (linear, cosine, inverse) on the TSP50 test set, which constitutes test-set model selection and may inflate the reported TSP50 results. Additionally, the loss weight lambda in Eq. (3) is never given a value, although it affects the balance between cross-entropy and self-consistency terms and is part of the reported hyperparameter configuration. Please specify lambda and either use a held-out validation set for schedule selection or justify why the schedule choice is not overfitting to the test distribution.
minor comments (5)
  1. [Section 3.3] The sentence "? ] also indicates that the attention mechanism demonstrate slower rates of oversmoothing compared to GCNs" contains an unresolved citation placeholder and a subject-verb agreement error; please fix the reference and wording.
  2. [Section 4.1, Baselines paragraph] The baseline "BQ-NCO" is cited as "[? ]" in the text and does not appear in the reference list; this needs to be completed.
  3. [Table 6] The header for DEITSP(16 Iter) is missing the "(%)" label on the Gap column, and the timing for eil51 (e.g., 2.646s for DEITSP(1 Iter)) is inconsistent with the sub-second timings of all other instances in that table; please check whether this reflects a one-time initialization cost or a typo.
  4. [Appendix A] The phrase "degressively insert them into the partial solution" appears to be a typo for "progressively insert"; please correct it.
  5. [Section 4.5, Table 4] The ablation table reports Gap and Time but does not state the number of test instances or seeds; adding this information would improve interpretability of the reported differences.

Circularity Check

1 steps flagged · score 8.0 of 10

Algorithm 2's inference loop re-noises around the ground-truth optimal tour a0, so the reported iterative gains depend on oracle access to the answer.

  1. self definitional [Algorithm 2, Step 7 (Section 3.4.1); contrasted with Algorithm 1, Step 3 and Section 3.4.1 text]
    "Algorithm 2 DEITSP Inference 1: Input: Diffusion model θ, noise schedule τ_i, iteration step M, TSP instance g. 2: a_t∼ Uniform(a_t), t = T ... 7: a_t∼ Cate(a_t ; p =a0Qt) ⊲ Adding noise"

    In Algorithm 1, a0 is the ground-truth optimal tour drawn from the dataset via `a0,g∼D`. Algorithm 2 is presented as the deployable inference procedure, but its Step 7 samples the next noisy state from Cate(·; p = a0 Q_t), i.e., it adds noise around the optimal tour, not around the model's previous denoised prediction. At test time a0 is unknown, so the inference loop as written uses oracle access to the answer. The network is then asked, at every iteration, to denoise perturbed copies of the ground truth, making the multi-iteration gains and near-zero gaps reported in Tables 1-3 artifacts of the ground truth being an input.

full rationale

The paper's one-step denoising component is, on its own, a standard supervised heatmap predictor trained against Concorde solutions, and the headline comparisons are made against Concorde and external baselines, so the one-iteration results are not themselves circular. However, the distinctive contribution of the paper is the iterative add/remove-noise strategy that 'alternates between adding and removing noise to improve exploration.' Algorithm 2 specifies that each such iteration re-noises from a0, the ground-truth optimal tour, which is unavailable at deployment. Every improvement attributed to increasing iteration steps (e.g., DEITSP(1 Iter) to DEITSP(16 Iter) in Tables 1-3) is therefore explained by feeding the oracle solution back into the denoiser, not by a self-contained inference procedure. The Section 3.4.1 description contradicts the pseudocode by claiming noise is added to the previous denoised output; if the released code follows the prose, the pseudocode is a serious specification error, and if it follows the pseudocode, the reported results are not from a deployable solver. Separately, the inverse-function noise schedule is compared on test instances in Section 4.5, which is mild test-set model selection rather than a definitional circularity. Because the central iterative claim reduces by construction to oracle access, the score is 8.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central empirical claims rest on standard diffusion math, Concorde ground truth, and several ad hoc design choices. The most important unquantified choices are the unreported loss weight lambda and the inverse-function schedule interval picked from a TSP50 ablation.

free parameters (5)
  • Loss weight lambda in Eq. (3)
    Balances cross-entropy and consistency loss terms; value not reported in the paper, so training cannot be exactly reproduced.
  • Inverse-function schedule interval for c_i = [0.25, 1.5]
    Eq. (12) with f as inverse function; interval chosen via ablation on TSP50 (Figure 4), not derived.
  • Diffusion noise schedule endpoints = beta_1=1e-4, beta_T=0.02, T=1000
    Budget for the discrete diffusion process taken from prior work [15,17]; chosen by hand for this task.
  • Consistency step interval k = 20
    Distance between noise levels in the self-consistency loss, adopted from [33].
  • Network depth, width, and heads = 6 layers, hidden 256, 8 heads
    Architecture hyperparameters fixed across all experiments without an ablation or sensitivity analysis.
assumptions (5)
  • standard math Discrete diffusion forward process Q_t with Bernoulli transitions and a linear beta schedule is a valid noise model for TSP adjacency matrices.
    Taken from Austin et al. [2]; used to define noisy states in training.
  • ad hoc to paper Consistency training on pairs of noise levels separated by k steps is sufficient to learn a single-step denoiser.
    The paper provides no proof; it is a design assumption inherited from consistency models [43] and validated only empirically.
  • domain assumption Concorde-provided optimal tours for training instances are correct and representative of the optimal solution distribution.
    Supervised training and all gap measurements rely on Concorde [1] as ground truth.
  • ad hoc to paper The inverse-function noise schedule with c_i in [0.25,1.5] improves refinement across all instance sizes and distributions.
    Motivated by sparsity intuition in Section 3.4.2 and selected via ablation on TSP50 (Figure 4); transfer to larger instances is assumed.
  • domain assumption A network trained on TSP100 generalizes zero-shot to TSP200-1000 and to real-world/TSPLIB distributions.
    Core generalization claim in Sections 4.3-4.4; no re-training for larger instances.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem." pith.science (2026). https://pith.science/paper/J7J3H3QH

@misc{pith2026250113767,
  author       = {Pith},
  title        = {Pith review of: An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J7J3H3QH}},
  note         = {Machine review of arXiv:2501.13767}
}
abstract

Recent advances in neural models have shown considerable promise in solving Traveling Salesman Problems (TSPs) without relying on much hand-crafted engineering. However, while non-autoregressive (NAR) approaches benefit from faster inference through parallelism, they typically deliver solutions of inferior quality compared to autoregressive ones. To enhance the solution quality while maintaining fast inference, we propose DEITSP, a diffusion model with efficient iterations tailored for TSP that operates in a NAR manner. Firstly, we introduce a one-step diffusion model that integrates the controlled discrete noise addition process with self-consistency enhancement, enabling optimal solution prediction through simultaneous denoising of multiple solutions. Secondly, we design a dual-modality graph transformer to bolster the extraction and fusion of features from node and edge modalities, while further accelerating the inference with fewer layers. Thirdly, we develop an efficient iterative strategy that alternates between adding and removing noise to improve exploration compared to previous diffusion methods. Additionally, we devise a scheduling framework to progressively refine the solution space by adjusting noise levels, facilitating a smooth search for optimal solutions. Extensive experiments on real-world and large-scale TSP instances demonstrate that DEITSP performs favorably against existing neural approaches in terms of solution quality, inference latency, and generalization ability. Our code is available at $\href{https://github.com/DEITSP/DEITSP}{https://github.com/DEITSP/DEITSP}$.

Figures

Figures reproduced from arXiv: 2501.13767 by the authors.

Figure 1
Figure 1. The proposed diffusion model learns to directly [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The network takes node coordinates 𝑣𝑖 , noisy ad￾jacency matrix 𝑎𝑡𝑖 𝑗 and time step 𝑡 as inputs to predicts the heatmaps 𝑎˜0𝑖 𝑗 . Mix refers to Eq. (5) and (8), while FFN and Norm is Feed Forward and Layer Normalization used in Vaswani et al. [45] 3.4 Iterative Denoising and Noise Scheduling In this section, we present the inference process of DEITSP. First, we use a greedy strategy to decode the heatmaps predicted … view at source ↗
Figure 3
Figure 3. DDIM iteratively predicts 𝑎𝑡−1 to progress the chain of mapping noise into data, discarding previously estimated 𝑎˜0. In contrast, our method aggregates the outputs of the diffusion model at multiple steps and decodes all outputs 𝑎˜ 𝑡 0 to improve solution quality. states. We present experiments on scheduling methods to verify this in Section 4.5 and provide detailed comparisons in Appendix B. Algorithm 2 outlines t… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Comparison of the performance of DEITSP with [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 6
Figure 6. Figure 6: Visualization of solutions produced by DEITSP us [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 8
Figure 8. Figure 8: Visualization of solutions produced by DEITSP us [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]
Figure 9
Figure 9. Figure 9: Visualization of noise addition process on the TSP20 instance. [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problems

    cs.NE 2026-01 conditional novelty 4.0 of 10

    HeatACO, a Max-Min Ant System decoder biased by a neural heatmap prior, reaches 0.11%/0.23%/1.15% optimality gaps on TSP500/1K/10K with seconds-to-minutes CPU decoding time.

Reference graph

Works this paper leans on

62 extracted references · 54 canonical work pages · cited by 1 Pith paper

  1. [1]

    Applegate, Robert E

    David L. Applegate, Robert E. Bixby, Vašek Chvátal, and William John Cook. 2007. The Traveling Salesman Problem: A Computational Study . Princeton University Press

    work page 2007

  2. [2]

    Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. 2021. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems 34 (2021), 17981–17993

    work page 2021

  3. [3]

    Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. Neural ma- chine translation by jointly learning to align and translate. In Proceedings of International Conference on Learning Representations

    work page 2015

  4. [4]

    Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Adam Meyerson. 2004. Approxi- mation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows. In Proceedings of the Annual ACM Symposium on Theory of Computing . 166–174

    work page 2004

  5. [5]

    Richard Bellman. 1962. Dynamic programming treatment of the travelling sales- man problem. J. ACM 9, 1 (1962), 61–63

    work page 1962

  6. [6]

    Irwan Bello, Hieu Pham, Quoc Viet Le, Mohammad Norouzi, and Samy Ben- gio. 2017. Neural combinatorial optimization with reinforcement learning. In Proceedings of International Conference on Learning Representations Workshop

    work page 2017

  7. [7]

    Xavier Bresson and Thomas Laurent. 2021. The transformer network for the traveling salesman problem. arXiv:2103.03012

    arXiv 2021

  8. [8]

    Ting Chen, Ruixiang Zhang, and Geoffrey Hinton. 2023. Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioning. In The Eleventh International Conference on Learning Representations . https://openreview.net/ forum?id=3itjR9QxFw

    work page 2023

Show all 62 references
  1. [9]

    Marielle Christiansen, Kjetil Fagerholt, and David Ronen. 2004. Ship routing and scheduling: status and perspectives. Transportation Science 38 (2004), 1–18

    2004

  2. [10]

    Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis- Martin Rousseau. 2018. Learning heuristics for the TSP by policy gradient. In Proceedings of Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 170–181

    2018

  3. [11]

    Zhanghua Fu, Kaibin Qiu, and Hongyuan Zha. 2021. Generalize a small pre- trained model to arbitrarily large TSP instances. In Proceedings of the AAAI Conference on Artificial Intelligence. 7474–7482

    2021

  4. [12]

    Chengrui Gao, Haopu Shang, Ke Xue, Dong Li, and Chao Qian. 2023. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. arXiv preprint arXiv:2308.14104 (2023)

    2023 arXiv

  5. [13]

    Michael Randolph Garey and David Stifler Johnson. 1990. Computers and In- tractability; A Guide to the Theory of NP-Completeness . W. H. Freeman & Co

    1990

  6. [14]

    Yong Liang Goh, Zhiguang Cao, Yining Ma, Yanfei Dong, Mohammed Haroon Dupty, and Wee Sun Lee. 2024. Hierarchical Neural Constructive Solver for Real-world TSP Scenarios. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining . 2120–2131. KDD ’2...

    2024

  7. [15]

    Alexandros Graikos, Nikolay Malkin, Nebojsa Jojic, and Dimitris Samaras. 2022. Diffusion models as plug-and-play priors. Advances in Neural Information Pro- cessing Systems 35 (2022), 14715–14728

    2022

  8. [16]

    Keld Helsgaun. 2017. An extension of the Lin–Kernighan–Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University (2017), 24–50

    2017

  9. [17]

    Jonathan Ho, Ajay Jain, and Pieter Abbeel. 2020. Denoising diffusion probabilistic models. Advances in neural information processing systems 33 (2020), 6840–6851

    2020

  10. [18]

    Md Shamim Hussain, Mohammed J Zaki, and Dharmashankar Subramanian

  11. [19]

    Yuan Jiang, Zhiguang Cao, Yaoxin Wu, Wen Song, and Jie Zhang. 2023. Ensemble- based deep reinforcement learning for vehicle routing problems under distribu- tion shift. Advances in Neural Information Processing Systems 36 (2023)

    2023

  12. [20]

    Yuan Jiang, Zhiguang Cao, Yaoxin Wu, and Jie Zhang. 2023. Multi-view graph contrastive learning for solving vehicle routing problems. In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence (Proceedings of Machine Learning Research, Vol. 216) , ...

    2023

  13. [21]

    Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. 2023. Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37. 8132–8140

    2023

  14. [22]

    Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Lau- rent

    Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Lau- rent. 2022. Learning the travelling salesperson problem requires rethinking generalization. Constraints 27 (2022), 70–98

    2022

  15. [23]

    Joshi, Thomas Laurent, and Xavier Bresson

    Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. 2019. An efficient graph convolutional network technique for the travelling salesman problem. In Proceedings of INFORMS Annual Meeting, Session on Boosting Combinatorial Optimization using Machine Learning . 1–17

    2019

  16. [24]

    Minseop Jung, Jaeseung Lee, and Jibum Kim. 2023. A Lightweight CNN- Transformer Model for Learning Traveling Salesman Problems. arXiv preprint arXiv:2305.01883 (2023)

    2023 arXiv

  17. [25]

    Minsu Kim, Jinkyoo Park, and Joungho Kim. 2021. Learning Collaborative Policies to Solve NP-hard Routing Problems. In Proceedings of Advances in Neural Information Processing Systems, Vol. 34. 10418–10430

    2021

  18. [26]

    Minsu Kim, Junyoung Park, and Jinkyoo Park. 2022. Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. In Proceedings of Advances in Neural Information Processing Systems , Vol. 35. 1936–1949

    2022

  19. [27]

    Gözde Kizilateş and Fidan Nuriyeva. 2013. On the nearest neighbor algorithms for the traveling salesman problem. In Advances in Computational Science, Engineer- ing and Information Technology: Proceedings of the Third International Conference on Computational Science, Engineer...

    2013

  20. [28]

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

    2019

  21. [29]

    Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. 2020. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. In Proceedings of Advances in Neural Information Processing Systems. 21188–21198

    2020

  22. [30]

    Kaiwen Li, Tao Zhang, Rui Wang, Wenjian Qin, Hui-hui He, and Hong Huang

  23. [31]

    Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. 2024. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems 36 (2024)

    2024

  24. [32]

    Shen Lin and Brian W Kernighan. 1973. An effective heuristic algorithm for the traveling-salesman problem. Operations research 21, 2 (1973), 498–516

    1973

  25. [33]

    Simian Luo, Yiqin Tan, Longbo Huang, Jian Li, and Hang Zhao. 2023. Latent consistency models: Synthesizing high-resolution images with few-step inference. arXiv preprint arXiv:2310.04378 (2023)

    2023 arXiv

  26. [34]

    Ning Ma and Yishun Dou. 2024. Semi-supervised Diffusion Solver for Travelling Salesman Problem. https://openreview.net/forum?id=0u9uvPdRgV

    2024

  27. [35]

    Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. 2021. Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer. In Proceedings of Advances in Neural Information Processing Systems, Vol. 34. 11096–11107

    2021

  28. [36]

    Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence V. Snyder

  29. [37]

    Alex Nowak, David Folqué, and Joan Bruna. 2018. Divide and conquer Networks. In Proceedings of International Conference on Learning Representations

    2018

  30. [38]

    Naoya Onizawa, Kota Katsuki, Duckgyu Shin, Warren J Gross, and Takahiro Hanyu. 2022. Fast-converging simulated annealing for Ising models based on integral stochastic computing. IEEE Transactions on Neural Networks and Learning Systems 34, 12 (2022), 10999–11005

    2022

  31. [39]

    Manfred Padberg and Giovanni Rinaldi. 1991. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33 (1991), 60–100

    1991

  32. [40]

    Qiu Ran, Yankai Lin, Peng Li, and Jie Zhou. 2021. Guiding non-autoregressive neural machine translation decoding with reordering information. In Proceedings of the AAAI Conference on Artificial Intelligence . 13727–13735

    2021

  33. [41]

    Gerhard Reinelt. 1991. TSPLIB—A traveling salesman problem library. ORSA journal on computing 3, 4 (1991), 376–384. https://www.math.uwaterloo.ca/tsp/ index.html

    1991

  34. [42]

    Jiaming Song, Chenlin Meng, and Stefano Ermon. 2020. Denoising Diffusion Implicit Models. arXiv:2010.02502 (October 2020). https://arxiv.org/abs/2010. 02502

    2020 arXiv

  35. [43]

    Yang Song, Prafulla Dhariwal, Mark Chen, and Ilya Sutskever. 2023. Consistency Models. arXiv preprint arXiv:2303.01469 (2023)

    2023 arXiv

  36. [44]

    Zhiqing Sun and Yiming Yang. 2023. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. In Proceedings of Advances in Neural Information Processing Systems

    2023

  37. [45]

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you Need. In Proceedings of Advances in Neural Information Processing Systems . 6000—-6010

    2017

  38. [46]

    Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. 2023. DiGress: Discrete Denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations . https://openreview.net/forum?id=UaAD-Nu86WX

    2023

  39. [47]

    Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. In Proceedings of Advances in Neural Information Processing Systems . 2692––2700

    2015

  40. [48]

    Lei Wang, Yubin Xiao, Jiechen Li, Xiang Feng, Qian Li, and Jialiang Yang. 2019. IIRWR: Internal inclined random walk with restart for lncRNA-Disease associa- tion prediction. IEEE Access 7 (2019), 54034–54041

    2019

  41. [49]

    Xuan Wu, Jizong Han, Di Wang, Pengyue Gao, Quanlong Cui, Liang Chen, Yanchun Liang, Han Huang, Heow Pueh Lee, Chunyan Miao, You Zhou, and Chunguo Wu. 2023. Incorporating Surprisingly Popular Algorithm and Euclidean distance-based adaptive topology into PSO.Swarm and Evolutiona...

    2023

  42. [50]

    Xuan Wu, Di Wang, Huanhuan Chen, Lele Yan, Yubin Xiao, Chunyan Miao, Hongwei Ge, Dong Xu, Yanchun Liang, Kangping Wang, et al . 2023. Neural Architecture Search for Text Classification With Limited Computing Resources Using Efficient Cartesian Genetic Programming. IEEE Transac...

    2023

  43. [51]

    Maskell, and You Zhou

    Xuan Wu, Di Wang, Lijie Wen, Yubin Xiao, Chunguo Wu, Yuesong Wu, Chaoyu Yu, Douglas L. Maskell, and You Zhou. 2024. Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives. arXiv:2406.00415 [cs.AI]

    2024 arXiv

  44. [52]

    Yubin Xiao, Di Wang, Huanhuan Chen, Boyang Li, Wei Pang, Xuan Wu, Hao Li, Dong Xu, Yanchun Liang, and You Zhou. 2023. Reinforcement learning- based non-autoregressive solver for traveling salesman problems. arXiv preprint arXiv:2308.00560 (2023)

    2023 arXiv

  45. [53]

    Yubin Xiao, Di Wang, Boyang Li, Mingzhao Wang, Xuan Wu, Changliang Zhou, and You Zhou. 2024. Distilling autoregressive models to obtain high-performance non-autoregressive solvers for vehicle routing problems with faster inference speed. In Proceedings of the AAAI Conference o...

    2024

  46. [54]

    Yubin Xiao, Di Wang, Xuan Wu, Yuesong Wu, Boyang Li, Wei Du, Liupu Wang, and You Zhou. 2024. Improving Generalization of Neural Vehicle Routing Problem Solvers Through the Lens of Model Architecture. arXiv preprint arXiv:2406.06652 (2024)

    2024 arXiv

  47. [55]

    Yubin Xiao, Zheng Xiao, Xiang Feng, Zhiping Chen, Linai Kuang, and Lei Wang

  48. [56]

    Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. 2021. Multi-Decoder Atten- tion Model with Embedding Glimpse for Solving Vehicle Routing Problems. In Proceeding of the AAAI Conference on Artificial Intelligence . 12042–12049

    2021

  49. [57]

    Zhe Xu, Zhixin Li, Qingwen Guan, Dingshui Zhang, Qiang Li, Junxiao Nan, Chunyang Liu, Wei Bian, and Jieping Ye. 2018. Large-scale order dispatch in on- demand ride-hailing platforms: A learning and planning approach. InProceedings of the 24th ACM SIGKDD international conferenc...

    2018

  50. [58]

    Yiwen Zhong, Juan Lin, Lijin Wang, and Hui Zhang. 2018. Discrete comprehensive learning particle swarm optimization algorithm with Metropolis acceptance criterion for traveling salesman problem. Swarm and Evolutionary Computation 42 (2018), 77–88. An Efficient Diffusion-based ...

    2018

  51. [2018]

    In Proceedings of Advances in Neural Information Processing Systems

    Reinforcement Learning for Solving the Vehicle Routing Problem. In Proceedings of Advances in Neural Information Processing Systems . 9861––9871

  52. [2020]

    BMC Bioinformatics 21 (2020), 1–22

    A novel computational model for predicting potential LncRNA-disease associations based on both direct and indirect features of LncRNA-disease pairs. BMC Bioinformatics 21 (2020), 1–22

    2020

  53. [2021]

    Zidonghua Xuebao/Acta Automatica Sinica 47 (2021), 2521–2537

    Research reviews of combinatorial optimization methods based on deep reinforcement learning. Zidonghua Xuebao/Acta Automatica Sinica 47 (2021), 2521–2537

    2021

  54. [2022]

    In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

    Global Self-Attention as a Replacement for Graph Convolution. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Pith tools

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