Research map / Learning theory and algorithms / Combinatorial and search optimization
Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Critiques heatmap-guided MCTS for large-scale TSP by showing a simple softmax-of-distance baseline (SoftDist) matches or beats learned heatmaps and that MCTS underperforms LKH-3 under a new Score metric.
Problem
Whether ML-generated heatmaps with surrogate losses actually help post-hoc MCTS for large-scale TSP, and how heatmap-guided MCTS compares with the LKH-3 heuristic.
Approach
Introduces SoftDist, a training-free heatmap that applies softmax to negated distances with one temperature tuned by grid search directly on the TSP objective, and a Score metric (ratio of LKH-3 gap to MCTS gap) for comparing guided MCTS against LKH-3 under identical hardware and time.
Key results
- SoftDist achieves a 1.44% gap on TSP-500, 2.20% on TSP-1000 and 3.13% on TSP-10000 with heatmap generation under 0.1 seconds, matching DIFUSCO's Pareto-optimal tradeoff while outperforming ATT-GCN, DIMES and UTSP on gap.
- Heatmap-guided MCTS methods achieve Scores below 10% on TSP-500 and TSP-1000 and about one-third on TSP-10000 relative to LKH-3 under default settings.
- Under alternative MCTS settings, a zero-input heatmap performs comparably to learned heatmaps, indicating limited heatmap influence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SoftDist instead of UTSP heatmaps | MCTS heatmap generation · TSP-500 | Gap: 3.41% -> 1.44% | Helped |
| Use SoftDist instead of UTSP heatmaps | MCTS heatmap generation · TSP-1000 | Gap: 4.40% -> 2.20% | Helped |
| Use SoftDist instead of UTSP heatmaps | MCTS heatmap generation · TSP-10000 | Gap | Helped |
| Use DIFUSCO instead of SoftDist heatmaps | MCTS heatmap generation · TSP-500 | Gap: 1.44% -> 0.51% | Helped |
| Use DIFUSCO instead of SoftDist heatmaps | MCTS heatmap generation · TSP-1000 | Gap: 2.20% -> 1.18% | Helped |
| Use DIFUSCO instead of SoftDist heatmaps | MCTS heatmap generation · TSP-10000 | Gap: 3.13% -> 2.77% | Helped |
| Use heatmap-guided MCTS instead of LKH-3 | TSP solving under matched resources and time constraints · TSP-500 | Score: 0.84% | Hurt |
| Use heatmap-guided MCTS instead of LKH-3 | TSP solving under matched resources and time constraints · TSP-1000 | Score: 4.17% | Hurt |
| Use heatmap-guided MCTS instead of LKH-3 | TSP solving under matched resources and time constraints · TSP-10000 | Score: 29.88% | Hurt |
| Replace the zero-input heatmap with SoftDist (ablation) | MCTS · TSP-500 | Score: 5.20% -> 5.32% | Helped |
| Replace the zero-input heatmap with SoftDist (ablation) | MCTS · TSP-1000 | Score: 11.72% -> 12.56% | Helped |
| Tune MCTS parameters and reduce the search time budget | Heatmap-guided MCTS · TSP-500 and TSP-1000 | Length | Helped |
Surprising findings
- A zero-input (uninformative) heatmap performs nearly as well as learned heatmaps under the alternative MCTS settings.
- A training-free softmax-of-distance heatmap with one tuned parameter outperforms most learned heatmap generators.
Limitations
- Evaluation focuses on 2D Euclidean TSP at specific scales (500, 1000, 10000) with a single MCTS framework.
- Comparisons with prior methods rely partly on reproduced or reported numbers, and DIFUSCO results were reproduced with possible overestimation of gaps.
Experimental setup
Datasets: TSP-500 TSP-1000 TSP-10000
Benchmarks: TSP-500 TSP-1000 TSP-10000
Metrics: tour length optimality gap inference time Score (LKH-3 gap / MCTS gap)
Baselines: ATT-GCN DIMES UTSP DIFUSCO LKH-3 Concorde EAN AM POMO+EAS
Builds on: MCTS LKH-3 DIFUSCO DIMES UTSP
Closest papers by meaning
- DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · similarity 0.88)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.87)
- Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization (NeurIPS 2024 · similarity 0.86)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.86)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.86)
- Efficient Combinatorial Optimization via Heat Diffusion (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.