DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems

组合优化（CO）问题在许多不同行业的实际应用中至关重要，其特点是具有巨大的解空间和对时间敏感的响应要求。尽管最近神经求解器取得了显著进展，但它们的表达能力有限，不太适合CO景观的多模态特性。虽然一些研究已经转向扩散模型，但它们需要模拟具有多个步骤的马尔可夫链才能产生样本，这是耗时的，并且不能满足实际应用的效率要求，特别是在大规模情况下。我们提出了一种名为DISCO的高效组合优化问题扩散求解器，它在解决方案质量和推断速度方面都表现出色。DISCO的有效性是双重的：首先，它通过解析可解形式实现快速解决方案去噪，允许直接从解空间中进行少量的反向时间步骤采样，从而大大减少推断时间。其次，DISCO通过将采样空间限制在更受控制的有意义域中，同时仍保留输出概率分布的固有多模态性，从而提高解决方案质量。DISCO在具有10000个节点的大型旅行商问题和具有挑战性的最大独立集基准测试中实现了最先进的结果，其每个实例的去噪时间最高可快44.8倍。通过进一步结合分治策略，DISCO可以通用地解决任意规模的问题实例，甚至优于专门针对相应规模进行训练的模型。

DISCO: 一种用于组合优化问题的快速扩散求解器

该论文提出了一种快速的扩散求解器，用于解决组合优化问题，通过限制采样空间并降噪来提高求解速度和质量

该方法在大规模的TSP和最大独立集问题上实现了最先进的结果，且求解时间最高可达44.8倍的加速；通过分治策略，该方法可以推广到任意规模的问题实例，并且在某些情况下超过了专门针对对应规模训练的模型。

最近的相关研究包括基于神经网络的求解器和扩散模型，但这些方法存在一些局限性，如表达能力不足、采样时间过长等。