摘要

本文介绍了一种名为DISCO的高效扩散求解器，用于解决大规模组合优化问题（CO）。DISCO在解决方案质量和推理速度方面表现出色，通过一种可解析求解的形式实现快速去噪，从而大幅减少推理时间。此外，DISCO通过引入解决方案残差，将采样空间限制在一个更有意义、更受约束的域内，同时保持输出概率分布的固有多模态特性。DISCO在处理包含10000个节点的超大规模旅行商问题（TSP）和具有挑战性的最大独立集基准测试中取得了最先进的结果，其单实例去噪时间比现有方法快达44.8倍。通过进一步结合分治策略，DISCO能够直接解决任意规模的实例，甚至超越专门针对相应规模训练的模型。

原理

DISCO的核心创新在于其高效的扩散求解机制，该机制通过两个主要策略实现：首先，通过一种可解析求解的去噪过程，DISCO能够直接从解空间中采样，仅需极少的反向时间步，从而显著减少推理时间。其次，DISCO通过引入解决方案残差，将采样空间限制在一个更有意义、更受约束的域内，同时保持输出概率分布的固有多模态特性。这种双重策略不仅提高了推理速度，还增强了解决方案的质量。

流程

DISCO的工作流程包括以下几个关键步骤：

1. 初始化：输入问题实例，使用参数化的扩散概率模型（DPM）生成每个问题变量的条件独立概率分布。
2. 去噪过程：通过分析可解的去噪过程，从噪声中快速生成高质量的解决方案，仅需极少的去噪步骤。
3. 残差约束：引入解决方案残差，将采样空间限制在一个更有意义、更受约束的域内，确保解决方案的有效性同时保持多样性。
4. 解码：将生成的概率分布通过特定的解码策略转换为离散的解决方案。
5. 分治策略：结合多模态启发式分治策略，将模型推广到任意规模的CO问题实例上。

应用

DISCO的应用前景广泛，特别适用于需要快速响应和高效率的实际应用场景，如物流、生产调度、资源分配等。其高效的推理速度和高质量的解决方案使其成为解决大规模组合优化问题的有力工具。此外，DISCO的分治策略使其能够灵活适应不同规模的问题，进一步扩大了其应用范围。