Lune

CVPR Findings2026

Efficient Discrete Diffusion Model for Scalable Multi-Objective Traveling Salesman Problem

Dawei Su, Zhanhong Fang, Junyi Luo, Debing Wang, Jinbiao Chen, Zizhen Zhang

Abstract

The Multi-Objective Traveling Salesman Problem (MOTSP), a prominent multi-objective combinatorial optimization challenge, has witnessed the development of various methods, especially for modest-scale scenarios. While these methods can produce high-quality solutions within a reasonable time, they may struggle to maintain the original quality as instances scale up to problems with 500 to 1000 points. This paper investigates the potential of emerging discrete diffusion models with highly expressive generative capabilities in tackling large-scale MOTSP instances. These models learn to enhance and refine heatmaps to generate solutions under weight decomposition. Moreover, to accelerate speed and optimize memory usage in the reverse diffusion process, we introduce novel denoising strategies during inference. Experimental results show that our approach not only matches the performance of advanced methods in smaller scenarios but also excels in larger problems without requiring training at the same scale. Beyond its applicability, our customized denoising strategies significantly accelerate the entire solving process, addressing a notable limitation of diffusion models.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Diffusion Models as Plug-and-Play Priors cites Denoising Diffusion Probabilistic Models
  • POMO: Policy Optimization with Multiple Optima for Reinforcement Learning cites A Learning-based Iterative Method for Solving Vehicle Routing Problems
  • DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization cites Diffusion Models as Plug-and-Play Priors
  • DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization cites POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
  • DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization cites A Learning-based Iterative Method for Solving Vehicle Routing Problems
  • DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization cites Denoising Diffusion Probabilistic Models
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on11

  1. Denoising Diffusion Probabilistic ModelsJonathan Ho, Ajay Jain, Pieter AbbeelNeurIPS 2020 · 35,902 citations
  2. POMO: Policy Optimization with Multiple Optima for Reinforcement LearningYeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon et al.NeurIPS 2020 · 731 citations
  3. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial OptimizationZhiqing Sun, Yiming YangNeurIPS 2023 · 356 citations
  4. Diffusion Models as Plug-and-Play PriorsAlexandros Graikos, Nikolay Malkin, Nebojsa Jojic, Dimitris SamarasNeurIPS 2022 · 323 citations
  5. A Learning-based Iterative Method for Solving Vehicle Routing ProblemsHao Lu, Xingwen Zhang, Shuang YangICLR 2020 · 270 citations

Related papers

  1. An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman ProblemMingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao et al.KDD 2025 · 7 citations
  2. Generation as Search Operator for Test-Time Scaling of Diffusion-based Combinatorial OptimizationYang Li, Lvda Chen, Haonan Wang, Runzhong Wang et al.NeurIPS 2025 · 13 citations
  3. DIMES: A Differentiable Meta Solver for Combinatorial Optimization ProblemsRuizhong Qiu, Zhiqing Sun, Yiming YangNeurIPS 2022 · 183 citations
  4. Generalize a Small Pre-trained Model to Arbitrarily Large TSP InstancesZhang-Hua Fu, Kai-Bin Qiu, Hongyuan ZhaAAAI 2021 · 247 citations
  5. Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion PlanningJinhao Liang, Sven Koenig, Ferdinando FiorettoAAAI 2026 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines