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.
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 on11
- Denoising Diffusion Probabilistic ModelsJonathan Ho, Ajay Jain, Pieter AbbeelNeurIPS 2020 · 35,902 citations
- POMO: Policy Optimization with Multiple Optima for Reinforcement LearningYeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon et al.NeurIPS 2020 · 731 citations
- DIFUSCO: Graph-based Diffusion Solvers for Combinatorial OptimizationZhiqing Sun, Yiming YangNeurIPS 2023 · 356 citations
- Diffusion Models as Plug-and-Play PriorsAlexandros Graikos, Nikolay Malkin, Nebojsa Jojic, Dimitris SamarasNeurIPS 2022 · 323 citations
- A Learning-based Iterative Method for Solving Vehicle Routing ProblemsHao Lu, Xingwen Zhang, Shuang YangICLR 2020 · 270 citations
Related papers
- An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman ProblemMingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao et al.KDD 2025 · 7 citations
- 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
- DIMES: A Differentiable Meta Solver for Combinatorial Optimization ProblemsRuizhong Qiu, Zhiqing Sun, Yiming YangNeurIPS 2022 · 183 citations
- Generalize a Small Pre-trained Model to Arbitrarily Large TSP InstancesZhang-Hua Fu, Kai-Bin Qiu, Hongyuan ZhaAAAI 2021 · 247 citations
- Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion PlanningJinhao Liang, Sven Koenig, Ferdinando FiorettoAAAI 2026 · 4 citations
