Research map / Learning theory and algorithms / Combinatorial and search optimization
DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem
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.
Proposes DualOpt, combining a grid-based divide-and-conquer (LKH3 on grids with edge-breaking and grid merging) with a path-based neural sub-path optimizer to solve large-scale TSP up to 100K nodes.
Problem
Large-scale traveling salesman problem (up to 100,000 nodes), where heuristics are slow and learning-based solvers fail to scale or generalize beyond ~1,000 nodes.
Approach
Two complementary divide-and-conquer stages: an iterative grid-based decomposition (solved in parallel by LKH3, with an edge-breaking strategy that reduces node count by representing partial routes by endpoints) yields an initial tour, which is then refined by path-based sub-path re-optimization with an attention-based neural solver trained via REINFORCE on small graphs (len 10–50).
Key results
- On TSP100K, DualOpt reaches objective 230.83 with gap -1.40% vs LKH3 in 8.6m vs LKH3 14.9h (about 104x speed-up).
- On TSPLIB's 10 largest instances, DualOpt gaps range 0.03%–1.80% vs LKH3, while GLOP gaps range 3.15%–10.17%.
- Ablation: removing the path stage (DualOpt w/oPath) yields gaps of 0.04–0.25% on TSP5K–TSP100K-ish, while removing grid stage (w/oGrid, random insertion init) gives 2.87–5.36% gaps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DualOpt instead of LKH3 | TSP solver · TSP_random, TSP1K–TSP100K | Obj.: 23.31 vs 23.31; 32.89 -> 32.72; 51.52 -> 51.56; 72.96 -> 72.62; 103.28 -> 102.9; 164.08 -> 162.81; 234.098 -> 230.83 | Mixed |
| use DualOpt instead of LKH3 | TSP solver · TSPLIB largest instances | Obj.: LKH3 and DualOpt Obj. values are shown instance-by-instance in the TSPLIB comparative table | Mixed |
| add path-based divide-and-optimize to the grid-based method (ablation) | DualOpt · TSP_random | Obj.: 23.34 -> 23.31 (TSP1K); 234.2 -> 230.83 (TSP100K) | Helped |
| add grid-based divide-and-conquer instead of random-insertion initialization (ablation) | DualOpt · TSP_random | Obj.: 24.56 -> 23.31 (TSP1K); 240.82 -> 230.83 (TSP100K) | Helped |
| set N_iter to 5 rather than the selected setting (ablation) | DualOpt · TSP_random | Obj.: 23.31 -> 25.06 (TSP1K); 72.62 -> 74.94 (TSP10K); 102.9 -> 104.66 (TSP20K); 162.8 -> 163.4 (TSP50K); 231.4 -> 230.8 (TSP1 | Mixed |
| vary N_iter across the tested values (ablation) | DualOpt · TSP_random | Obj.: TSP1K: 23.31 (N_iter = 2) to 25.06 (N_iter = 5); TSP5K: 51.54 (N_iter = 2), 51.56 (N_iter = 3) | Mixed |
| reduce edge-breaking margin from m to 0.5m (ablation) | DualOpt · TSP_random | Obj.: 23.31 -> 23.38 (TSP1K); 32.72 -> 32.83 (TSP2K); 51.56 -> 51.8 (TSP5K); 72.62 -> 72.83 (TSP10K) | Mixed |
| increase edge-breaking margin from m to 2m (ablation) | DualOpt · TSP_random | Obj.: 23.31 -> 23.27 (TSP1K); 32.72 -> 32.75 (TSP2K); 51.56 -> 51.62 (TSP5K); 72.62 -> 72.76 (TSP10K) | Mixed |
Surprising findings
- DualOpt improves over LKH3 on TSP100K (-1.40% gap) despite LKH3 being the strongest heuristic baseline, and it is also better than LKH3 on most TSP_random sizes.
- Concorde is worse than LKH3 on TSP5K (+3.75% gap) despite being an exact solver, attributed to time limits in the reported comparison.
Limitations
- Sub-solver is LKH3 with default parameters, so the method depends on a traditional heuristic inside the pipeline.
- Gains are not uniform: DualOpt does not beat LKH3 on TSP5K (0.08% gap) and TSP1K ties with SIL.
- Parameter choices (N_iter, sub-path lengths, iterations) are set per scale by hand and the statistical significance of improvements is not tested.
Experimental setup
Datasets: TSP_random instances from Fu et al. and Pan et al. (TSP1K to TSP100K) TSPLIB (10 largest instances, >5,000 nodes)
Benchmarks: TSP_random (TSP1K-TSP100K) TSPLIB (10 largest instances)
Metrics: objective length gap to LKH3 (%) running time
Baselines: Concorde LKH3 POMO DIMES DIFUSCO SIL GCN-MCTS SoftDist H-TSP GLOP
Builds on: LKH3 Attention Model POMO GLOP
Closest papers by meaning
- ViTSP: A Vision Language Models Guided Framework for Large-Scale Traveling Salesman Problems (ICLR 2026 · similarity 0.90)
- H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem (AAAI 2023 · similarity 0.88)
- Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems (ICML 2024 · similarity 0.88)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.86)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.85)
- Destroy and Repair Using Hyper-Graphs for Routing (AAAI 2025 · similarity 0.84)
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.