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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1524-0703 |