DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
By Zhiqing Sun, Yiming Yang. Neural Information Processing Systems, 2023
307 citations recorded by the source corpus.
Neural network-based Combinatorial Optimization (CO) methods have shown promising results in solving various NP-complete (NPC) problems without relying on hand-crafted domain knowledge. This paper broadens the current scope of neural solvers for NPC problems by introducing a new graph-based diffusion framework, namely DIFUSCO. Our framework casts NPC problems as discrete {0, 1}-vector optimization problems and leverages graph-based denoising diffusion models to generate high-quality solutions. We investigate two types of diffusion models with Gaussian and Bernoulli noise, respectively, and devise an effective inference schedule to enhance the solution quality. We evaluate our methods on two well-studied NPC combinatorial optimization problems: Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Experimental results show that DIFUSCO strongly outperforms the previous state-of-the-art neural solvers, improving the performance gap between ground-truth and neural solvers from 1.76% to 0.46% on TSP-500, from 2.46% to 1.17% on TSP-1000, and from 3.19% to 2.58% on TSP10000. For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.
Subfields: Artificial Intelligence
View Paper: https://www.semanticscholar.org/paper/5f90d43e6ece5c6ee6e8186e4b57d46c85377713
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Volodymyr Kuleshov
- Yair Schiff
- Subham Sekhar Sahoo
- Aaron Gokaslan
- Justin T. Chiu
- Alexander Rush
- Marianne Arriola
- Edgar Marroquin
Citations in the corpus
- Simple and Effective Masked Diffusion Language Models (2024, background): “Diffusion models excel at producing realistic, high-quality images and have received significant attention as potential tools for generating discrete data such as text [1, 23, 25], biological sequences [2], and graphs [45, 48].”
- ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (2024, unknown): “Beyond their foundational understanding of programming logic and structure (Chen et al., 2023c; Liventsev et al., 2023; Madaan et al., 2023a), LLMs exhibit the ability to generate novel programs that lead to mathematical discoveries (Romera-Paredes et al., 2023).”