Combinatorial Optimization (CO) problems are fundamentally crucial in
numerous practical applications across diverse industries, characterized by
entailing enormous solution space and demanding time-sensitive response.
Despite significant advancements made by recent neural solvers, their limited
expressiveness does not conform well to the multi-modal nature of CO
landscapes. While some research has pivoted towards diffusion models, they
require simulating a Markov chain with many steps to produce a sample, which is
time-consuming and does not meet the efficiency requirement of real
applications, especially at scale. We propose DISCO, an efficient DIffusion
Solver for Combinatorial Optimization problems that excels in both solution
quality and inference speed. DISCO's efficacy is two-pronged: Firstly, it
achieves rapid denoising of solutions through an analytically solvable form,
allowing for direct sampling from the solution space with very few reverse-time
steps, thereby drastically reducing inference time. Secondly, DISCO enhances
solution quality by restricting the sampling space to a more constrained,
meaningful domain guided by solution residues, while still preserving the
inherent multi-modality of the output probabilistic distributions. DISCO
achieves state-of-the-art results on very large Traveling Salesman Problems
with 10000 nodes and challenging Maximal Independent Set benchmarks, with its
per-instance denoising time up to 44.8 times faster. Through further combining
a divide-and-conquer strategy, DISCO can be generalized to solve
arbitrary-scale problem instances off the shelf, even outperforming models
trained specifically on corresponding scales.

提出了一种用于组合优化问题的高效扩散求解器 DISCO，通过快速去噪和限制采样空间的方法，在解决质量和推理速度方面表现出色。