pith. machine review for the scientific record. sign in

arxiv: 2604.20236 · v1 · submitted 2026-04-22 · 💻 cs.LG

Recognition: unknown

Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

Bo-Cheng Lin , Yi Mei , Mengjie Zhang
Authors on Pith no claims yet

Pith reviewed 2026-05-10 01:09 UTC · model grok-4.3

classification 💻 cs.LG
keywords graph sparsificationtravelling salesman problemmachine learningcandidate graphTSP solvertwo-stage approachalpha-nearestPOPMUSIC
0
0 comments X

The pith

A two-stage machine-learning approach sparsifies TSP candidate graphs while retaining optimal-tour edges across distance types and sizes.

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

The paper establishes that forming the union of two strong heuristics first ensures high recall of edges needed for optimal tours, after which a single machine-learning model can safely remove many remaining edges to lower density. This matters because high-performance TSP solvers search only within candidate graphs, so excessive edges slow them down while missing optimal edges degrades solution quality. Experiments across TSPLIB instances with four distance types, five distributions, and sizes from 50 to 500 show the method keeps coverage high, works where prior neural sparsifiers fail outside Euclidean cases, and grows more effective as instances get larger.

Core claim

The authors establish that a two-stage process—union of α-Nearest and POPMUSIC to maximize recall of optimal edges, followed by a trained model that classifies and removes unnecessary edges—substantially reduces candidate-graph density while preserving high coverage, generalizes across distance types and distributions, outperforms recent neural methods restricted to Euclidean distances, and becomes increasingly valuable at larger scales where single-stage heuristics degrade.

What carries the argument

The two-stage sparsification pipeline: first the union graph from α-Nearest and POPMUSIC heuristics for high recall, then a machine-learning model trained to prune edges not belonging to any optimal tour.

If this is right

  • Candidate graphs become substantially sparser, allowing TSP solvers to search faster without loss of solution quality.
  • The approach maintains high coverage of optimal-tour edges across four distance types and five spatial distributions.
  • It outperforms recent neural sparsification methods that operate only on Euclidean instances.
  • Performance gains relative to single-stage heuristics increase as problem size grows from 50 to 500 cities.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same union-then-prune pattern could be tested on other combinatorial problems that rely on candidate graphs for local search.
  • Checking the model's edge-removal decisions against known optimal tours on synthetic non-TSPLIB distributions would reveal any hidden distribution-specific bias.
  • At scales beyond 500 cities the density reduction might enable exact or near-exact solving of instances that currently require heavy approximation.

Load-bearing premise

The machine-learning model trained on the union graph can reliably identify and remove edges that are never part of any optimal tour without introducing bias that harms coverage on unseen distributions or larger sizes.

What would settle it

An experiment on a large TSPLIB instance with non-Euclidean distances where the two-stage method's retained optimal edges fall below those kept by a single-stage heuristic, causing the solver to miss the known optimum.

Figures

Figures reproduced from arXiv: 2604.20236 by Bo-Cheng Lin, Mengjie Zhang, Yi Mei.

