DISCO: Efficient Diffusion Solver for large-scale Combinatorial Optimization problems
Combinatorial Optimization (CO) problems are fundamentally important in numerous real-world applications across diverse industries, notably computer graphics, characterized by entailing enormous solution space and demanding time-sensitive response. Despite recent advancements in neural solvers, thei...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2025-09-01
|
| Series: | Graphical Models |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1524070325000311 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849229279014944768 |
|---|---|
| author | Hang Zhao Kexiong Yu Yuhang Huang Renjiao Yi Chenyang Zhu Kai Xu |
| author_facet | Hang Zhao Kexiong Yu Yuhang Huang Renjiao Yi Chenyang Zhu Kai Xu |
| author_sort | Hang Zhao |
| collection | DOAJ |
| description | Combinatorial Optimization (CO) problems are fundamentally important in numerous real-world applications across diverse industries, notably computer graphics, characterized by entailing enormous solution space and demanding time-sensitive response. Despite recent advancements in neural solvers, their limited expressiveness struggles to capture the multi-modal nature of CO landscapes. While some research has adopted diffusion models, these methods sample solutions indiscriminately from the entire NP-complete solution space with time-consuming denoising processes, limiting scalability for large-scale problems. We propose DISCO, an efficient DIffusion Solver for large-scale Combinatorial Optimization problems that excels in both solution quality and inference speed. DISCO’s efficacy is twofold: First, it enhances solution quality by constraining the sampling space to a more meaningful domain guided by solution residues, while preserving the multi-modal properties of the output distributions. Second, it accelerates the denoising process through an analytically solvable approach, enabling solution sampling with very few reverse-time steps and significantly reducing inference time. This inference-speed advantage is further amplified by Jittor, a high-performance learning framework based on just-in-time compiling and meta-operators. DISCO delivers strong performance on large-scale Traveling Salesman Problems and challenging Maximal Independent Set benchmarks, with inference duration up to 5.38 times faster than existing diffusion solver alternatives. We apply DISCO to design 2D/3D TSP Art, enabling the generation of fluid stroke sequences at reduced path costs. By incorporating DISCO’s multi-modal property into a divide-and-conquer strategy, it can further generalize to solve unseen-scale instances out of the box. |
| format | Article |
| id | doaj-art-0315b454cdae48e1b9ef4099780d6a3d |
| institution | Kabale University |
| issn | 1524-0703 |
| language | English |
| publishDate | 2025-09-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Graphical Models |
| spelling | doaj-art-0315b454cdae48e1b9ef4099780d6a3d2025-08-22T04:55:54ZengElsevierGraphical Models1524-07032025-09-0114110128410.1016/j.gmod.2025.101284DISCO: Efficient Diffusion Solver for large-scale Combinatorial Optimization problemsHang Zhao0Kexiong Yu1Yuhang Huang2Renjiao Yi3Chenyang Zhu4Kai Xu5Wuhan University, Wuhan, ChinaNational University of Defense Technology, Changsha, ChinaNational University of Defense Technology, Changsha, ChinaNational University of Defense Technology, Changsha, ChinaNational University of Defense Technology, Changsha, China; Corresponding authors.National University of Defense Technology, Changsha, China; Xiangjiang Laboratory, Changsha, China; Corresponding authors.Combinatorial Optimization (CO) problems are fundamentally important in numerous real-world applications across diverse industries, notably computer graphics, characterized by entailing enormous solution space and demanding time-sensitive response. Despite recent advancements in neural solvers, their limited expressiveness struggles to capture the multi-modal nature of CO landscapes. While some research has adopted diffusion models, these methods sample solutions indiscriminately from the entire NP-complete solution space with time-consuming denoising processes, limiting scalability for large-scale problems. We propose DISCO, an efficient DIffusion Solver for large-scale Combinatorial Optimization problems that excels in both solution quality and inference speed. DISCO’s efficacy is twofold: First, it enhances solution quality by constraining the sampling space to a more meaningful domain guided by solution residues, while preserving the multi-modal properties of the output distributions. Second, it accelerates the denoising process through an analytically solvable approach, enabling solution sampling with very few reverse-time steps and significantly reducing inference time. This inference-speed advantage is further amplified by Jittor, a high-performance learning framework based on just-in-time compiling and meta-operators. DISCO delivers strong performance on large-scale Traveling Salesman Problems and challenging Maximal Independent Set benchmarks, with inference duration up to 5.38 times faster than existing diffusion solver alternatives. We apply DISCO to design 2D/3D TSP Art, enabling the generation of fluid stroke sequences at reduced path costs. By incorporating DISCO’s multi-modal property into a divide-and-conquer strategy, it can further generalize to solve unseen-scale instances out of the box.http://www.sciencedirect.com/science/article/pii/S1524070325000311Diffusion modelCombinatorial optimizationGraphics application |
| spellingShingle | Hang Zhao Kexiong Yu Yuhang Huang Renjiao Yi Chenyang Zhu Kai Xu DISCO: Efficient Diffusion Solver for large-scale Combinatorial Optimization problems Graphical Models Diffusion model Combinatorial optimization Graphics application |
| title | DISCO: Efficient Diffusion Solver for large-scale Combinatorial Optimization problems |
| title_full | DISCO: Efficient Diffusion Solver for large-scale Combinatorial Optimization problems |
| title_fullStr | DISCO: Efficient Diffusion Solver for large-scale Combinatorial Optimization problems |
| title_full_unstemmed | DISCO: Efficient Diffusion Solver for large-scale Combinatorial Optimization problems |
| title_short | DISCO: Efficient Diffusion Solver for large-scale Combinatorial Optimization problems |
| title_sort | disco efficient diffusion solver for large scale combinatorial optimization problems |
| topic | Diffusion model Combinatorial optimization Graphics application |
| url | http://www.sciencedirect.com/science/article/pii/S1524070325000311 |
| work_keys_str_mv | AT hangzhao discoefficientdiffusionsolverforlargescalecombinatorialoptimizationproblems AT kexiongyu discoefficientdiffusionsolverforlargescalecombinatorialoptimizationproblems AT yuhanghuang discoefficientdiffusionsolverforlargescalecombinatorialoptimizationproblems AT renjiaoyi discoefficientdiffusionsolverforlargescalecombinatorialoptimizationproblems AT chenyangzhu discoefficientdiffusionsolverforlargescalecombinatorialoptimizationproblems AT kaixu discoefficientdiffusionsolverforlargescalecombinatorialoptimizationproblems |