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

arXiv: https://arxiv.org/abs/2406.19705 · HTML: https://mlsanity.com/paper/2406.19705/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 63 of its 119 references that are in the map.
- First posted on arXiv 28 Jun 2024.

## Builds on (most cited first, 30 of 63)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Classifier-Free Diffusion Guidance](https://mlsanity.com/paper/2207.12598/) (2022)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Diffusion Policy: Visuomotor Policy Learning via Action Diffusion](https://mlsanity.com/paper/2303.04137/) (2023)
- [Video Diffusion Models](https://mlsanity.com/paper/2204.03458/) (2022)
- [Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks](https://mlsanity.com/paper/1511.06434/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Variational Diffusion Models](https://mlsanity.com/paper/2107.00630/) (2021)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [MCVD: Masked Conditional Video Diffusion for Prediction, Generation, and Interpolation](https://mlsanity.com/paper/2205.09853/) (2022)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Diffusion models as plug-and-play priors](https://mlsanity.com/paper/2206.09012/) (2022)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)

## Built on by (most cited first, 11 of 11)

- [Deliberate Planning of 3D Bin Packing on Packing Configuration Trees](https://mlsanity.com/paper/2504.04421/) (2025)
- [A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem](https://mlsanity.com/paper/2510.08627/) (2025)
- [Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization](https://mlsanity.com/paper/2502.19377/) (2025)
- [Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization](https://mlsanity.com/paper/2511.19573/) (2025)
- [Transport, Don't Generate: Deterministic Geometric Flows for Combinatorial Optimization](https://mlsanity.com/paper/2602.10794/) (2026)
- [Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization](https://mlsanity.com/paper/2605.25129/) (2026)
- [LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers](https://mlsanity.com/paper/2605.29005/) (2026)
- [Diffusion-Based Data-Driven Assortment Optimization](https://mlsanity.com/paper/2608.11419/) (2026)
- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)
- [Parallel Tempering for Diffusion-Based Combinatorial Optimization](https://mlsanity.com/paper/2609.37323/) (2026)
- [EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization](https://mlsanity.com/paper/2610.04953/) (2026)

## Abstract (arXiv)

Combinatorial Optimization (CO) problems are fundamentally important in numerous real-world applications across diverse industries, 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 shifted towards diffusion models, these models still sample solutions indiscriminately from the entire NP-complete solution space with time-consuming denoising processes, which limit their practicality for large problem scales. 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 minimal reverse-time steps and significantly reducing inference time. DISCO delivers strong performance on large-scale Traveling Salesman Problems and challenging Maximal Independent Set benchmarks, with inference time up to 5.28 times faster than other diffusion alternatives. By incorporating a divide-and-conquer strategy, DISCO can well generalize to solve unseen-scale problem instances, even surpassing models specifically trained for those scales.