Figure 1
Figure 1. Figure 1: Single-stage vs. two-stage sparsification. Top: existing approaches apply heuristics or ML independently to the full graph. Bottom: our method first maximises recall via a heuristic union, then reduces density via learned pruning [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The five spatial distributions used in our benchmark (EUC_2D, N=100). Each distribution × distance type combination forms one TSP family. We test the two-stage method on a benchmark of twenty TSP families: four TSPLIB distance types (EUC_2D, MAN_2D, ATT, GEO) crossed with five spatial distributions ( [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Sensitivity of the pruning threshold η on the union base graph (N=100, validation set). Left: retained density (Edges/N). Right: optimal-tour coverage (%) [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Feature importance for the union base graph by instance family. Columns are the 20 TSP families; rows are LR, SVM, and XGBoost. Coloured segments show the share of each feature family. Source provenance dominates across all models and families [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Source provenance of extra-lost optimal edges in union mode. Each bar shows the share of coverage losses from dual-source edges (both generators), α-only edges, and POPMUSIC-only edges. Single-source edges, especially α-only, are over-represented among losses. Source provenance of lost edges [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Feature profiles of extra-lost optimal edges for the union base graph. Each column is one of the 20 TSP families; each row is one ML model. Each dot is one feature value of a lost optimal-tour edge; dots cluster where the model systematically misjudges. speedup (union + LR) without increasing the optimality gap; union + LR achieves the lowest gap among all candidate configurations tested, including the unp… view at source ↗
read the original abstract

High-performance TSP solvers like LKH search within a sparsified candidate graph rather than over all possible edges. Graph sparsification is non-trivial: keep too many edges and the solver wastes time; cut too many and it loses edges that belong to the optimal tour. The two leading heuristic methods, $\alpha$-Nearest and POPMUSIC, produce high-quality candidate graphs, but no single heuristic is both sparse and reliable across all instance sizes and distributions. Machine learning methods can potentially learn better sparsification models. However, existing approaches operate on the complete graph, which is expensive and mostly restricted to Euclidean distances. To address this issue, we propose a two-stage graph sparsification approach: Stage~1 takes the union of $\alpha$-Nearest and POPMUSIC to maximise recall; Stage~2 trains a single model to reduce density. We conducted experiments across four TSPLIB distance types, five spatial distributions, and problem sizes from 50 to 500. The two-stage approach substantially reduces candidate-graph density while retaining high coverage, generalises across distance types and distributions, outperforms recent neural sparsification methods that are restricted to Euclidean distances, and becomes increasingly valuable at larger scales where single-stage heuristics degrade.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 1 minor

Summary. The manuscript proposes a two-stage graph sparsification method for the Travelling Salesman Problem. Stage 1 constructs the union of α-Nearest and POPMUSIC candidate graphs to maximize recall of optimal-tour edges. Stage 2 trains a single machine-learning classifier on this union to prune non-optimal edges and reduce density. Experiments are reported across four TSPLIB distance types, five spatial distributions, and instance sizes 50–500; the authors claim the method retains high coverage, generalizes beyond Euclidean distances, outperforms prior neural sparsifiers, and grows more valuable at larger scales.

Significance. If the generalization and scaling claims are substantiated, the work could improve practical TSP solvers such as LKH by supplying sparser yet reliable candidate graphs across diverse instance families. The two-stage design usefully combines existing heuristics with learned pruning and avoids the computational cost of operating on the complete graph. The breadth of tested distance types and distributions is a positive feature, but the absence of quantitative tables, error bars, and scaling results beyond n = 500 limits the strength of the central empirical claims.

major comments (3)
  1. [Abstract] Abstract: the assertion that the method 'becomes increasingly valuable at larger scales where single-stage heuristics degrade' is unsupported by the reported experiments, which are limited to n ≤ 500; no results, ablations, or analysis for n > 500 are provided to justify the extrapolation.
  2. [Experimental section] Experimental section: the manuscript provides no description of the train/validation/test split strategy, the precise feature set fed to the stage-2 classifier, or any ablation that isolates the contribution of the learned pruner from the union graph itself. Without these details the generalization claim across distributions cannot be rigorously assessed.
  3. [Results] Results: the abstract states that the two-stage approach 'substantially reduces candidate-graph density while retaining high coverage' yet no quantitative tables, coverage percentages, density ratios, error bars, or statistical tests are referenced; this absence prevents evaluation of the magnitude and reliability of the reported gains.
minor comments (1)
  1. [Abstract] The abstract uses the phrase 'union graph (α-nearest + POPMUSIC)' without immediately defining the concrete values of α or the POPMUSIC parameters employed; a short parenthetical clarification would improve readability.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive feedback. We address each major comment below and will make the indicated revisions to improve clarity, rigor, and support for the claims.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the assertion that the method 'becomes increasingly valuable at larger scales where single-stage heuristics degrade' is unsupported by the reported experiments, which are limited to n ≤ 500; no results, ablations, or analysis for n > 500 are provided to justify the extrapolation.

    Authors: We agree that no experiments for n > 500 are presented and that the extrapolation in the abstract is not directly supported by new data. The statement was motivated by the observed trend within n=50–500 that single-stage heuristics produce progressively denser candidate graphs while the two-stage pruner maintains coverage. To avoid overclaiming, we will revise the abstract to remove the phrase about larger scales and instead note that the approach 'maintains high coverage while reducing density across tested instance sizes up to 500.' We will also add a short paragraph in the discussion analyzing the scaling trend visible in the existing results. revision: partial

  2. Referee: [Experimental section] Experimental section: the manuscript provides no description of the train/validation/test split strategy, the precise feature set fed to the stage-2 classifier, or any ablation that isolates the contribution of the learned pruner from the union graph itself. Without these details the generalization claim across distributions cannot be rigorously assessed.

    Authors: These details were inadvertently omitted from the submitted manuscript. The split was performed instance-wise (70/15/15 train/validation/test) with separate generation per distribution and distance type to prevent leakage. The stage-2 classifier uses a feature vector consisting of normalized edge length, rank within α-nearest and POPMUSIC neighborhoods, local edge density, and global instance statistics. We will insert a new subsection detailing the split procedure, the complete feature list with definitions, and an ablation comparing the union graph alone versus the full two-stage pipeline. This will directly support the generalization claims. revision: yes

  3. Referee: [Results] Results: the abstract states that the two-stage approach 'substantially reduces candidate-graph density while retaining high coverage' yet no quantitative tables, coverage percentages, density ratios, error bars, or statistical tests are referenced; this absence prevents evaluation of the magnitude and reliability of the reported gains.

    Authors: We acknowledge the results section relies on figures without accompanying tables or statistical summaries. We will add a table reporting mean coverage percentages and density ratios (with standard deviations across 10 random seeds) for each distance type and spatial distribution. We will also include Wilcoxon signed-rank tests comparing the two-stage method against the union baseline and prior neural sparsifiers. These quantitative additions will allow direct assessment of the magnitude and reliability of the improvements. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical ML evaluation on held-out TSP instances

full rationale

The paper proposes a two-stage heuristic+ML pipeline for TSP candidate-graph construction and evaluates it via standard train/test splits on TSPLIB and synthetic instances. No mathematical derivation, uniqueness theorem, or ansatz is invoked whose validity reduces to the fitted model outputs or to self-citations. Stage-1 is the explicit union of two published heuristics; Stage-2 is a supervised classifier whose training objective (edge classification) is distinct from the reported coverage/density metrics. All performance numbers are obtained by applying the trained model to unseen instances, satisfying the self-contained benchmark criterion.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; the approach implicitly assumes standard supervised learning on graph features and that the union heuristic already captures near-optimal recall.

pith-pipeline@v0.9.0 · 5515 in / 1199 out tokens · 50861 ms · 2026-05-10T01:09:15.861704+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 31 canonical work pages · 1 internal anchor

  1. [1]

    Artificial Intelligence Review 58(9), 267 (2025).https://doi.org/10.1007/s10462-025-11267-x

    Alanzi, E., Menai, M.E.B.: Solving the traveling salesman problem with machine learning: a review of recent advances and challenges. Artificial Intelligence Review 58(9), 267 (2025).https://doi.org/10.1007/s10462-025-11267-x

    work page doi:10.1007/s10462-025-11267-x 2025

  2. [2]

    Applegate, D., Bixby, R., Chvatal, V., Cook, W.: Concorde TSP solver (2006)

    2006

  3. [3]

    Bello, I., Pham, H., Le, Q.V., Norouzi, M., Bengio, S.: Neural Combinatorial Optimization with Reinforcement Learning (2017), arXiv:1611.09940 [cs]

    work page Pith review arXiv 2017

  4. [4]

    Mathematical Programming Computation16(4), 599–628 (2024).https://doi.org/10.1007/s12532-024-00262-y

    Cook, W., Helsgaun, K., Hougardy, S., Schroeder, R.T.: Local elimination in the traveling salesman problem. Mathematical Programming Computation16(4), 599–628 (2024).https://doi.org/10.1007/s12532-024-00262-y

    work page doi:10.1007/s12532-024-00262-y 2024

  5. [5]

    Information Processing Letters 24(5), 339–342 (1987).https://doi.org/10.1016/0020-0190(87)90160-8

    Dillencourt, M.B.: Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations. Information Processing Letters 24(5), 339–342 (1987).https://doi.org/10.1016/0020-0190(87)90160-8

    work page doi:10.1016/0020-0190(87)90160-8 1987

  6. [6]

    Computing in Geometry and Topology3(1), 1:1–1:23 (2024)

    Fekete, S., Keldenich, P., Krupke, D., Niehs, E.: Edge Sparsification for Geometric Tour Problems. Computing in Geometry and Topology3(1), 1:1–1:23 (2024). https://doi.org/10.57717/cgt.v3i1.20

    work page doi:10.57717/cgt.v3i1.20 2024

  7. [7]

    https://doi.org/10.48550/arXiv.2104.09345, arXiv:2104.09345 [cs]

    Fitzpatrick, J., Ajwani, D., Carroll, P.: Learning to Sparsify Travelling Sales- man Problem Instances (2021). https://doi.org/10.48550/arXiv.2104.09345, arXiv:2104.09345 [cs]

    work page doi:10.48550/arxiv.2104.09345 2021

  8. [8]

    Proceedings of the AAAI Conference on Artificial Intelligence35(8), 7474–7482 (May 2021).https://doi.org/10.1609/aaai.v35i8

    Fu, Z.H., Qiu, K.B., Zha, H.: Generalize a Small Pre-trained Model to Arbi- trarily Large TSP Instances. Proceedings of the AAAI Conference on Artificial Intelligence35(8), 7474–7482 (May 2021).https://doi.org/10.1609/aaai.v35i8. 16916, https://ojs.aaai.org/index.php/AAAI/article/view/16916, number: 8

    work page doi:10.1609/aaai.v35i8 2021

  9. [9]

    In: Advances in Neural Information Processing Systems

    Gasse, M., Chetelat, D., Ferroni, N., Charlin, L., Lodi, A.: Exact Combinatorial Optimization with Graph Convolutional Neural Networks. In: Advances in Neural Information Processing Systems. vol. 32. Curran Associates, Inc. (2019)

    2019

  10. [10]

    In: Proceed- ings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

    Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., Kerschke, P.: On the potential of normalized TSP features for automated algorithm selection. In: Proceed- ings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. pp. 1–15. FOGA ’21, Association for Computing Machinery, New York, NY, USA (2021).https://doi.org/10.1145/3450218.3477308

    work page doi:10.1145/3450218.3477308 2021

  11. [11]

    Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., Kerschke, P.: A study on theeffectsofnormalizedTSPfeaturesforautomatedalgorithmselection.Theoretical Computer Science940, 123–145 (2023).https://doi.org/10.1016/j.tcs.2022. 10.019

    work page doi:10.1016/j.tcs.2022 2023

  12. [12]

    (eds.) Parallel Problem Solving from Nature – PPSN XVIII

    Heins, J., Schäpermeier, L., Kerschke, P., Whitley, D.: Dancing to the State of the Art? In: Affenzeller, M., Winkler, S.M., Kononova, A.V., Trautmann, H., Tušar, T., Machado, P., Bäck, T. (eds.) Parallel Problem Solving from Nature – PPSN XVIII. pp. 100–115. Springer Nature Switzerland, Cham (2024).https: //doi.org/10.1007/978-3-031-70055-2_7

    work page doi:10.1007/978-3-031-70055-2_7 2024

  13. [13]

    European Journal of Operational Research126(1), 106–130 (2000)

    Helsgaun, K.: An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research126(1), 106–130 (2000)

    2000

  14. [14]

    In: Kratsch, D., Todinca, I

    Hougardy, S., Schroeder, R.T.: Edge Elimination in TSP Instances. In: Kratsch, D., Todinca, I. (eds.) Graph-Theoretic Concepts in Computer Science. pp. 275–

  15. [15]

    Springer International Publishing, Cham (2014).https://doi.org/10.1007/ 978-3-319-12340-0_23

    2014

  16. [16]

    Hudson, B., Li, Q., Malencia, M., Prorok, A.: Graph Neural Network Guided Local Search for the Traveling Salesperson Problem (2022).https://doi.org/10.48550/ arXiv.2110.05291, arXiv:2110.05291 [cs, stat] 16 Bo-Cheng Lin, Yi Mei, Mengjie Zhang

    work page arXiv 2022

  17. [17]

    LIPIcs, Volume 210, CP 2021210, 33:1–33:21 (2021)

    Joshi, C.K., Cappart, Q., Rousseau, L.M., Laurent, T.: Learning TSP Requires Rethinking Generalization. LIPIcs, Volume 210, CP 2021210, 33:1–33:21 (2021). https://doi.org/10.4230/LIPICS.CP.2021.33

    work page doi:10.4230/lipics.cp.2021.33 2021

  18. [18]

    48550/arXiv.1906.01227, http://arxiv.org/abs/1906.01227, arXiv:1906.01227 [cs, stat]

    Joshi, C.K., Laurent, T., Bresson, X.: An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (Oct 2019).https://doi.org/10. 48550/arXiv.1906.01227, http://arxiv.org/abs/1906.01227, arXiv:1906.01227 [cs, stat]

    work page arXiv 2019

  19. [19]

    In: Proceedings of the Genetic and Evolutionary Computation Conference Companion

    Kerschke, P., Bossek, J., Trautmann, H.: Parameterization of state-of-the-art perfor- mance indicators: a robustness study based on inexact TSP solvers. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion. pp. 1737–

  20. [20]

    GECCO ’18, Association for Computing Machinery, New York, NY, USA (2018).https://doi.org/10.1145/3205651.3208233

    work page doi:10.1145/3205651.3208233 2018

  21. [21]

    Evolutionary Computation 26(4), 597–620 (2018).https://doi.org/10.1162/evco_a_00215

    Kerschke, P., Kotthoff, L., Bossek, J., Hoos, H.H., Trautmann, H.: Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary Computation 26(4), 597–620 (2018).https://doi.org/10.1162/evco_a_00215

    work page doi:10.1162/evco_a_00215 2018

  22. [22]

    Kool, W., Hoof, H.v., Welling, M.: Attention, Learn to Solve Routing Problems! (2019).https://doi.org/10.48550/arXiv.1803.08475, arXiv:1803.08475

    work page Pith review doi:10.48550/arxiv.1803.08475 2019

  23. [23]

    In: Dhaenens, C., Jourdan, L., Marmion, M.E

    Kotthoff, L., Kerschke, P., Hoos, H., Trautmann, H.: Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection. In: Dhaenens, C., Jourdan, L., Marmion, M.E. (eds.) Learning and Intelligent Optimization. pp. 202–217. Springer International Publishing, Cham (2015).https://doi.org/10. 1007/978-3-319-19084-6_18

    2015

  24. [24]

    Krasnogor, N., Plata, L., Moscato, P., Norman, M.: A New Hybrid Heuristic For Large Geometric Traveling Salesman Problems Based On The Delaunay Triangula- tion (1999)

    1999

  25. [25]

    Sparse Dynamic Discretization Discovery via Arc- Dependent Time Discretizations.Comput

    Letchford, A.N., Pearson, N.A.: Good triangulations yield good tours. Computers & Operations Research35(2), 638–647 (2008).https://doi.org/10.1016/j.cor. 2006.03.025

    work page doi:10.1016/j.cor 2008

  26. [26]

    Lischka, A., Wu, J., Basso, R., Chehreghani, M.H., Kulcsar, B.: Travelling Salesman Problem Goes Sparse With Graph Neural Networks (2023)

    2023

  27. [27]

    Lischka, A., Wu, J., Basso, R., Chehreghani, M.H., Kulcsár, B.: Less Is More – On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP (2024).https://doi.org/10.48550/ARXIV.2403.17159

    work page doi:10.48550/arxiv.2403.17159 2024

  28. [28]

    Proceedings of the 7th Internatinal Conferencenon Genetic Algorithms pp

    NAGATA, Y.: Edge Assembly Crossover:A High-power Genetic Algorithm for the Traveling Salesman Problem. Proceedings of the 7th Internatinal Conferencenon Genetic Algorithms pp. 450–457 (1997)

    1997

  29. [29]

    Qiu, R., Sun, Z., Yang, Y.: DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. Advances in Neural Information Processing Systems35, 25531–25546 (Dec 2022),https://proceedings.neurips.cc/paper_files/paper/ 2022/hash/a3a7387e49f4de290c23beea2dfcdc75-Abstract-Conference.html

    2022

  30. [30]

    In: Dorigo, M., Di Caro, G., Sampels, M

    Randall, M., Montgomery, J.: Candidate Set Strategies for Ant Colony Optimisation. In: Dorigo, M., Di Caro, G., Sampels, M. (eds.) Ant Algorithms. pp. 243–249. Springer, Berlin, Heidelberg (2002).https://doi.org/10.1007/3-540-45724-0_ 22

    work page doi:10.1007/3-540-45724-0_ 2002

  31. [31]

    ORSA Journal on Computing (1991).https://doi.org/10.1287/ijoc.3.4.376

    Reinelt, G.: TSPLIB–A Traveling Salesman Problem Library. ORSA Journal on Computing (1991).https://doi.org/10.1287/ijoc.3.4.376

    work page doi:10.1287/ijoc.3.4.376 1991

  32. [32]

    OR Spectrum43(3) (2021)

    Sun, Y., Ernst, A., Li, X., Weiner, J.: Generalization of machine learning for problem reduction: a case study on travelling salesman problems. OR Spectrum43(3) (2021). https://doi.org/10.1007/s00291-020-00604-x ML for Two-Stage TSP Graph Sparsification 17

    work page doi:10.1007/s00291-020-00604-x 2021

  33. [33]

    IEEE Transactions on Pattern Analysis and Machine Intelligence43(5), 1746–1760 (2021).https: //doi.org/10.1109/TPAMI.2019.2954827

    Sun, Y., Li, X., Ernst, A.: Using Statistical Measures and Machine Learning for Graph Reduction to Solve Maximum Weight Clique Problems. IEEE Transactions on Pattern Analysis and Machine Intelligence43(5), 1746–1760 (2021).https: //doi.org/10.1109/TPAMI.2019.2954827

    work page doi:10.1109/tpami.2019.2954827 2021

  34. [34]

    Sun, Z., Yang, Y.: DIFUSCO: Graph-based Diffusion Solvers for Combina- torial Optimization. Advances in Neural Information Processing Systems36 (Feb 2024), https://proceedings.neurips.cc/paper_files/paper/2023/hash/ 0ba520d93c3df592c83a611961314c98-Abstract-Conference.html

    2024

  35. [35]

    European Journal of Operational Research272(2), 420–429 (2019).https://doi

    Taillard, É.D., Helsgaun, K.: POPMUSIC for the travelling salesman problem. European Journal of Operational Research272(2), 420–429 (2019).https://doi. org/10.1016/j.ejor.2018.06.039

    work page doi:10.1016/j.ejor.2018.06.039 2019

  36. [36]

    Taillard, É.D., Voss, S.: Popmusic – Partial Optimization Metaheuristic under Spe- cial Intensification Conditions.https://doi.org/10.1007/978-1-4615-1507-4_ 27

    work page doi:10.1007/978-1-4615-1507-4_

  37. [37]

    In: 2024 IEEE International Conference on Progress in Informatics and Computing (PIC)

    Tuononen, J., Fränti, P.: Modified Greedy Delaunay Graph-Based Method for TSP Initialization. In: 2024 IEEE International Conference on Progress in Informatics and Computing (PIC). pp. 177–183. IEEE, Shanghai, China (2024).https://doi. org/10.1109/PIC62406.2024.10892746

    work page doi:10.1109/pic62406.2024.10892746 2024

  38. [38]

    In: Sellmann, M., Tierney, K

    Vo, T.Q.T., Baiou, M., Nguyen, V.H., Weng, P.: Improving Subtour Elimination Constraint Generation in Branch-and-Cut Algorithms for the TSP with Machine Learning. In: Sellmann, M., Tierney, K. (eds.) Learning and Intelligent Optimization. pp. 537–551. Springer International Publishing, Cham (2023).https://doi.org/ 10.1007/978-3-031-44505-7_36

    work page doi:10.1007/978-3-031-44505-7_36 2023

  39. [39]

    Wang, L., Zheng, J., Xiong, Z., Li, C., He, K.: Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems (2025).https://doi.org/ 10.48550/arXiv.2505.15862, arXiv:2505.15862 [cs]

    work page doi:10.48550/arxiv.2505.15862 2025

  40. [40]

    Expert Systems with Applications42(12), 5150–5162 (2015)

    Wang, Y.: An approximate method to compute a sparse graph for traveling salesman problem. Expert Systems with Applications42(12), 5150–5162 (2015). https: //doi.org/10.1016/j.eswa.2015.02.037

    work page doi:10.1016/j.eswa.2015.02.037 2015

  41. [41]

    In: Advances in Neural Information Processing Systems

    Xin, L., Song, W., Cao, Z., Zhang, J.: NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem. In: Advances in Neural Information Processing Systems. vol. 34, pp. 7472–7483. Curran Associates, Inc. (2021)

    2021

  42. [42]

    URLhttps://doi.org/10.1016/j.knosys.2022.110144

    Zheng, J., He, K., Zhou, J., Jin, Y., Li, C.M.: Reinforced Lin–Kernighan–Helsgaun algorithms for the traveling salesman problems. Knowledge-Based Systems260, 110144 (2023).https://doi.org/10.1016/j.knosys.2022.110144

    work page doi:10.1016/j.knosys.2022.110144 2023

  43. [43]

    https://doi.org/10.48550/arXiv.1809.10469, arXiv:1809.10469 [cs]

    Zhong, X.: Probabilistic Analysis of Edge Elimination for Euclidean TSP (2024). https://doi.org/10.48550/arXiv.1809.10469, arXiv:1809.10469 [cs]

    work page doi:10.48550/arxiv.1809.10469 2024

  44. [44]

    Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks

    Zhou, C., Lin, X., Wang, Z., Zhang, Q.: Learning to Reduce Search Space for Generalizable Neural Routing Solver (2025).https://doi.org/10.48550/arXiv. 2503.03137, arXiv:2503.03137 [cs]

    work page internal anchor Pith review doi:10.48550/arxiv 2025