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

Kexiong Yu
National University of Defense Technology
<EMAIL_ADDRESS>
&Hang Zhao
National University of Defense Technology
<EMAIL_ADDRESS>
&Yuhang Huang
National University of Defense Technology
<EMAIL_ADDRESS>
&Renjiao Yi
National University of Defense Technology
<EMAIL_ADDRESS>
&Kai Xu
National University of Defense Technology
<EMAIL_ADDRESS>
&Chenyang Zhu
National University of Defense Technology
<EMAIL_ADDRESS>

###### Abstract

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.

##  1 Introduction

Combinatorial Optimization (CO) is a fundamental field in both computer
science and operations research, encompassing the search for an optimal
solution from a finite set of entities. These challenges are widespread in
various real-world applications across diverse industries, spanning logistics
[57; 63], production scheduling [92; 95], and resource allocation [98; 100]. A
distinctive characteristic of CO problems is the exponential expansion of
their solution space as the problem scale increases. This exponential growth
is particularly pronounced in the case of NP-complete (NPC) problems [27],
representing the most formidable challenges within NP and posing a formidable
obstacle to precisely finding an optimal solution within a polynomial time
frame.

In recent years, deep learning algorithms have showcased remarkable
capabilities in predicting CO solutions [15; 48]. However, these learning-
based neural solvers are susceptible to being misled by the multi-modality
inherent in CO problems [47], wherein the learning agent is required to
identify a set of optimal solutions. This multi-modality complicates the
learning process, hindering efficient convergence to desired solutions,
particularly when confronted with large-scale instances [13; 89]. Diffusion
probabilistic models [35; 69; 79] have demonstrated robust capabilities in
various generation tasks. Of particular interest, Chi et al. [14] and Huang et
al. [41] have employed diffusion methods for decision model construction,
showcasing their inherent advantages in addressing multi-modal problems. This
serves as inspiration for us to explore the application of diffusion models to
CO problems, which similarly exhibit multi-modal characteristics.

We are not the first to apply diffusion models to CO problems. Graikos et al.
[32] tackle Euclidean Traveling Salesman problems (TSP) by converting each
instance into a low-resolution greyscale image and then utilizing a
Convolutional Neural Network (CNN) [56] for denoising the solution. Sun and
Yang [80] attempt to address this limitation by incorporating Graph Neural
Networks (GNNs) [31] to explicit model problem structures. Although these
approaches show improved performance, they require simulating a Markov chain
with many steps for generation, which significantly incurs time overhead. This
limitation inevitably hampers their practicality for time-sensitive real-world
applications [28; 91], especially when dealing with large-scale instances.

We contend that the potential of diffusion models in addressing CO problems
has yet to be fully discovered. We propose DISCO, an efficient DIffusion
Solver for Combinatorial Optimization problems. DISCO obtains rapidly
generating high-quality solutions with very few denoising steps and enhances
solution quality by restricting the sampling space to a more constrained,
meaningful domain guided by solution residues. DISCO achieves state-of-the-art
results on large-scale TSP-10000 instances and challenging Maximal Independent
Set (MIS) 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.

##  2 Related Work

#### Combinatorial Optimization

Combinatorial optimization (CO) problems have garnered considerable attention
over the years due to their extensive applicability across diverse domains
such as logistics [4; 52], production scheduling [92; 95], and resource
allocation [98; 100]. However, the exponential growth of the solution space,
as the problem scale escalates for these NPC problems [27], poses a formidable
challenge for finding an optimal solution within a polynomial time frame.
Traditional solvers for CO problems can be classified into exact algorithms,
approximation algorithms, and heuristic methods. Exact algorithms [55; 74],
such as dynamic programming [17] and cutting-plane methods [88], aim to
exactly find the optimal solution for each test instance. However, they only
suit small to medium-sized problems due to the inherent heavy computational
complexity. Approximation [37; 84] and heuristic [29; 67] methods, on the
other hand, are used when the problem scale is large or time constraints exist
for finding solutions. These methods can find solutions within an acceptable
time cost. However, they typically heavily rely on expert knowledge [34; 83]
and cannot guarantee the high quality of the final discoveries.

#### Learning for Combinatorial Optimization

With the blossoming of deep learning mechanisms that do not heavily rely on
expert knowledge and can be easily adapted to various automated searching
processes, researchers have widely explored neural solvers for CO problems.
These approaches encompass both supervised learning (SL) [80; 86] and
reinforcement learning (RL) [68; 82]. From a practical perspective, the choice
between SL and RL depends on the availability of problem data. For online
operation problems [8; 76], the input data is progressively revealed, and
decisions must be made immediately upon data arrival. Such problems require
algorithms to make decisions without fully understanding the problem,
typically modeled as Markov Decision processes and solved through trial-and-
error methods using RL [97; 99]. Conversely, for offline problems [66; 70],
all input data and all constraints are fully provided before solving the
problems. The decision-makers can fully utilize all relevant information for
comprehensive analysis and iteratively improve solution quality. Providing an
initial solution by SL and further refining it by decoding strategies [19; 26;
32; 52] has become a common practice [22]. Most CO problems can be modeled as
decision problems on graphs [59; 92; 93; 95]. Notably, the Traveling Salesman
Problem (TSP) [7; 64] and the Maximum Independent Set (MIS) [12; 21] stand out
as two foundations regarding edge and node decision problems. DISCO leverages
anisotropic GNNs [10; 45] as the backbone to produce embeddings for both graph
edges and nodes, adequately demonstrating its superiority on both TSP and MIS
instances.

#### Diffusion Probabilistic Model

Diffusion probabilistic models (DPMs) [35; 69; 79] are primarily utilized for
high-quality generation and have exhibited robust capabilities in generating
images [42; 94], audios [62], and videos [36; 87]. This impressive method was
initially formulated by Sohl-Dickstein et al. [78] and further extended by Ho
et al. [35] through the proposal of a general generation framework. Its
principle involves simulating a forward process of gradually introducing
noise, followed by training a reverse noise removal model to generate data.
These models can further adjust the conditional variables [23] during the
reverse process to generate data samples that satisfy specific attributes or
conditions. In comparison to other generative models such as Generative
Adversarial Networks (GANs) [30; 72], diffusion models demonstrate higher
stability during training. This is attributed to their avoidance of
adversarial training and they gradually approach the true distribution of the
data by learning to remove noise.

#### Diffusion for Combinatorial Optimization

In addition to stable and high-quality generation, DPMs have exhibited a
promising prospect for generating a wide variety of distributions [35; 41].
This multi-modal property particularly benefits CO problem solving, where
multiple optimal solutions may exist and confront the limited expressiveness
of previous neural solvers [33; 47; 58]. Some attempts have been made. Graikos
et al. [32] convert TSP instances into low-resolution greyscale images encoded
by CNN while Sun and Yang [80] incorporate GNN [31] for problem
representation. These efforts mainly focus on feature extraction and overlook
the slow reverse process of diffusion models, which significantly hampers
their practicality for time-sensitive real-world applications [28; 91],
particularly at large scales. DISCO differentiates itself by developing a
specialized diffusion process tailored for CO, optimizing both forward and
reverse processes. Specifically, DISCO employs an analytical denoising process
[40] to quickly produce high-quality solutions with very few denoising steps,
while dramatically reducing solution space associated with NPC problems by
introducing solution residues [60]. This enhanced efficiency on both inference
speed and solution quality further amplifies DISCO’s generalization advantages
on the CO challenge of arbitrary scales.

##  3 Preliminary

Combinatorial optimization can generically be framed as the task of finding a
valid solution $\mathbf{X}_{s}$ from a discrete solution space
$\mathcal{X}_{s}=\\{0,1\\}^{N}$ for a given instance $s$, while minimizing the
task-specific cost function $\text{cost}(\mathbf{X}_{s})$ [70]. The optimal
solution $\mathbf{X}^{*}_{s}$ is defined as:

$\operatorname*{argmin}_{\mathbf{X}_{s}\in\mathcal{X}_{s}}\text{cost}(\mathbf{X}_{s}).$
(1)

Taking TSP instances as an example, $N$ represents the edge number,
$X_{i}\in\mathbf{X}_{s}$ indicates whether the $i$-th edge is selected, and
$\text{cost}_{s}(\mathbf{X})$ means the tour length of $\mathbf{X}$.
Parameterized solvers, denoted as $p(\cdot|s)$, are trained to predict the
probability distribution over each problem variable. Either supervised
learning [80; 86] or reinforcement learning [4; 52] mechanisms have been
extensively explored.

While previous neural CO solvers have shown promising results, they usually
suffer from the expressiveness limitation when confronted with multiple
optimal solutions for the same graph [33; 47]. Thanks to recent advances in
generative models, DPMs have exhibited promising prospects for generating a
wide variety of distributions [35; 41] suitable for CO solving.

DPMs view the input-to-noise process as a parameterized Markov chain that
gradually adds noise to the original data $\mathbf{x}_{0}$ until the signal is
completely corrupted, this forward process is first formulated by Sohl-
Dickstein et al. [78] with definition:

$q(\mathbf{x}_{t}\mid\mathbf{x}_{0})=\mathcal{N}\left(\mathbf{x}_{t};\alpha_{t}\mathbf{x}_{0},\beta_{t}^{2}\mathbf{I}\right),$
(2)

where $\alpha_{t}$ and $\beta_{t}$ are the differentiable functions of time
$t$ with bounded derivatives, $\mathbf{x}_{t}$ is noisy data, and $\mathbf{I}$
is the identity matrix. Kingma et al. [49] give proof that this Markov chain
can be represented by the following stochastic differential equation:

$d\mathbf{x}_{t}=h_{t}\mathbf{x}_{t}\,dt+g(t)\,d\mathbf{w}_{t},\quad\mathbf{x}_{0}\sim
q(\mathbf{x}_{0}),$ (3)

where $h_{t}=\frac{\mathrm{d}\log{\alpha_{t}}}{\mathrm{d}t}$,
$g_{t}^{2}=\frac{\mathrm{d}\beta_{t}^{2}}{\mathrm{d}t}-2h_{t}\beta_{t}^{2}$,
and $\mathbf{w}_{t}$ denotes the standard Wiener process [24].

##  4 Method

We introduce our analytical denoising process to generate high-quality
solutions with very few reverse-time steps in Sec. 4.1. By introducing
solution residues, as clarified in Sec. 4.2, we restrict the sampling space to
a more constrained, meaningful domain, ensuring solution effectiveness while
preserving diversity. In Sec. 4.3, we further generalize DISCO to solve
arbitrary-scale CO problems combining with a multi-modality inspired divide-
and-conquer strategy.

###  4.1 Analytically Solvable Denoising Process

Given problem instance $s$, parameterized DPM $p(\cdot|s)$ generates
conditionally independent probability distribution $\mathbf{x}_{0}$ for each
problem variable, also known as heatmap scores [26; 80]. Subsequently, task-
specific decoding processes [19; 52] are employed to transform predicted
$\mathbf{x}_{0}$ into discrete solution $\mathbf{X}_{s}$. Typically, DPMs
employ numerical integration during the reverse process, requiring multiple
steps of accumulation and solving. This process incurs significant time
overhead. For example, DDPM [35] usually takes 900 $\sim$ 1000 sampling steps
for meaningful image generation. The slow solving speed significantly limits
the practical application of diffusion solvers for real-world CO problems,
particularly considering many time-sensitive demands, such as on-call routing
[28] and on-demand hailing service [91], not to mention the large-scale
operation challenges.

To avoid time-consuming numerical integration and generate high-quality
solutions with fewer steps, we substitute the numerical integration process
with an analytically solvable form. Inspired by decoupled diffusion models
(DDMs) [40], the original solution-to-noise mapping can be decoupled into
solution-to-zero and zero-to-noise mapping:

$\mathbf{x}_{t}=\mathbf{x}_{0}+\int_{0}^{t}\mathbf{f}_{t}dt+\int_{0}^{t}d\mathbf{w}_{t},\quad\mathbf{x}_{0}\sim
q(\mathbf{x}_{0}),$ (4)

where $\mathbf{x}_{0}=\mathbf{X}_{s}$ denotes the high-quality solution label,
$\mathbf{x}_{t}$ is the noisy solution, and $\mathbf{f}_{t}$ represents the
analytic attenuation function. In the formulation,
$\mathbf{x}_{0}+\int_{0}^{t}\mathbf{f}_{t}dt$ describes the solution
attenuation and $\int_{0}^{t}d\mathbf{w}_{t}$ describes the noise accumulation
respectively. Decoupling the original solution-to-noise mapping into two
relatively simpler processes improves the effectiveness of diffusion model
training.

More importantly, since $\mathbf{f}_{t}$ can be designed analytically, the
efficiency of the reversed process can be improved by much fewer evaluation
steps, e.g., inference with 1 or 2 steps. Based on Eq. 4, the transition
probability from $\mathbf{x}_{0}$ to $\mathbf{x}_{t}$ can be defined as:

$q(\mathbf{x}_{t}\mid\mathbf{x}_{0})=\mathcal{N}(\mathbf{x}_{t};\mathbf{x}_{0}+\int_{0}^{t}\mathbf{f}_{t}d_{t},t\mathbf{I}).$
(5)

For a reversed process, the sampling formula for $\mathbf{x}_{0}$ is based on
the analytic function $\mathbf{f}_{t}$ that models the solution to zero
transition process. We employ continuous-time Markov chain with the smallest
time step $\Delta t\rightarrow 0^{+}$ and use conditional distribution
$q(\mathbf{x}_{t-\Delta t}\mid\mathbf{x}_{t},\mathbf{x}_{0})$ to approximate
$q(\mathbf{x}_{t-\Delta t}\mid\mathbf{x}_{t})$, which is formulated by:

$\begin{split}&q(\mathbf{x}_{t-\Delta
t}|\mathbf{x}_{t},\mathbf{x}_{0})\propto\exp\\{-\frac{(\mathbf{x}_{t-\Delta
t}-\mathbf{\widetilde{u}})^{2}}{2\widetilde{\sigma}^{2}\mathbf{I}}\\},\\\
&\mathbf{\widetilde{u}}=\mathbf{x}_{t}-\int_{t-\Delta
t}^{t}\mathbf{f}_{t}d_{t}-\frac{\Delta
t}{\sqrt{t}}\boldsymbol{\epsilon},\quad\widetilde{\sigma}^{2}=\frac{\Delta
t(t-\Delta t)}{t},\end{split}$ (6)

where $\boldsymbol{\epsilon}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$. Since
$\mathbf{f}_{t}$ has an analytic form, we can avoid the numerical integration-
based denoising and instead directly sample heatmap $\mathbf{x}_{0}$ with an
arbitrary step size, which significantly reduces the inference time.

###  4.2 Residue-Constrained Solution Generation

(a) Traditional denoising process.(b) Ours.

Figure 1: (a) The output of traditional diffusion processes spans the entire
mixed-quality solution space, i.e., a significant proportion of the
generations do not satisfy problem constraints besides high-quality heatmaps.
(b) DISCO constrains the generations close to the high-quality label
$\mathbf{X}_{s}$ by introducing residues, resulting in a smaller but more
meaningful solution space, while still preserving the multi-modality of the
output distributions.

The NPC solution space of CO problems exponentially grows with problem scales.
The reverse generation covering such an enormous space is inefficient since
many samples do even not adhere to problem constraints, as depicted in Fig. 1
(a). We propose to restrict the sampling space from the entire NPC space to a
more constrained, meaningful domain while still preserving the multi-modality
of the output probabilistic distributions. We achieve this by introducing
solution residues [60] to prioritize certainty besides noises to emphasize
diversity, as shown in Fig. 1 (b). The reversed process starts from both noise
and an exceedingly economical degraded solution, confining the generated
samples close to the high-quality input data. Driving a high-quality solution
from a degraded or heuristic one has been verified as effective and is widely
adopted in solving various CO problems [95; 100].

We denote $\mathbf{X}_{d}$ a readily obtainable degraded solution that
satisfies problem constraints and solution residues
$\mathbf{x}_{res}=\mathbf{X}_{d}-\mathbf{x}_{0}$. Take TSP as an example,
$\mathbf{X}_{d}$ can be obtained by connecting vertices in the graph in a
sequential order to form a tour. The forward process can be defined as:

$\mathbf{x}_{t}=\mathbf{x}_{0}+\int_{0}^{t}\mathbf{x}_{res}dt+\sqrt{t}\boldsymbol{\epsilon},\quad\boldsymbol{\epsilon}\sim\mathcal{N}(\boldsymbol{\epsilon};\mathbf{0},\mathbf{I}).$
(7)

Different from the original decoupled forward process, the first term of Eq.
7, $\mathbf{x}_{0}+\int_{0}^{t}\mathbf{x}_{res}dt$ represents the solution to
degradation rather than solution to zero process. Intuitively, the former is
much easier to learn since it only needs to predict the residue. Similar to
Eq. 6, the transition probability of the reversed process is defined as:

$\begin{split}&q(\mathbf{x}_{t-\Delta
t}|\mathbf{x}_{t},\mathbf{x}_{0})\propto\exp\left\\{-\frac{(\mathbf{x}_{t-\Delta
t}-\mathbf{u})^{2}}{2\sigma^{2}\mathbf{I}}\right\\},\\\
&\mathbf{u}=\mathbf{x}_{t}-\int_{t-\Delta t}^{t}\mathbf{x}_{res}dt-\Delta
t\boldsymbol{\epsilon}/\sqrt{t},\quad\sigma^{2}=\Delta t(t-\Delta
t)/t.\end{split}$ (8)

The residue prioritizes certainty while the noise emphasizes diversity, so
that the solution space for sampling is effectively constrained. We also
provide theoretical analysis about the equivalence between DISCO and DDM in
App. A, supporting the effectiveness of our method.

#### Training

We adopt anisotropic GNNs [10; 45] as the network architecture of DISCO.
Unlike typical GNNs such as GCN [50] or GAT [85] designed for node-only
embedding, anisotropic GNNs produce embeddings for both nodes and edges, which
are then fed into the diffusion model to generate heatmaps. Practically, we
input the noisy solution $\mathbf{x}_{t}$, the nodes and edges of
$\mathbf{X}_{d}$, and the time $t$ into the anisotropic GNN with parameter
$\boldsymbol{\theta}$, predicting the parameterized residue
$\mathbf{x}_{res}^{\boldsymbol{\theta}}$ and noise
$\boldsymbol{\epsilon}^{\boldsymbol{\theta}}$ simultaneously. Specific
implementation details are provided in App. G.

We focus on offline CO problems. Therefore, we train DISCO in an efficient and
stable supervised mechanism to discover common patterns from high-quality
solutions available for each instance. This also helps circumvent the
challenges associated with scaling up and the latency in the inference that
arises from the sparse rewards and sample efficiency issues when learning in
an RL framework [65; 89], especially at large scales. The training objective
is defined as:

$\min_{\boldsymbol{\theta}}\mathbb{E}_{q(\mathbf{X}_{s})}\mathbb{E}_{q(\boldsymbol{\epsilon})}\left[\|\mathbf{x}_{res}^{\boldsymbol{\theta}}-\mathbf{x}_{res}\|^{2}+\|\boldsymbol{\epsilon}^{\boldsymbol{\theta}}-\boldsymbol{\epsilon}\|^{2}\right].$
(9)

After the model has been trained, it can be applied to generate heatmaps for a
virtually unlimited number of unseen graphs during deployment. These heatmaps
are fed into decoding strategies like Greedy [32], Sample [52], 2-opt [19],
MCTS [26], and so on, for achieving the final solution.

#### Sampling

Eq. 7 shows the endpoint of the forward process is the mixture of the degraded
solution and noise, therefore, we start from the mixture in the sampling
process. Given a degraded solution $\mathbf{X}_{d}$ and a noise
$\boldsymbol{\epsilon}$ sampled from the normal distribution, we set
$\mathbf{x}_{1}=\mathbf{X}_{d}+\boldsymbol{\epsilon}$ ($t=1$). Sampling from
$\mathbf{x}_{1}$ instead of $\boldsymbol{\epsilon}$ constrains the sample
space from the entire noise domain into a smaller one, ensuring an effective
solution. For a $K$-step sampling, we set the step size of each sampling to
$1/K$. At each sampling step, we utilize the anisotropic GNN to predict the
estimated residue $\mathbf{x}_{res}^{\boldsymbol{\theta}}$ and noise
$\boldsymbol{\epsilon}^{\boldsymbol{\theta}}$. In this way, we can solve the
reversed process via Eq. 8 iteratively, obtaining the high-quality solution
$\mathbf{x}_{0}$ until $t=0$. After we sample a probability distribution
$\mathbf{x}_{0}$ from $p_{\boldsymbol{\theta}}(s)$ for instance $s$, we adopt
the same operation as [80] to obtain the normalized heatmap score
$\mathbf{h}=0.5(\mathbf{x}_{0}+1)$.

###  4.3 Multi-Modality Inspired Graph Search

Parameterized solvers trained on fixed scales often struggle to generalize
well to test instances of different scales [26]. Training a model from scratch
on the target scale or fine-tuning the model includes additional training time
within the decision loop, making it impractical for real-world applications
that demand an off-the-shelf response. We aim to further develop the
generalization ability of DISCO to unseen-scale instances. With the efficiency
advantage of DISCO in both inference speed and solution quality, along with
the assistance of the SL approach in discovering common solution patterns, we
can enhance this generalization ability through a divide-and-conquer strategy.

Figure 2:  Our multi-modality inspired graph search method, illustrated using
a TSP instance for simplicity. M & D denotes merging a combination of heatmaps
$\mathbf{c}$ to global heatmap $\mathbf{H}$ and decoding a trial $\mathbf{X}$
from $\mathbf{H}$.  Algorithm 1 Multi-Modal Graph Search

0: A graph problem $G$ to be solved

0:

1: Pre-train DISCO model $p_{\boldsymbol{\theta}}$ on a small scale

2: Sample a set of subgraphs $\mathbf{g}$ from $G$

3: for $g\in\mathbf{g}$ do

4: Sample heatmap set $\mathcal{H}$ from $p_{\boldsymbol{\theta}}(g)$ with $q$
different noise $\mathbf{x}_{t}$

5: end for

6: Initialize trial set $\mathcal{X}=\emptyset$

7: for $k=1,2,3,\dots,n$ do

8: Sample $\mathbf{h}$ from each $\mathcal{H}$ as combination $\mathbf{c}_{k}$

9: Merge $\mathbf{c}_{k}$ as a global heatmap $\mathbf{H}_{k}$

10: Decode trial $\mathbf{X}_{k}$ from $\mathbf{H}_{k}$, add it to
$\mathcal{X}$

11: end for

12: Select a final trial with
$\arg\min_{\mathbf{X}\in\mathcal{X}}\text{cost}(\mathbf{X})$

Specifically, we leverage a model $p_{\boldsymbol{\theta}}$ trained on a small
scale to serve as a base and construct heatmaps for sub-problems $\mathbf{g}$
decomposed from the original graph $G$, thereby smoothly generalize
$p_{\boldsymbol{\theta}}$ to arbitrary scales. A detailed pipeline is provided
in Fig. 2. We set each subgraph $g\in\mathbf{g}$ with a fixed number of nodes
for the decomposition. We adopt a vector $\mathbf{o}_{v}$ recording the
occurrence number of each node of $G$ in all existing subgraphs. In each
iteration, we choose the node with the index
$\operatorname*{argmin}(\mathbf{o}^{v})$ as the cluster center and select the
remaining nodes with the k-nearest neighbor rule [18], forming a subgraph $g$.
This process continues until $\min(\mathbf{o}^{v})$ exceeds a certain
threshold $\omega$. For each $g\in\mathbf{g}$, we resize it to a uniform size.
Leveraging DISCO models $p_{\boldsymbol{\theta}}$ trained on a small problem
scale, we can generate sub-heatmap score $\mathbf{h}$ for $g$. The solution
for the original graph $G$ is obtained by merging all sub-heatmaps which
jointly cover $G$ at least $\omega$ times. The merged global heatmap
$\mathbf{H}$ is calculated as follows:

$\mathbf{H}_{ij}=\frac{1}{\mathbf{o}_{ij}}\times\sum_{l=1}^{|\mathbf{g}|}\phi(\mathbf{h}_{l},i,j),$
(10)

where $\phi(\mathbf{h}_{l},i,j)$ represents the heatmap value contributed by
$\mathbf{h}_{l}$ corresponding to index $ij$ of $\mathbf{H}$, with
$\phi(\mathbf{h}_{l},i,j)=0$ if no correspondence. Subsequently, we decode the
final solution $\mathbf{X}$ from $\mathbf{H}$.

While the divide-and-conquer approach improves generalization performance, the
preference of sub-heatmaps of selecting the locally shortest path may lead the
final solution to get stuck in the sub-optimum. We further leverage the multi-
modality of DISCO to enhance the solution diversity and avoid this sub-optimum
dilemma. For each subgraph $g\in\mathbf{g}$, we repeatedly sample a set of
heatmaps $\mathcal{H}$ with $q$ different noise $\mathbf{x}_{t}$. We randomly
sample one heatmap $\mathbf{h}$ from each $\mathcal{H}$, combining as a set
$\mathbf{c}$ with $|\mathbf{c}|=|\mathbf{g}|$, merging as a global heatmap
$\mathbf{H}$, and decoding a solution trial $\mathbf{X}$ from $\mathbf{H}$.
This sample process is repeated $n$ times, generating multiple trials as
$\mathcal{X}$. We decide the final solution with the minimum cost from
$\mathcal{X}$, i.e.,
$\arg\min_{\mathbf{X}\in\mathcal{X}}\text{cost}(\mathbf{X})$. Although there
may be $\exp_{q}(|\mathbf{g}|)$ possible combinations, we observe that the
final performance asymptotically converges to the number of sampled trials, so
we only need finite $n$ samples. We also provide our detailed algorithm in
Alg. 1.

##  5 Experiments

We provide extensive experimental results to demonstrate the superiority of
DISCO. We begin by detailing the experimental settings in Sec. 5.1, followed
by comparisons with state-of-the-art CO solvers on well-studied TSP problems
in Sec. 5.2 to showcase DISCO’s performance. Subsequently, we conduct
ablations on DISCO components in Sec. 5.3, verify its generalization ability
to arbitrary problem scales in Sec. 5.4, and also assess its scalability in
solving MIS problems in Sec. 5.5.

###  5.1 Experimental Settings

#### Metrics

While DISCO is generically applicable to various NPC problems, we mainly
conduct evaluations focused on the most representative TSP problems, as it is
a common challenge in the machine learning community with well-studied
competitors for demonstrating our method’s superiority. Given this, our
evaluation metrics are the average length (Length) of predicted tours and the
clock time (Time) required to generate solutions for all test instances,
presented in seconds (s), minutes (m), or hours (h). We also report the
performance gap (Gap), which is the average of the relative decrease in
performance compared to a baseline method.

#### Baselines

We extensively compare DISCO with various baselines, including exact solvers,
heuristic solvers, and state-of-the-art learning methods. For exact solvers,
our comparisons include Concorde [3] and Gurobi [61]. Regarding heuristic
solvers, we evaluate against LKH-3 [34] and a simple Farthest Insertion
principle [16]. In terms of learning-based methods, we compare with recent
advances including AM [52], GCN [46], POMO [53], EAN [22], POMO + EAS [39],
Att-GCN [26], DIMES [71], and a graph-based diffusion solver DIFUSCO [80].

We label the large-scale training instances using the LKH-3 heuristic solver
[34] and we take the same test instances as [26; 80]. All evaluations are
conducted on a single NVIDIA Tesla V100 GPU, paired by Intel(R) Xeon(R) Gold
CPUs @ 2.50GHz, consistent with previous works [71; 80]. Some learning-based
solvers struggle with large problem scales; for instance, Image Diffusion [32]
only operates on a $64\times 64$ greyscale image. To ensure fairness, we
compare them on small-scale instances. The results are provided in App. C,
along with comparisons with Transformer [11], Sym-NCO [48], DPDP [65], and
MDAM [90]. Our codes, trained models, and documentation are provided in the
Supplementary Material and will be publicly released upon acceptance.

###  5.2 Comprehensive Comparisons

Table 1: Comparisons on large-scale TSP problems. AS, G, S, BS, and MCTS
denotes Active Search [5], Greedy decoding, Sampling decoding, Beam Search
[81], and Monte Carlo Tree Search [51], respectively. The symbol * indicates
the baseline for computing the performance gap. The symbol ${\dagger}$ denotes
that the diffusion model samples once. The per-instance inference time for
diffusion models DISCO/DIFUSCO is $\boldsymbol{5.21\times 10^{-2}}$/2.21(s)
for TSP-500, $\boldsymbol{1.23\times 10^{-1}}$/5.51(s) for TSP-1000, and
$\boldsymbol{1.10}$/31.91(s) for TSP-10000 instances.

Algorithm | Type | TSP-500 | TSP-1000 | TSP-10000
---|---|---|---|---
Length $\downarrow$ |  Gap $\downarrow$ |  Time $\downarrow$ |  Length $\downarrow$ |  Gap $\downarrow$ |  Time $\downarrow$ |  Length $\downarrow$ |  Gap $\downarrow$ |  Time $\downarrow$
Concorde | Exact |  16.55∗ | — |  37.66$\mathrm{m}$ |  23.12∗ | — |  6.65$\mathrm{h}$ | N/A | N/A | N/A
Gurobi | Exact | 16.55 | 0.00% |  45.63$\mathrm{h}$ | N/A | N/A | N/A | N/A | N/A | N/A
LKH-3 (default) | Heuristics | 16.55 | 0.00% |  46.28$\mathrm{m}$ | 23.12 | 0.00% |  2.57$\mathrm{h}$ |  71.77∗ | — |  8.8$\mathrm{h}$
LKH-3 (less trials) | Heuristics | 16.55 | 0.00% |  3.03$\mathrm{m}$ | 23.12 | 0.00% |  7.73$\mathrm{m}$ | 71.79 | — |  51.27$\mathrm{m}$
Farthest Insertion | Heuristics | 18.30 | 10.57% |  0$\mathrm{s}$ | 25.72 | 11.25% |  0$\mathrm{s}$ | 80.59 | 12.29% |  6$\mathrm{s}$
AM | RL+G | 20.02 | 20.99% |  1.51$\mathrm{m}$ | 31.15 | 34.75% |  3.18$\mathrm{m}$ | 141.68 | 97.39% |  5.99$\mathrm{m}$
GCN | SL+G | 29.72 | 79.61% |  6.67$\mathrm{m}$ | 48.62 | 110.29% |  28.52$\mathrm{m}$ | N/A | N/A | N/A
POMO+EAS-Emb | RL+AS+G | 19.24 | 16.25% |  12.80$\mathrm{h}$ | N/A | N/A | N/A | N/A | N/A | N/A
POMO+EAS-Tab | RL+AS+G | 24.54 | 48.22% |  11.61$\mathrm{h}$ | 49.56 | 114.36% |  63.45$\mathrm{h}$ | N/A | N/A | N/A
DIMES | RL+G | 18.93 | 14.38% |  0.97$\mathrm{m}$ | 26.58 | 14.97% |  2.08$\mathrm{m}$ | 86.44 | 20.44% |  4.65$\mathrm{m}$
DIMES | RL+AS+G | 17.81 | 7.61% |  2.10$\mathrm{h}$ | 24.91 | 7.74% |  4.49$\mathrm{h}$ | 80.45 | 12.09% |  3.07$\mathrm{h}$
DIFUSCO |  SL+G${\dagger}$+2-opt | 16.80 | 1.49% |  3.65$\mathrm{m}$ | 23.56 | 1.90% |  12.06$\mathrm{m}$ | 73.99 | 3.10% |  35.38$\mathrm{m}$
DISCO (Ours) |  SL+G${\dagger}$+2-opt | 16.86 | 1.87% |  0.25$\mathrm{m}$ | 23.65 | 2.29% |  1.12$\mathrm{m}$ | 73.85 | 2.90% |  25.12$\mathrm{m}$
EAN | RL+S+2-opt | 23.75 | 43.57% |  57.76$\mathrm{m}$ | 47.73 | 106.46% |  5.39$\mathrm{h}$ | N/A | N/A | N/A
AM | RL+BS | 19.53 | 18.03% |  21.99$\mathrm{m}$ | 29.90 | 29.23% |  1.64$\mathrm{h}$ | 129.40 | 80.28% |  1.81$\mathrm{h}$
GCN | SL+BS | 30.37 | 83.55% |  38.02$\mathrm{m}$ | 51.26 | 121.73% |  51.67$\mathrm{m}$ | N/A | N/A | N/A
DIMES | RL+S | 18.84 | 13.84% |  1.06$\mathrm{m}$ | 26.36 | 14.01% |  2.38$\mathrm{m}$ | 85.75 | 19.48% |  4.80$\mathrm{m}$
DIMES | RL+AS+S | 17.80 | 7.55% |  2.11$\mathrm{h}$ | 24.89 | 7.70% |  4.53$\mathrm{h}$ | 80.42 | 12.05% |  3.12$\mathrm{h}$
DIFUSCO | SL+S+2-opt | 16.65 | 0.57% |  11.46$\mathrm{m}$ | 23.45 | 1.43% |  48.09$\mathrm{m}$ | 73.89 | 2.95% |  6.72$\mathrm{h}$
DISCO (Ours) | SL+S+2-opt | 16.73 | 1.09% |  3.88$\mathrm{m}$ | 23.56 | 1.90% |  9.62$\mathrm{m}$ | 73.81 | 2.84% |  1.60$\mathrm{h}$
Att-GCN | SL+MCTS | 16.97 | 2.54% |  2.20$\mathrm{m}$ | 23.86 | 3.22% |  4.10$\mathrm{m}$ | 74.93 | 4.39% |  21.49$\mathrm{m}$
DIMES | RL+MCTS | 16.87 | 1.93% |  2.92$\mathrm{m}$ | 23.73 | 2.64% |  6.87$\mathrm{m}$ | 74.63 | 3.98% |  29.83$\mathrm{m}$
DIMES | RL+AS+MCTS | 16.84 | 1.76% |  2.15$\mathrm{h}$ | 23.69 | 2.46% |  4.62$\mathrm{h}$ | 74.06 | 3.19% |  3.57$\mathrm{h}$
DIFUSCO | SL+MCTS | 16.63 | 0.46% |  10.13$\mathrm{m}$ | 23.39 | 1.17% |  24.47$\mathrm{m}$ | 73.62 | 2.58% |  47.36$\mathrm{m}$
DISCO (Ours) | SL+MCTS | 16.63 | 0.46% |  6.99$\mathrm{m}$ | 23.42 | 1.30% |  15.82$\mathrm{m}$ | 73.56 | 2.49% |  42.35$\mathrm{m}$

We compare DISCO to alternative NPC solvers across various problem scales,
namely TSP-500, TSP-1000, and TSP-10000. Given that the approach of providing
heatmaps by parameterized solvers and further transforming them into solutions
by decoding strategies has become a common practice since 2018 [22], we report
parameterized solvers’ performance combined with different decoding strategies
including greedy [32], sampling [52], 2-opt [19], MCTS [26], and so on. We
give a specific introduction to these decoding strategies in App. F. We
particularly align the decoding settings of DISCO with DIFUSCO [80] to
demonstrate its superiority as a diffusion solver. We follow Graikos et al.
[32] and use the Greedy+2-opt decoding strategy as the default for all
experiments. The sampling strategy is conducted by sampling 16 times for
TSP-500 and TSP-1000, and 4 times for TSP-10000 [80]. The MCTS decoding
strategy only samples one heatmap [71]. Unless otherwise specified, we set the
denoising steps of DISCO to 2 to demonstrate its efficiency advantage. For
DIFUSCO, we follow their settings and use 50 steps. We provide more evaluation
details in App. G.

The comprehensive results are summarized in Tab. 1. We observe that both
DIFUSCO and DISCO outperform the previous probabilistic solvers across all
three settings, with DISCO dominating at larger TSP-10000 problem scales, even
when combined with various decoding strategies. This underscores the
importance of the diffusion choice, which inherently possesses multi-modal
expressiveness that suits operation problems well. More importantly, DISCO
exhibits an absolute advantage in inference speed compared to DIFUSCO, with
its per-instance inference time achieving up to $44.8$ times speedup, better
satisfying many real-world applications that require time-sensitive responses.
We also evaluate DISCO on real-world TSP scenarios from TSPLIB [73] in App. E.
DISCO is the best performer in 28 out of 29 test cases while its inference
speed surpasses all compared algorithms, further validating the practicality
of our method. We also provide comparisons of DISCO with more recent learning-
based methods which are only trainable on small-scale instances in App. C,
with DISCO consistently maintaining its advantage on both inference speed and
solution quality. To facilitate a better understanding of our approach, we
provide visual comparisons of denoising results in App. D. These include the
evolution of generated heatmaps throughout the denoising process and the
correlation between the final solution quality and the total number of
diffusion steps.

###  5.3 Ablations on DISCO Components

We conduct ablation experiments on two key modules of DISCO: the analytical
denoising process and residue constraints. The results are summarized in Tab.
2. We can observe that for the version without the analytical denoising, which
can also be regarded as an equal implementation of DIFUSCO [80], its reverse
process requires 50 steps to achieve satisfactory results; otherwise, the
solution quality suffers. In contrast, with the analytical denoising process,
we can obtain a satisfactory solution in just 2 steps, significantly improving
inference speed. Moreover, the presence of residue constraints notably
enhances the quality of generated heatmaps, as evident from a direct example
in Fig. 3. The improvement in predicted heatmap quality naturally translates
into higher solution quality. , ultimately reflecting the efficacy of DISCO
motivation.

(a) W/o residue. (b) W/ residue.

Figure 3:  Akin to inner loops in a generated TSP heatmap (a), the denoised
samples without residues span an enormous NPC space, leading to frequent
failures in satisfying problem constraints as (b).

Table 2: Ablations on DISCO components. Step denotes the denoising step
number. A and R represent the analytical diffusion process and residue
constraints. Denoising with 1 step leads to near-zero variance, higher
confidence, and potentially better performance.

| Algorithm | Steps | TSP-1000 | TSP-10000
---|---|---|---|---
|  Length$\downarrow$ |  Gap(%)$\downarrow$ |  Time $\downarrow$ |  Length $\downarrow$ |  Gap(%)$\downarrow$ |  Time $\downarrow$
Greedy | W/o A&R | 50 | 23.56 | 1.90% |  12.06$\mathrm{m}$ | 73.99 | 3.10% |  35.38$\mathrm{m}$
W/o A&R | 2 | 24.72 | 6.92% |  1.37$\mathrm{m}$ | 78.25 | 9.03% |  27.01$\mathrm{m}$
W/o R | 2 | 24.02 | 3.89% |  1.33$\mathrm{m}$ | 78.01 | 8.69% |  20.60$\mathrm{m}$
DISCO | 2 | 23.86 | 3.20% |  1.37$\mathrm{m}$ | 74.94 | 4.42% |  26.18$\mathrm{m}$
DISCO | 1 | 23.65 | 2.29% |  1.12$\mathrm{m}$ | 73.85 | 2.90% |  25.12$\mathrm{m}$
Sampling | W/o A&R | 50 | 23.45 | 1.43% |  48.09$\mathrm{m}$ | 73.89 | 2.95% |  6.72$\mathrm{h}$
W/o A&R | 2 | 24.36 | 5.36% |  21.35$\mathrm{m}$ | 78.08 | 8.79% |  1.78$\mathrm{h}$
W/o R | 2 | 23.80 | 2.94% |  25.82$\mathrm{m}$ | 77.86 | 8.49% |  1.87$\mathrm{h}$
DISCO | 2 | 23.56 | 1.90% |  9.62$\mathrm{m}$ | 74.28 | 3.51% |  1.67$\mathrm{h}$
DISCO | 1 | 23.66 | 2.34% |  7.22$\mathrm{m}$ | 73.81 | 2.84% |  1.60$\mathrm{h}$

###  5.4 Multi-Modality Inspired Graph Search

Benefiting from DISCO’s verified advantage in both inference speed and
solution quality, we can apply our multi-modality inspired graph search method
to generalize a small-scale DISCO model $p_{\boldsymbol{\theta}}$ to solve the
arbitrary scale problem instances off the shelf. We train base model
$p_{\boldsymbol{\theta}}$ on TSP-100 instances and transfer it to
TSP-500/1000/10000 instances. The results are summarized in Tab. 3. We can
observe that when testing a trained model on a different problem scale,
although DISCO generalizes decently, it performs less effectively compared to
models trained on the equivalent scale. Meanwhile, our multi-modal graph
search algorithm, combined with $p_{\boldsymbol{\theta}}$ trained only on
TSP-100, exhibits better performance even when a substantial scale difference
exists. With just 50 trials, it can even outperform models trained on the
corresponding scale. Att-GCN [26] also adopts the decomposition mechanism for
enhancing generalization. However, their parameterized solver lacks the
ability to generate multiple trials, which causes the final solution may get
stuck in the sub-optimum and be less effective than DISCO. Although DIFUSCO
[80] also possesses the multi-modal property, its inference speed is
prohibitively slow, requiring extensive test time to obtain satisfactory
solutions.

While our graph search approach offers $\exp_{q}(|\mathbf{g}|)$ possibilities,
the final performance asymptotically converges to the number of sampled
trials, as confirmed in Fig. 4. The required sample number increases with
solution variance, which is controlled by the number of denoising steps. We
recommend 2-step denoising for better practice. We also compare our method
with a variant that does not generate multiple trials, i.e., merging all
generated heatmap sets $\mathcal{H}$ at once, revealing that the multi-
modality inspired search method generally outperforms this approach. This
amplifies the importance of solution diversity for solving offline CO
problems. DISCO’s performance can be further enhanced by trading off time
costs through various means such as increasing sampled trials, augmenting the
subgraph number $|\mathbf{g}|$ by controlling $\omega$, and re-decoding the
merged heatmap combinations corresponding to the most promising trial with
more sophisticated strategies like MCTS. These conclusions are also
corroborated in Table 3.

Table 3: Results on multi-modality inspired graph search. O means merging all
generated heatmap sets at once.

Algorithm | Type | Trial | TSP-500 | TSP-1000 | TSP-10000
---|---|---|---|---|---
Length $\downarrow$ |  Gap $\downarrow$ |  Time $\downarrow$ |  Length $\downarrow$ |  Gap $\downarrow$ |  Time $\downarrow$ |  Length $\downarrow$ |  Gap $\downarrow$ |  Time $\downarrow$
LKH-3 (default) | Heuristics | - |  16.55∗ | 0.00% |  46.28$\mathrm{m}$ |  23.12∗ | 0.00% |  2.57$\mathrm{h}$ |  71.77∗ | — |  8.8$\mathrm{h}$
Att-GCN | SL+MCTS | 1 | 16.97 | 2.54% |  2.20$\mathrm{m}$ | 23.86 | 3.22% |  4.10$\mathrm{m}$ | 74.93 | 4.39% |  21.49$\mathrm{m}$
DISCO (TSP-500) |  SL+G${\dagger}$+2-opt | 1 | 16.86 |  1.87% |  0.25$\mathrm{m}$ | 23.97 | 3.68% |  0.93$\mathrm{m}$ | 76.03 | 5.94% |  21.52$\mathrm{m}$
DISCO (TSP-1000) |  SL+G${\dagger}$+2-opt | 1 | 16.94 | 2.16% |  0.23$\mathrm{m}$ | 23.65 |  2.29% |  1.12$\mathrm{m}$ | 74.31 | 3.54% |  22.65$\mathrm{m}$
DISCO (TSP-10000) |  SL+G${\dagger}$+2-opt | 1 | 17.28 | 4.25% |  0.32$\mathrm{m}$ | 24.19 | 4.63% |  1.73$\mathrm{m}$ | 73.85 |  2.90% |  25.12$\mathrm{m}$
DIFUSCO + O |  SL+G${\dagger}$+2-opt | 1 | 17.20 | 3.70% |  2.00$\mathrm{h}$ | 24.00 | 3.81% |  4.46$\mathrm{h}$ | 74.33 | 3.57% |  4.91$\mathrm{h}$
DIFUSCO |  SL+G${\dagger}$+2-opt | 50 | 16.96 | 2.48% |  2.34$\mathrm{h}$ | 23.78 | 2.85% |  5.02$\mathrm{h}$ | 74.35 | 3.60% |  5.93$\mathrm{h}$
DISCO + O |  SL+G${\dagger}$+2-opt | 1 | 17.02 | 2.84% |  3.33$\mathrm{m}$ | 23.88 | 3.29% |  9.45$\mathrm{m}$ | 74.45 | 3.73% |  36.43$\mathrm{m}$
DISCO |  SL+G${\dagger}$+2-opt | 50 | 16.79 |  1.45% |  11.67$\mathrm{m}$ | 23.61 |  2.14% |  28.83$\mathrm{m}$ | 74.24 |  3.44% |  1.82$\mathrm{h}$
DISCO |  SL+G${\dagger}$+2-opt | 100 | 16.77 | 1.33% |  18.26$\mathrm{m}$ | 23.59 | 2.01% |  42.33$\mathrm{m}$ | 74.22 | 3.41% |  3.76$\mathrm{h}$
DISCO ($\omega=4$) |  SL+G${\dagger}$+2-opt | 50 | 16.78 | 1.39% |  17.53$\mathrm{m}$ | 23.61 | 2.12% |  44.93$\mathrm{m}$ | 74.23 | 3.43% |  2.18$\mathrm{h}$
DISCO | SL+MCTS | 50 | 16.70 | 0.91% |  18.81$\mathrm{m}$ | 23.54 | 1.82% |  42.19$\mathrm{m}$ | 73.69 | 2.68% |  2.10$\mathrm{h}$

Figure 4: Asymptotic performance of multi-modal graph search with trial
number.

Table 4: Results on MIS problems. TS denotes Tree Search [58].

Method | Type | SATLIB | ER-[700-800]
---|---|---|---
Size $\uparrow$ |  Gap $\downarrow$ |  Time $\downarrow$ |  Size $\uparrow$ |  Gap $\downarrow$ |  Time $\downarrow$
KaMIS | Heuristics |  425.96∗ | — |  37.58$\mathrm{m}$ |  44.87∗ | — |  52.13$\mathrm{m}$
Gurobi | Exact | 425.95 | 0.00% |  26.00$\mathrm{m}$ | 41.38 | 7.78% |  50.00$\mathrm{m}$
DGL | SL+TS | N/A | N/A | N/A | 37.26 | 16.96% |  22.71$\mathrm{m}$
Intel | SL+TS | N/A | N/A | N/A | 38.80 | 13.43% |  20.00$\mathrm{m}$
Intel | SL+G | 420.66 | 1.48% |  23.05$\mathrm{m}$ | 34.86 | 22.31% |  6.06$\mathrm{m}$
DIMES | RL+G | 421.24 | 1.11% |  24.17$\mathrm{m}$ | 38.24 | 14.78% |  6.12$\mathrm{m}$
DIFUSCO | SL+G | 424.50 | 0.34% |  13.00$\mathrm{m}$ | 38.83 | 12.40% |  8.80$\mathrm{m}$
DISCO (Ours) | SL+G | 424.58 | 0.32% |  10.32$\mathrm{m}$ | 40.30 | 10.17% |  9.00$\mathrm{m}$
LwD | RL+S | 422.22 | 0.88% |  18.83$\mathrm{m}$ | 41.17 | 8.25% |  6.33$\mathrm{m}$
DIMES | RL+S | 423.28 | 0.63% |  20.26$\mathrm{m}$ | 42.06 | 6.26% |  12.01$\mathrm{m}$
DIFUSCO | SL+S | 425.04 | 0.22% |  26.09$\mathrm{m}$ | 40.70 | 9.29% |  17.33$\mathrm{m}$
DISCO (Ours) | SL+S | 425.06 | 0.21% |  27.25$\mathrm{m}$ | 42.21 | 5.93% |  16.93$\mathrm{m}$

###  5.5 Evaluations on Maximal Independent Set

Besides TSP instances, we also evaluate DISCO on commonly studied MIS
problems, both of which are adequately representative of edge-based and node-
based NPC problems. Evaluations are conducted on SATLIB [38] and Erdős-Rényi
(ER) [25] graph sets, which exhibit challenge for recent learning-based
solvers [1; 9; 58; 71]. The training instances are labeled by the KaMIS
heuristic solver [54] with test instances aligned with [71]. We adopt the same
denoising steps and sample times as DIFUSCO [80] to distinguish model
capabilities. Specific details of experimental settings and baselines can be
found in App. B. We report the average size of the independent set (Size) in
Tab. 4. DISCO exhibits an absolute performance advantage over all competitor
algorithms.

##  6 Conclusion

We propose DISCO, an efficient diffusion solver for CO problems. DISCO obtains
rapidly generating high-quality solutions with very few denoising steps and
enhances solution quality by restricting the sampling space by solution
residues. DISCO achieves state-of-the-art results on large-scale TSP-10000
instances and challenging MIS benchmarks SATLIB and Erdős-Rényi, 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 those scales. This work focuses on solving offline problems
with supervised approaches. Integrating DISCO to address online problems
through trial and error is meaningful for future research. Employing an active
learning approach that directly determines the best trial for the multi-modal
graph search method, instead of sampling, would also be exciting.

##  7 Broader Impacts

Our proposed DISCO method is a general-purpose parameterized solver for CO
problems. DISCO leverages diffusion technologies to address the multi-modal
nature of CO problems effectively. DISCO optimizes both its forward and
reverse processes more efficiently for solution generation, and significantly
excels in both inference speed and solution quality. This improved efficiency
further enhances DISCO’s capabilities to generalize to arbitrary-scale
instances off the shelf. We believe that such efficient, learnable neural
solvers for NPC problems will have a positive impact on a broad range of real-
world applications [28; 91].

## References

  * [1] S. Ahn, Y. Seo, and J. Shin.  Learning what to defer for maximum independent sets.  In International Conference on Machine Learning, 2020.
  * [2] D. V. Andrade, M. G. Resende, and R. F. Werneck.  Fast local search for the maximum independent set problem.  Journal of Heuristics, 2012.
  * [3] D. Applegate, R. Bixby, V. Chvatal, and W. Cook.  Concorde tsp solver.  https://www.math.uwaterloo.ca/tsp/concorde/index.html, 2006.
  * [4] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio.  Neural combinatorial optimization with reinforcement learning.  arXiv preprint arXiv:1611.09940, 2016.
  * [5] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio.  Neural combinatorial optimization with reinforcement learning.  In International Conference on Learning Representations, Workshop, 2017.
  * [6] Y. Bengio, J. Louradour, R. Collobert, and J. Weston.  Curriculum learning.  In International Conference on Machine Learning, 2009.
  * [7] J. Bi, Y. Ma, J. Wang, Z. Cao, J. Chen, Y. Sun, and Y. M. Chee.  Learning generalizable models for vehicle routing problems via knowledge distillation.  Advances in Neural Information Processing Systems, 2022.
  * [8] A. Borodin and R. El-Yaniv.  Online Computation and Competitive Analysis.  Cambridge University Press, 2005.
  * [9] M. Böther, O. Kißig, M. Taraz, S. Cohen, K. Seidel, and T. Friedrich.  What’s wrong with deep learning in tree search for combinatorial optimization.  In International Conference on Learning Representations, 2022.
  * [10] X. Bresson and T. Laurent.  An experimental study of neural networks for variable graphs.  2018\.
  * [11] X. Bresson and T. Laurent.  The transformer network for the traveling salesman problem.  arXiv preprint arXiv:2103.03012, 2021.
  * [12] L. Brusca, L. C. Quaedvlieg, S. Skoulakis, G. Chrysos, and V. Cevher.  Maximum independent set: Self-training through dynamic programming.  Advances in Neural Information Processing Systems, 2024.
  * [13] X. Chen and Y. Tian.  Learning to perform local rewriting for combinatorial optimization.  Advances in Neural Information Processing Systems, 2019.
  * [14] C. Chi, S. Feng, Y. Du, Z. Xu, E. Cousineau, B. Burchfiel, and S. Song.  Diffusion policy: Visuomotor policy learning via action diffusion.  In Robotics: Science and Systems, 2023.
  * [15] J. Choo, Y.-D. Kwon, J. Kim, J. Jae, A. Hottung, K. Tierney, and Y. Gwon.  Simulation-guided beam search for neural combinatorial optimization.  Advances in Neural Information Processing Systems, 2022.
  * [16] W. J. Cook, D. L. Applegate, R. E. Bixby, and V. Chvátal.  The Traveling Salesman Problem: a Computational Study.  Princeton University Press, 2011.
  * [17] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.  Introduction to Algorithms.  MIT press, 2022.
  * [18] T. Cover and P. Hart.  Nearest neighbor pattern classification.  IEEE Transactions on Information Theory, 1967.
  * [19] G. A. Croes.  A method for solving traveling-salesman problems.  Operations Research, 1958.
  * [20] P. R. d O Costa, J. Rhuggenaath, Y. Zhang, and A. Akcay.  Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning.  In Asian Conference on Machine Learning, 2020.
  * [21] V.-A. Darvariu, S. Hailes, and M. Musolesi.  Solving graph-based public goods games with tree search and imitation learning.  Advances in Neural Information Processing Systems, 2021.
  * [22] M. Deudon, P. Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau.  Learning heuristics for the tsp by policy gradient.  In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2018.
  * [23] P. Dhariwal and A. Nichol.  Diffusion models beat gans on image synthesis.  Advances in Neural Information Processing Systems, 2021.
  * [24] A. Einstein et al.  On the motion of small particles suspended in liquids at rest required by the molecular-kinetic theory of heat.  Annalen Der Physik, 1905.
  * [25] P. Erdős, A. Rényi, et al.  On the evolution of random graphs.  Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 1960.
  * [26] Z. Fu, K. Qiu, and H. Zha.  Generalize a small pre-trained model to arbitrarily large TSP instances.  In AAAI Conference on Artificial Intelligence, 2021.
  * [27] M. R. Garey and D. S. Johnson.  Computers and Intractability.  Freeman San Francisco, 1979.
  * [28] G. Ghiani, F. Guerriero, G. Laporte, and R. Musmanno.  Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies.  European Journal of Operational Research, 2003.
  * [29] F. W. Glover and G. A. Kochenberger.  Handbook of Metaheuristics.  Springer Science & Business Media, 2006.
  * [30] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio.  Generative adversarial nets.  Advances in Neural Information Processing Systems, 2014.
  * [31] M. Gori, G. Monfardini, and F. Scarselli.  A new model for learning in graph domains.  In International Joint Conference on Neural Networks, 2005.
  * [32] A. Graikos, N. Malkin, N. Jojic, and D. Samaras.  Diffusion models as plug-and-play priors.  Advances in Neural Information Processing Systems, 2022.
  * [33] J. Gu, J. Bradbury, C. Xiong, V. O. K. Li, and R. Socher.  Non-autoregressive neural machine translation.  In International Conference on Learning Representation, 2018.
  * [34] K. Helsgaun.  An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems.  Roskilde University, 2017.
  * [35] J. Ho, A. Jain, and P. Abbeel.  Denoising diffusion probabilistic models.  In Advances in Neural Information Processing Systems, 2020.
  * [36] J. Ho, T. Salimans, A. Gritsenko, W. Chan, M. Norouzi, and D. J. Fleet.  Video diffusion models.  Advances in Neural Information Processing Systems, 2022.
  * [37] D. S. Hochba.  Approximation algorithms for np-hard problems.  ACM Sigact News, 1997.
  * [38] H. H. Hoos and T. Stützle.  Satlib: An online resource for research on sat.  Sat, 2000.
  * [39] A. Hottung, Y. Kwon, and K. Tierney.  Efficient active search for combinatorial optimization problems.  In International Conference on Learning Representations, 2022.
  * [40] Y. Huang, Z. Qin, X. Liu, and K. Xu.  Decoupled diffusion models with explicit transition probability.  arXiv preprint arXiv:2306.13720, 2023.
  * [41] Z. Huang, L. Liang, Z. Ling, X. Li, C. Gan, and H. Su.  Reparameterized policy learning for multimodal trajectory optimization.  In International Conference on Machine Learning, 2023.
  * [42] Z. Huang, P. Zhou, S. Yan, and L. Lin.  Scalelong: Towards more stable training of diffusion model via scaling network long skip connection.  Advances in Neural Information Processing Systems, 2023.
  * [43] B. Hudson, Q. Li, M. Malencia, and A. Prorok.  Graph neural network guided local search for the traveling salesperson problem.  In International Conference on Learning Representations, 2022.
  * [44] E. T. Jaynes.  Probability Theory: the Logic of Science.  Cambridge University Press, 2003.
  * [45] C. K. Joshi, Q. Cappart, L.-M. Rousseau, and T. Laurent.  Learning the travelling salesperson problem requires rethinking generalization.  Constraints, 2022.
  * [46] C. K. Joshi, T. Laurent, and X. Bresson.  An efficient graph convolutional network technique for the travelling salesman problem.  arXiv preprint arXiv:1906.01227, 2019.
  * [47] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song.  Learning combinatorial optimization algorithms over graphs.  Advances in Neural Information Processing Systems, 2017.
  * [48] M. Kim, J. Park, and J. Park.  Sym-nco: Leveraging symmetricity for neural combinatorial optimization.  Advances in Neural Information Processing Systems, 2022.
  * [49] D. Kingma, T. Salimans, B. Poole, and J. Ho.  Variational diffusion models.  Advances in Neural Information Processing Systems, 2021.
  * [50] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [51] L. Kocsis and C. Szepesvári.  Bandit based monte-carlo planning.  In European Conference on Machine Learning, pages 282–293. Springer, 2006.
  * [52] W. Kool, H. van Hoof, and M. Welling.  Attention, learn to solve routing problems!  In International Conference on Learning Representations, 2019.
  * [53] Y.-D. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, and S. Min.  Pomo: Policy optimization with multiple optima for reinforcement learning.  Advances in Neural Information Processing Systems, 2020.
  * [54] S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck.  Finding near-optimal independent sets at scale.  In Workshop on Algorithm Engineering and Experiments, 2016.
  * [55] E. L. Lawler and D. E. Wood.  Branch-and-bound methods: A survey.  Operations Research, 1966.
  * [56] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 1998.
  * [57] Y. Li, J. Guo, R. Wang, and J. Yan.  From distribution learning in training to gradient search in testing for combinatorial optimization.  Advances in Neural Information Processing Systems, 2024.
  * [58] Z. Li, Q. Chen, and V. Koltun.  Combinatorial optimization with graph convolutional networks and guided tree search.  Advances in Neural Information Processing Systems, 2018.
  * [59] Z. Li and X. Si.  Nsnet: A general neural probabilistic framework for satisfiability problems.  Advances in Neural Information Processing Systems, 2022.
  * [60] J. Liu, Q. Wang, H. Fan, Y. Wang, Y. Tang, and L. Qu.  Residual denoising diffusion models.  In Computer Vision and Pattern Recognition, 2024.
  * [61] LLC Gurobi Optimization.  Gurobi Optimizer Reference Manual, 2018.
  * [62] S. Luo, C. Yan, C. Hu, and H. Zhao.  Diff-foley: Synchronized video-to-audio synthesis with latent diffusion models.  Advances in Neural Information Processing Systems, 2024.
  * [63] Y. Ma, Z. Cao, and Y. M. Chee.  Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt.  In Advances in Neural Information Processing Systems, 2023.
  * [64] Y. Ma, Z. Cao, and Y. M. Chee.  Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt.  Advances in Neural Information Processing Systems, 2024.
  * [65] Y. Ma, J. Li, Z. Cao, W. Song, L. Zhang, Z. Chen, and J. Tang.  Learning to iteratively solve routing problems with dual-aspect collaborative transformer.  Advances in Neural Information Processing Systems, 2021.
  * [66] S. Martello, D. Pisinger, and D. Vigo.  The three-dimensional bin packing problem.  Operations Research, 2000.
  * [67] Z. Michalewicz and D. B. Fogel.  How to Solve It: Modern Heuristics.  Springer Science & Business Media, 2013.
  * [68] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al.  Human-level control through deep reinforcement learning.  Nature, 2015.
  * [69] A. Q. Nichol and P. Dhariwal.  Improved denoising diffusion probabilistic models.  In International Conference on Machine Learning, 2021.
  * [70] C. H. Papadimitriou and K. Steiglitz.  Combinatorial Optimization: Algorithms and Complexity.  Courier Corporation, 1998.
  * [71] R. Qiu, Z. Sun, and Y. Yang.  DIMES: A differentiable meta solver for combinatorial optimization problems.  In Advances in Neural Information Processing Systems, 2022.
  * [72] A. Radford, L. Metz, and S. Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks.  arXiv preprint arXiv:1511.06434, 2015.
  * [73] G. Reinelt.  Tsplib—a traveling salesman problem library.  ORSA Journal on Computing, 1991.
  * [74] A. Schrijver et al.  Combinatorial Optimization: Polyhedra and Efficiency.  Springer, 2003.
  * [75] J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, T. Graepel, et al.  Mastering atari, go, chess and shogi by planning with a learned model.  Nature, 2020.
  * [76] S. S. Seiden.  On the online bin packing problem.  Journal of the ACM, 2002.
  * [77] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  Nature, 2016.
  * [78] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In International Conference on Machine Learning, 2015.
  * [79] J. Song, C. Meng, and S. Ermon.  Denoising diffusion implicit models.  In International Conference on Learning Representations, 2021.
  * [80] Z. Sun and Y. Yang.  DIFUSCO: graph-based diffusion solvers for combinatorial optimization.  In Advances in Neural Information Processing Systems, 2023.
  * [81] I. Sutskever, O. Vinyals, and Q. V. Le.  Sequence to sequence learning with neural networks.  Advances in Neural Information Processing Systems, 2014.
  * [82] R. S. Sutton and A. G. Barto.  Reinforcement Learning: An Introduction.  MIT Press, 2018.
  * [83] É. D. Taillard and K. Helsgaun.  Popmusic for the travelling salesman problem.  European Journal of Operational Research, 2019.
  * [84] V. V. Vazirani.  Approximation Glgorithms.  Springer, 2001.
  * [85] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y. Bengio, et al.  Graph attention networks.  Stat, 2017.
  * [86] O. Vinyals, M. Fortunato, and N. Jaitly.  Pointer networks.  Advances in Neural Information Processing Systems, 2015.
  * [87] V. Voleti, A. Jolicoeur-Martineau, and C. Pal.  Mcvd-masked conditional video diffusion for prediction, generation, and interpolation.  Advances in Neural Information Processing Systems, 2022.
  * [88] L. A. Wolsey and G. L. Nemhauser.  Integer and Combinatorial Optimization.  John Wiley & Sons, 2014.
  * [89] Y. Wu, W. Song, Z. Cao, J. Zhang, and A. Lim.  Learning improvement heuristics for solving routing problems.  IEEE Transactions on Neural Networks and Learning Systems, 2021\.
  * [90] L. Xin, W. Song, Z. Cao, and J. Zhang.  Multi-decoder attention model with embedding glimpse for solving vehicle routing problems.  In AAAI Conference on Artificial Intelligence, 2021.
  * [91] Z. Xu, Z. Li, Q. Guan, D. Zhang, Q. Li, J. Nan, C. Liu, W. Bian, and J. Ye.  Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach.  In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018.
  * [92] H. Ye, J. Wang, Z. Cao, H. Liang, and Y. Li.  Deepaco: Neural-enhanced ant systems for combinatorial optimization.  Advances in Neural Information Processing Systems, 2024.
  * [93] E. Yolcu and B. Póczos.  Learning local search heuristics for boolean satisfiability.  Advances in Neural Information Processing Systems, 2019.
  * [94] P. Yu, Y. Zhu, S. Xie, X. S. Ma, R. Gao, S.-C. Zhu, and Y. N. Wu.  Learning energy-based prior model with diffusion-amortized mcmc.  Advances in Neural Information Processing Systems, 2024.
  * [95] C. Zhang, Z. Cao, W. Song, Y. Wu, and J. Zhang.  Deep reinforcement learning guided improvement heuristic for job shop scheduling.  In International Conference on Learning Representations, 2024.
  * [96] Y. Zhang, S. Wang, G. Ji, et al.  A comprehensive survey on particle swarm optimization algorithm and its applications.  Mathematical Problems in Engineering, 2015.
  * [97] H. Zhao, Z. Pan, Y. Yu, and K. Xu.  Learning physically realizable skills for online packing of general 3D shapes.  ACM Transactions on Graphics, 2023.
  * [98] H. Zhao, Q. She, C. Zhu, Y. Yang, and K. Xu.  Online 3D bin packing with constrained deep reinforcement learning.  In AAAI Conference on Artificial Intelligence, 2021.
  * [99] H. Zhao, Y. Yu, and K. Xu.  Learning efficient online 3D bin packing on packing configuration trees.  In International Conference on Learning Representations, 2021.
  * [100] H. Zhao, C. Zhu, X. Xu, H. Huang, and K. Xu.  Learning practically feasible policies for online 3D bin packing.  Science China Information Sciences, 2022.

## Appendix

##  Appendix A Equivalence Analysis between DDM and DISCO

Real-world combinatorial optimization (CO) problems often require the rapid
generation of high-quality solutions $\mathbf{X}_{s}$ for problem instance
$s$. Previous neural solvers have suffered from the expressiveness limitation
when confronted with multiple optimal solutions for the same graph [33, 47,
58]. In contrast, diffusion probabilistic models (DPMs) [35] have shown
promising prospects for generating a wide variety of distributions suitable
for CO solving. The only bottleneck is the slow inference speed of DPMs. This
is due to DPMs employing numerical integration during the reverse process,
requiring multiple steps of accumulation and solving and significantly
incurring time overhead.

Inspired by decoupled diffusion models (DDMs) [40], we substitute the time-
consuming numerical integration process with an analytically solvable form.
The original solution-to-noise mapping can be decoupled into solution-to-zero
and zero-to-noise mapping:

$\mathbf{x}_{t}=\mathbf{x}_{0}+\int_{0}^{t}\mathbf{f}_{t}dt+\int_{0}^{t}d\mathbf{w}_{t},\quad\mathbf{x}_{0}\sim
q(\mathbf{x}_{0}),$ (11)

where $\mathbf{x}_{0}+\int_{0}^{t}\mathbf{f}_{t}dt$ describes the solution
attenuation and $\int_{0}^{t}d\mathbf{w}_{t}$ describes the noise
accumulation. Since $\mathbf{f}_{t}$ can be designed analytically, the
efficiency of the reversed process can be improved by much fewer evaluation
steps, e.g., inference steps = 1 or 2. The distribution of $\mathbf{x}_{t}$
conditioned on $\mathbf{x}_{0}$ is defined as:

$q(\mathbf{x}_{t}\mid\mathbf{x}_{0})=\mathcal{N}(\mathbf{x}_{t};\mathbf{x}_{0}+\mathbf{F}_{t},t\mathbf{I}),$
(12)

where $\mathbf{F}_{t}=\int_{0}^{t}\mathbf{f}_{t}d_{t}$ and we sample
$\mathbf{x}_{t}$ by
$\mathbf{x}_{t}=\mathbf{x}_{0}+\mathbf{F}_{t}+\sqrt{t}\boldsymbol{\epsilon}$
with $\boldsymbol{\epsilon}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$.

For a reverse time, the sampling formula for $\mathbf{x}_{0}$ is based on the
analytic attenuation function $\mathbf{f}_{t}$ that models image to zero
transition. We employ continuous-time Markov chain with the smallest time step
$\delta t\rightarrow 0^{+}$ and use conditional distribution
$q(\mathbf{x}_{t-\Delta t}\mid\mathbf{x}_{t},\mathbf{x}_{0})$ to approximate
$q(\mathbf{x}_{t-\Delta t}\mid\mathbf{x}_{t},\mathbf{x}_{0})$.

$q(\mathbf{x}_{t-\Delta
t}\mid\mathbf{x}_{t},\mathbf{x}_{0})\propto\exp\left\\{-\frac{(\mathbf{x}_{t-\Delta
t}-\widetilde{\mathbf{u}})^{2}}{2\widetilde{\sigma}^{2}\mathbf{I}}\right\\},$
(13)

where $\boldsymbol{\epsilon}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$,
$\widetilde{\mathbf{u}}=\mathbf{x}_{t}+\mathbf{F}_{t-\Delta
t}-\mathbf{F}_{t}+\boldsymbol{\epsilon}\Delta t/\sqrt{t}$, and
${\widetilde{\sigma}}^{2}=\Delta t(t-\Delta t)/t$. Since $\mathbf{f}_{t}$ has
an analytic form, we can avoid the ordinary differential equation-based
denoising and instead directly sample $\mathbf{x}_{0}$ with an arbitrary step
size, which significantly reduces the inference time.

Although the inference speed can benefit from the analytically solvable form,
denoising methods still require inefficient sampling from the entire NPC
solution space of CO problems, which typically grows exponentially with the
number of problem scale $N$. We propose to constrain the sampling space into a
smaller one by introducing residues [60] to DDM, which is our DISCO method,
i.e., an efficient DIffusion Solver for CO problems. The reversed process
starts from both noise and an exceedingly cost-effective degraded solution,
confining the generation process in a smaller but more meaningful domain close
to the high-quality labels. The residue prioritizes certainty while the noise
emphasizes diversity, so that to ensure solution effectiveness while still
maintaining their multi-modality property

Instead of the traditional forward process merely outputting noise, it is now
a combination of noise $\mathbf{x}_{t}$ and a degraded solution
$\mathbf{X}_{d}$ for generating residue constraints
$\mathbf{x}_{res}=\mathbf{X}_{d}-\mathbf{x}_{0}$. The degraded solution
$\mathbf{X}_{d}$ is an exceedingly cost-effective path but satisfies problem
constants. For example, $0-1-\ldots-n-0$, connecting nodes in sequential
order. Since DDM has already demonstrated its equivalence to previous
diffusion processes defined by Equation 3 [40], we now provide proof of the
equivalence between our method and DDM to demonstrate the effectiveness of
DISCO in a theoretical aspect.

#### Forward Process

The proposed forward formula considering residue is:

$\mathbf{x}_{t}=\mathbf{x}_{0}+\int_{0}^{t}\mathbf{x}_{res}dt+\sqrt{t}\boldsymbol{\epsilon}.$
(14)

Compared with the original forward formulation of DDM (Eq. 4), the proposed
forward formulation utilizes a different function $\mathbf{x}_{res}$
substituting the attenuation function $\mathbf{f}_{t}$, which means the two
diffusion processes are equivalent.

#### Reversed Process

In the reversed process, we need to parameterize two components:
$\mathbf{x}_{res}^{\boldsymbol{\theta}}$ and
$\boldsymbol{\epsilon}^{\boldsymbol{\theta}}$, which estimate the residue
$\mathbf{x}_{res}$ and the noise $\boldsymbol{\epsilon}$, respectively. From
Eq. 7, we have:

$\mathbf{x}_{0}=\mathbf{x}_{t}-\int_{0}^{t}\mathbf{x}_{res}dt-\sqrt{t}\boldsymbol{\epsilon}.$
(15)

Thus, the reverse process can be defined as:

$p_{\theta}(\mathbf{x}_{t-\Delta t}\mid\mathbf{x}_{t}):=q(\mathbf{x}_{t-\Delta
t}\mid\mathbf{x}_{t},\mathbf{x}_{0}).$ (16)

Applying Bayes’ theorem [44], we obtain:

$\displaystyle q(\mathbf{x}_{t-\Delta t}\mid\mathbf{x}_{t},\mathbf{x}_{0})$
$\displaystyle=\frac{q(\mathbf{x}_{t}\mid\mathbf{x}_{t-\Delta
t})q(\mathbf{x}_{t-\Delta
t}\mid\mathbf{x}_{t})}{q(\mathbf{x}_{t}\mid\mathbf{x}_{0})}$ (17)
$\displaystyle=\frac{q(\mathbf{x}_{t}\mid\mathbf{x}_{t-\Delta
t})\mathcal{N}(\mathbf{x}_{t-\Delta t};\mathbf{x}_{0}+\mathbf{H}_{t-\Delta
t},(t-\Delta
t)\mathbf{I})}{\mathcal{N}(\mathbf{x}_{t};\mathbf{x}_{0}+\mathbf{F}_{t},t\mathbf{I})}.$

Eq. 17 aligns with the reverse process in DDM, thus the reverse process
formula is:

$q(\mathbf{x}_{t-\Delta
t}\mid\mathbf{x}_{t},\mathbf{x}_{0})\propto\exp{\left(-\frac{(\mathbf{x}_{t-\Delta
t}-\mathbf{u})^{2}}{2\sigma^{2}\mathbf{I}}\right)},$ (18)

where $\widetilde{\mathbf{u}}=\mathbf{x}_{t}-\int_{t_{-}\Delta
t}^{t}h_{t}dt-\frac{\Delta
t}{\sqrt{t}}\epsilon,\widetilde{\sigma}^{2}=\frac{\Delta t(t-\Delta t)}{t}$,
equivalent to the reverse formula of DDM.

##  Appendix B Maximal Independent Set

Besides the TSP problem, we also evaluate DISCO on commonly studied MIS
problems, both of which are adequately representative of edge-based and node-
based NPC problems. We give specific details of experimental settings in this
section.

#### Datasets

We conduct evaluations on SATLIB [38] and Erdős-Rényi (ER) [25] graph sets,
which exhibit challenge for recent learning-based solvers [1, 9, 58, 71]. The
training instances of labeled by the KaMIS heuristic solver [54]. The split of
test instances on SAT datasets and the random-generated ER test graphs are
taken from [71].

#### Metrics

We compare the performance of different probabilistic solvers by the average
size (Size) of the predicted maximal independent set for each test instance;
larger sizes indicate better performance. We also use the same Gap and Time
definitions as in the TSP case. We adopt the same denoising steps and sample
times as DIFUSCO [80] to distinguish model capabilities. Specifically, we use
50 steps for denoising heatmap and generate 4 times for sampling strategies.
Following the principle of efficiency, we random sample a set of nodes from
the original graph with a probability of 50% to obtain the degraded solution.

#### Baselines

We compare DISCO with 7 other MIS solvers on the same test sets, including two
traditional OR methods and five learning-based approaches. For the traditional
methods, we use Gurobi and KaMIS [54] as baselines. For the learning-based
methods, we compare with LwD [1], Intel [58], DGL [9], DIMES [71], and DIFUSCO
[80].

##  Appendix C Comparisons on Small-Scale TSP Instances

Table 5: Comparisons on TSP-50 and TSP-100. The symbol $*$ denotes the
baseline for computing the performance gap. The symbol ${\dagger}$ indicates
that the diffusion model samples once.

Algorithm | Type | TSP-50 | TSP-100
---|---|---|---
Length$\downarrow$ |  Gap(%)$\downarrow$ |  Length $\downarrow$ |  Gap(%)$\downarrow$
Concorde | Exact |  5.69∗ | 0.00 |  7.76∗ | 0.00
2-OPT | Heuristics | 5.86 | 2.95 | 8.03 | 3.54
AM | Greedy | 5.80 | 1.76 | 8.12 | 4.53
GCN | Greedy | 5.87 | 3.10 | 8.41 | 8.38
Transformer | Greedy | 5.71 | 0.31 | 7.88 | 1.42
POMO | Greedy | 5.73 | 0.64 | 7.84 | 1.07
Sym-NCO | Greedy | - | - | 7.84 | 0.94
DPDP |  $1k$-Improvements | 5.70 | 0.14 | 7.89 | 1.62
Image Diffusion |  Greedy${\dagger}$ | 5.76 | 1.23 | 7.92 | 2.11
DIFUSCO |  Greedy${\dagger}$ | 5.70 | 0.10 | 7.78 | 0.24
DISCO (Ours) |  Greedy${\dagger}$ | 5.70 | 0.16 | 7.80 | 0.58
AM |  $1k\times$Sampling | 5.73 | 0.52 | 7.94 | 2.26
GCN |  $2k\times$Sampling | 5.70 | 0.01 | 7.87 | 1.39
Transformer |  $2k\times$Sampling | 5.69 | 0.00 | 7.76 | 0.39
POMO |  $8\times$Augment | 5.69 | 0.03 | 7.77 | 0.14
Sym-NCO |  $100\times$Sampling | - | - | 7.79 | 0.39
MDAM |  $50\times$Sampling | 5.70 | 0.03 | 7.79 | 0.38
DPDP |  $100k$-Improvements | 5.70 | 0.00 | 7.77 | 0.00
DIFUSCO |  $16\times$Sampling | 5.69 | -0.01 | 7.76 | -0.01
DISCO (Ours) |  $16\times$Sampling | 5.69 | -0.01 | 7.76 | 0.03

Some learning-based solvers struggle with large problem scales, we compare
them on small-scale instances to ensure fairness. Specifically, we compare
with learning-based methods Image Diffusion [32], Transformer [11], Sym-NCO
[48], DPDP [65], and MDAM [90]. Along with the learning-based methods works on
large scales including AM [52], GCN [46], POMO [53], EAN [22], POMO + EAS
[39], Att-GCN [26], DIMES [71], and DIFUSCO [80]. We also make comparisons
with traditional operation methods including Concorde [3] and Gurobi [61],
LKH-3 [34], 2-OPT [19], and Farthest Insertion [16]. We label the training
instances using the Concorde solver for TSP-50/100 and we take the same test
instances as [45, 52]. The comprehensive results are summarized in Tab. 5,
with DISCO consistently maintaining its advantage on both inference speed and
solution quality. We visualize the performance and time-cost of DISCO on
TSP-50 in Fig. 5, along with performance comparisons with previous diffusion
solver DIFUSCO [80]. Corresponding denoising processes are provided in Fig. 6.

(a) Performance of baseline.(b) Performance of DISCO.(c) Runtime of DISCO.

Figure 5: The performance of both the baseline method DIFUSCO [80] (a) and
DISCO (b) on TSP-50 instances with different denoising steps and sample
number. Corresponding per-instance run-time ($\mathrm{sec}$) of diffusion-
based methods is depicted in (c). The negative performance gap arises because
the Concorde solver, used for providing labels, only accepts integer
coordinates as inputs, resulting in inaccurate non-optimal solutions due to
rounding issues. For DISCO with a denoising step of 1, its variance $\sigma$
tends to zero, as described by Eq. 8, yielding relatively more confident
solutions and potentially better performance. However, this does not lead to
performance improvement in response to actively sampling more times.

DIFUSCO

DISCO w/o R

DISCO (Ours)

NoiseStep 1Step 2Step 3Step 4Step 5

Figure 6: Denoising processes on TSP-50. Decoding the final heatmap with
Greedy+2-opt yields tour lengths of 5.95 for DIFUSCO, 5.77 for DISCO without
residues (w/o R), and 5.75 for DISCO.

##  Appendix D Qualitative Results

###  D.1 Denoising Processes on Large-Scale Instances

We illustrate the denoising processes of different diffusion methods on large-
scale problems in Figure 7, using TSP-1000 as an example for clarity. The
analytical denoising design and introduction of residues in DISCO ensure that
high-quality solutions can be obtained with a few steps. In contrast,
alternative methods generate solutions that frequently violate problem
constraints, such as isolated nodes, non-closed tours, and inner loops.

DIFUSCO

DISCO w/o R

DISCO (Ours)

NoiseStep 1Step 2Step 3Step 4Step 5

Figure 7: Denoising processes on TSP-1000. Decoding the final heatmap with
Greedy+2-opt yields tour lengths of 27.69 for DIFUSCO, 26.33 for DISCO without
residues (w/o R), and 25.35 for DISCO.

###  D.2 Performance with Different Denoising Steps

Here, we demonstrate the final heatmaps $\mathbf{x}_{0}$ generated by
different denoising steps with different diffusion methods. The visualizations
are summarized in Fig. 8, which still opt for TSP-1000 to ensure readability.
The corresponding decoded tour lengths are annotated directly below each plot.
It is evident that DISCO consistently produces high-quality solutions across
various denoising steps. Particularly for time-sensitive scenarios requiring
few denoising steps, DISCO maintains a significant advantage over the
baselines.

DIFUSCO

DISCO w/o R

DISCO (Ours)

28.4228.2827.6927.2525.1424.8428.2027.9126.3325.6425.0624.7927.7227.4325.3525.0524.4424.39Step
1Step 2Step 5Step 10Step 20Step 50

Figure 8:  Generated heatmaps on TSP 1000-instances under different denoising
steps, with the final decoded tour length captioned below. DISCO consistently
produces higher-quality heatmaps that better satisfy the problem constraints,
leading to better decoding results with the same number of denoising steps.

##  Appendix E Generalization to Real-World Instances

We evaluate DISCO on TSPLIB [73], a collection of real-world TSP scenarios, to
assess its effectiveness in transferring knowledge from the synthetically
generated data to the real world. We directly transfer the DISCO models
trained on TSP-50 and TSP-100 to these real-world instances without any fine-
tuning. Each instance strictly follows the evaluation protocol proposed by
TSPLIB. The results are summarized in Tab. 6. We can observe that DISCO is the
best performer in 28 out of 29 test cases. Notably, as a diffusion-based
algorithm, DISCO’s solving speed is the fastest among all compared algorithms
across all cases, further demonstrating its efficiency advantage and
practicality. The test code and models for this part are provided in the
Supplementary Material for reproducibility. We also provide visualizations of
each solution generated by DISCO in Fig. 9.

Table 6:  TSPLIB performance. We indicate the training scales for
DISCO/DIFUSCO in parentheses.

Method |  Kool et al. [52] |  Joshi et al.[46] |  Costa et al. [20] |  Hudson et al. [43] | DIFUSCO (50) | DIFUSCO (100) | DISCO (50) | DISCO (100)
---|---|---|---|---|---|---|---|---
Instance | Time (s) | Gap (%) | Time (s) | Gap (%) | Time (s) | Gap (%) | Time (s) | Gap (%) | Time (s) | Gap (%) | Time (s) | Gap (%) | Time (s) | Gap (%) | Time (s) | Gap (%)
eil51 | 0.125 | 1.628 | 3.026 | 8.339 | 28.051 | 0.067 | 10.074 | 0.000 | 0.482 | 0.000 | 0.519 | 0.117 | 0.049 | 0.000 | 0.049 | 0.000
berlin52 | 0.129 | 4.169 | 3.068 | 33.225 | 31.874 | 0.449 | 10.103 | 0.142 | 0.527 | 0.000 | 0.526 | 0.000 | 0.047 | 0.000 | 0.048 | 0.000
st70 | 0.200 | 1.737 | 4.037 | 24.785 | 23.964 | 0.040 | 10.053 | 0.764 | 0.663 | 0.000 | 0.670 | 0.000 | 0.062 | -0.741 | 0.064 | -0.741
eil76 | 0.225 | 1.992 | 4.303 | 27.411 | 26.551 | 0.096 | 10.155 | 0.163 | 0.788 | 0.000 | 0.788 | 0.174 | 0.076 | -0.557 | 0.072 | -0.557
pr76 | 0.226 | 0.816 | 4.378 | 27.793 | 39.485 | 1.228 | 10.049 | 0.039 | 0.765 | 0.000 | 0.785 | 0.187 | 0.074 | -0.379 | 0.072 | -0.379
rat99 | 0.347 | 2.645 | 5.559 | 17.633 | 32.188 | 0.123 | 9.948 | 0.550 | 1.236 | 1.187 | 1.192 | 0.000 | 0.115 | 0.000 | 0.103 | -0.165
kroA100 | 0.352 | 4.017 | 5.705 | 28.828 | 42.095 | 18.313 | 10.255 | 0.728 | 1.259 | 0.741 | 1.217 | 0.000 | 0.110 | -0.019 | 0.106 | -0.019
kroB100 | 0.352 | 5.142 | 5.712 | 34.686 | 35.137 | 1.119 | 10.317 | 0.147 | 1.252 | 0.648 | 1.235 | 0.742 | 0.116 | 0.235 | 0.108 | 0.262
kroC100 | 0.352 | 0.972 | 5.641 | 35.506 | 34.333 | 0.349 | 10.172 | 1.571 | 1.199 | 1.712 | 1.168 | 0.000 | 0.108 | 0.029 | 0.103 | -0.067
kroD100 | 0.352 | 2.717 | 5.621 | 38.018 | 25.772 | 0.866 | 10.375 | 0.572 | 1.226 | 0.000 | 1.175 | 0.000 | 0.118 | -0.117 | 0.110 | -0.117
kroE100 | 0.352 | 1.470 | 5.650 | 26.589 | 34.475 | 1.832 | 10.270 | 1.216 | 1.208 | 0.274 | 1.197 | 0.274 | 0.114 | 0.168 | 0.110 | 0.000
rd100 | 0.352 | 3.407 | 5.737 | 50.432 | 28.963 | 0.003 | 10.125 | 0.459 | 1.191 | 0.000 | 1.172 | 0.000 | 0.101 | -0.733 | 0.097 | -0.733
eil101 | 0.359 | 2.994 | 5.790 | 26.701 | 23.842 | 0.387 | 10.276 | 0.201 | 1.222 | 0.576 | 1.215 | 0.000 | 0.114 | -0.318 | 0.107 | -0.318
lin105 | 0.380 | 1.739 | 5.938 | 34.902 | 39.517 | 1.867 | 10.330 | 0.606 | 1.321 | 0.000 | 1.280 | 0.000 | 0.124 | -0.306 | 0.107 | -0.306
pr107 | 0.391 | 3.933 | 5.964 | 80.564 | 29.039 | 0.898 | 9.977 | 0.439 | 1.381 | 0.228 | 1.378 | 0.415 | 0.148 | -0.199 | 0.144 | -0.169
pr124 | 0.499 | 3.677 | 7.059 | 70.146 | 29.570 | 10.322 | 10.360 | 0.755 | 1.803 | 0.925 | 1.782 | 0.494 | 0.144 | 0.198 | 0.144 | 0.151
bier127 | 0.522 | 5.908 | 7.242 | 45.561 | 39.029 | 3.044 | 10.260 | 1.948 | 1.938 | 1.011 | 1.915 | 0.366 | 0.176 | -0.379 | 0.169 | -1.026
ch130 | 0.550 | 3.182 | 7.351 | 39.090 | 34.436 | 0.709 | 10.032 | 3.519 | 1.989 | 1.970 | 1.967 | 0.077 | 0.153 | 0.245 | 0.162 | -0.016
pr136 | 0.585 | 5.064 | 7.727 | 58.673 | 31.056 | 0.000 | 10.379 | 3.387 | 2.184 | 2.490 | 2.142 | 0.000 | 0.146 | 0.069 | 0.180 | -0.342
pr144 | 0.638 | 7.641 | 8.132 | 55.837 | 28.913 | 1.526 | 10.276 | 3.581 | 2.478 | 0.519 | 2.446 | 0.261 | 0.159 | -0.063 | 0.186 | -0.063
ch150 | 0.697 | 4.584 | 8.546 | 49.743 | 35.497 | 0.312 | 10.109 | 2.113 | 2.608 | 0.376 | 2.555 | 0.000 | 0.169 | 0.276 | 0.202 | -0.061
kroA150 | 0.695 | 3.784 | 8.450 | 45.411 | 29.399 | 0.724 | 10.331 | 2.984 | 2.617 | 3.753 | 2.601 | 0.000 | 0.174 | 0.033 | 0.208 | -0.098
kroB150 | 0.696 | 2.437 | 8.573 | 56.745 | 29.005 | 0.886 | 10.018 | 3.258 | 2.626 | 1.839 | 2.592 | 0.067 | 0.176 | 0.554 | 0.206 | 0.417
pr152 | 0.708 | 7.494 | 8.632 | 33.925 | 29.003 | 0.029 | 10.267 | 3.119 | 2.716 | 1.751 | 2.712 | 0.481 | 0.183 | 0.122 | 0.221 | -0.062
u159 | 0.764 | 7.551 | 9.012 | 38.338 | 28.961 | 0.054 | 10.428 | 1.020 | 2.963 | 3.758 | 2.892 | 0.000 | 0.184 | -0.067 | 0.196 | -0.067
rat195 | 1.114 | 6.893 | 11.236 | 24.968 | 34.425 | 0.743 | 12.295 | 1.666 | 4.400 | 1.540 | 4.428 | 0.767 | 0.266 | 0.947 | 0.310 | 0.560
d198 | 1.153 | 373.020 | 11.519 | 62.351 | 30.864 | 0.522 | 12.596 | 4.772 | 4.615 | 4.832 | 4.153 | 3.337 | 0.297 | 0.330 | 0.375 | 0.292
kroA200 | 1.150 | 7.106 | 11.702 | 40.885 | 33.832 | 1.441 | 11.088 | 2.029 | 4.710 | 6.187 | 4.686 | 0.065 | 0.301 | 1.134 | 0.346 | -0.398
kroB200 | 1.150 | 8.541 | 11.689 | 43.643 | 31.951 | 2.064 | 11.267 | 2.589 | 4.606 | 6.605 | 4.619 | 0.590 | 0.301 | 1.481 | 0.346 | 0.065
Mean | 0.532 | 16.767 | 7.000 | 40.025 | 31.766 | 1.725 | 10.420 | 1.529 | 1.999 | 1.480 | 1.966 | 0.290 | 0.149 | 0.067 | 0.161 | -0.136

Figure 9: Visualization of DISCO’s generated solutions on TSPLIB instances.

##  Appendix F Decoding Strategy

For offline problems [66, 70], all input data and all constraints are fully
provided before solving the problems. The decision-makers can fully utilize
all relevant information for comprehensive analysis and iteratively improve
solution quality. Providing an initial solution by SL and further refining it
by decoding strategies has become a common practice [22]. We introduce the
following decoding strategies combined with DISCO, including greedy strategy
[32], sampling strategy [52], 2-OPT decoding strategy [19], and MCTS [26].

#### Greedy Strategy

We use a straightforward greedy strategy to decode solutions from heatmaps
produced by probabilistic models. Specifically, we iteratively add the
highest-scoring candidates among the remaining ones to the partial solution.
We repeat this process until all relevant nodes/edges are incorporated. For
diffusion-based methods, we sample the initial solution once with a single
noise data $\mathbf{x}_{t}$. We set the denoising step as 1 for DISCO when
executing this greedy strategy, allowing the variance $\sigma$ to approach
zero (as described in Eq. 8) to generate more confident solutions.

#### Sampling Strategy

Probabilistic solvers usually sample multiple solutions [52] through various
means and execute the best one. Statistically, increasing the number of
samples can enhance the breadth and depth while exploring the solution space,
thereby increasing the probability of finding higher-quality solutions [96].
Following this logic, we generate multiple heatmaps from
$p_{\boldsymbol{\theta}}(\mathbf{x}_{0}|s)$ with different noise data
$\mathbf{x}_{t}$ and then apply the greedy decoding algorithm described above
to each heatmap. For DISCO, we set the denoising step over 1 for heatmap
generation, which allows the variance $\sigma$ to be non-zero to enrich
solution diversity, while introducing solution residues to constrain
generations as high-quality as possible.

#### 2-opt Strategy

We also adopt a 2-opt decoding strategy [2] to refine the greedy solutions of
TSP tasks. Specifically, we iteratively swap two edges in the current solution
to reduce the total length of the tour. We repeat this process until no
further improvement can be made. We follow Graikos et al. [32] and use this
Greedy+2-opt decoding strategy as the default.

#### Monte Carlo Tree Search

Building on the work of Fu et al., [26], we enhance TSP solutions with Monte
Carlo tree search (MCTS) [75, 77]. We employ $k$-opt transformation actions
guided by heatmaps produced by the parameterized model to refine current
solutions. MCTS executes simulation, selection, and back-propagation phases
until the sampling pool yields no further improvements. Although MCTS
typically exhibits stronger performance than other decoding methods, its
iterative solution updating approach also tends to incur higher computational
costs. We recommend that our users select the appropriate decoding strategy
based on their customized needs.

We conduct DISCO combined with all these strategies on TSP instances to
demonstrate its robustness. Following instructions from [9], we only conduct
greedy strategy and sampling strategy on MIS instances to fairly compare the
capabilities of different parameterized solvers.

##  Appendix G Implementation Details

#### Training Setting

We adopt anisotropic GNNs [85] as the backbone of our DISCO model. Anisotropic
GNNs can produce embeddings for both nodes and edges, which exactly match the
CO problems most of which can be formulated as graph problems. Specifically,
we input the noisy solution $\mathbf{x}_{t}$, the node and edge features of
$\mathbf{X}_{d}$, and the time $t$ into the anisotropic GNN with parameter
$\boldsymbol{\theta}$, predicting the parameterized residue
$\mathbf{x}_{res}^{\boldsymbol{\theta}}$ and noise
$\boldsymbol{\epsilon}^{\boldsymbol{\theta}}$ simultaneously. We adopt a
linear schedule [40] to gradually reduce the noise during the model’s
generation process.

Following Sun and Yang [80], we implement sparsification in large-scale graph
problems to diminish computational complexity. We constrain each node to
maintain only $k$ edges connecting to its closest neighbors. Specifically, we
limit $k$ to 50 for TSP-500 and increase it to 100 for TSP-1000/10000. We also
directly transfer the trained models to the same graphs with different
sparsifications without fine-tuning, the generalization results are summarized
in Tab. 7. We can observe that DISCO performs consistently stable while the
sparsification changes, indicating its robustness.

Table 7: Evaluation results on different sparsification $k$. The symbol
$\circ$ indicates the sparsification used for training, while the other lines
are directly generalized without fine-tuning.

Algorithm | Type | $k$ | TSP-500 | TSP-1000 | TSP-10000
---|---|---|---|---|---
Length $\downarrow$ |  Time $\downarrow$ |  Length $\downarrow$ |  Time $\downarrow$ |  Length $\downarrow$ |  Time $\downarrow$
DISCO |  SL+G${\dagger}$+2-opt | 50 |  16.86∘ |  0.25$\mathrm{m}$ | 23.70 |  0.78$\mathrm{m}$ | 73.85 |  24.80$\mathrm{m}$
DISCO |  SL+G${\dagger}$+2-opt | 100 | 16.99 |  0.50$\mathrm{m}$ |  23.65∘ |  1.12$\mathrm{m}$ |  73.85∘ |  25.12$\mathrm{m}$
DISCO | SL+S+2-opt | 50 |  16.73∘ |  3.88$\mathrm{m}$ | 23.60 |  8.93$\mathrm{m}$ | 73.82 |  1.48$\mathrm{h}$
DISCO | SL+S+2-opt | 100 | 16.85 |  6.68$\mathrm{m}$ |  23.56∘ |  9.62$\mathrm{m}$ |  73.81∘ |  1.60$\mathrm{h}$
DISCO | SL+MCTS | 50 |  16.63∘ |  6.99$\mathrm{m}$ | 23.62 |  14.25$\mathrm{m}$ | 73.58 |  42.03$\mathrm{m}$
DISCO | SL+MCTS | 100 | 16.70 |  7.07$\mathrm{m}$ |  23.42∘ |  15.82$\mathrm{m}$ |  73.56∘ |  42.35$\mathrm{m}$

For the TSP-50 and TSP-100 instances, we utilize 1502000 random instances,
training with batch sizes of 256 and 128 respectively. For TSP-500 and
TSP-1000 challenges, we train DISCO with instances of 128000 and 64000 and
batch size of 32. For TSP-10000, the model is trained using 6,400 instances
with a batch size of 4. Align with DIFUSCO [80], we incorporate curriculum
learning approach[6] and begin the training process for TSP-500/1000 from the
TSP-100 checkpoint, and for TSP-10000 from the TSP-500 checkpoint. We label
the training instances for TSP-50/100 using the Concorde solver. For
TSP-500/1000/10000, we label training instances using the LKH-3 heuristic
solver [34] with 1000 trials.

For the MIS instances, we use the training split of 49500 examples from SATLIB
[38], training with a batch size of 64. For Erdős-Rényi [25] graph sets, we
use 60000 random instances from the ER-[700-800] variant and train DISCO with
a batch size of 16. The training instances of labeled by the KaMIS heuristic
solver [54].

#### Evaluation Details

We conduct extensive evaluations on both TSP and MIS instances to demonstrate
the superiority of our DISCO model. We keep our experimental settings
consistent with previous literature [71, 80]. For TSP-500 and TSP-1000, we
take 128 instances as the test set, while for TSP-10000, we use 16 instances.
For small-scale TSP instances, i.e., TSP-50 and TSP-100, we evaluate on 1280
instances. For MIS instances, we evaluate on 500 instances on SATLIB [38] and
128 instances on ER-[700-800] [25] graph sets.

Given that diffusion models are capable of generating diverse samples from
their distribution, for each experiment, we evaluate DISCO 5 times with
different random seeds and report the averaged results. We summarize the
experimental results on large-scale TSP instances in Tab. 8. We also provide
the standard deviation (Std) of these repeated evaluations to demonstrate the
stability of our method. Our algorithm consistently demonstrates low variance
and little fluctuations in performance, indicating its robustness across
different runs.

Table 8: Statistical analysis of repeated evaluations on large-scale TSP
problems. MS denotes our multi-modality inspired graph search method, where
each search samples 50 solution trials.

Algorithm | Type | TSP-500 | TSP-1000 | TSP-10000
---|---|---|---|---
Length $\downarrow$ |  Std $\downarrow$ |  Time $\downarrow$ |  Length $\downarrow$ |  Std $\downarrow$ |  Time $\downarrow$ |  Length $\downarrow$ |  Std $\downarrow$ |  Time $\downarrow$
DISCO |  SL+G${\dagger}$+2-opt |  16.862$\pm 0.008$ | $4.81\times 10^{-2}$ |  0.25$\mathrm{m}$ |  23.653$\pm 0.005$ | $2.92\times 10^{-3}$ |  1.12$\mathrm{m}$ |  73.851$\pm 0.035$ | $3.00\times 10^{-2}$ |  25.12$\mathrm{m}$
DISCO | SL+S+2-opt |  16.733$\pm 0.002$ | $1.14\times 10^{-3}$ |  3.88$\mathrm{m}$ |  23.651$\pm 0.007$ | $5.77\times 10^{-3}$ |  9.62$\mathrm{m}$ |  73.811$\pm 0.031$ | $3.51\times 10^{-2}$ |  1.60$\mathrm{h}$
DISCO | SL+MCTS |  16.632$\pm 0.004$ | $2.68\times 10^{-3}$ |  6.99$\mathrm{m}$ |  23.419$\pm 0.004$ | $2.91\times 10^{-3}$ |  15.82$\mathrm{m}$ |  73.562$\pm 0.029$ | $3.27\times 10^{-2}$ |  42.35$\mathrm{m}$
DISCO + MS |  SL+G${\dagger}$+2-opt |  16.789$\pm 0.005$ | $3.49\times 10^{-3}$ |  11.67$\mathrm{m}$ |  23.614$\pm 0.003$ | $2.51\times 10^{-3}$ |  28.83$\mathrm{m}$ |  74.240$\pm 0.034$ | $3.21\times 10^{-2}$ |  1.82$\mathrm{h}$

## NeurIPS Paper Checklist

  1. 1.

Claims

  2. Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

  3. Answer: [Yes]

  4. Justification: The abstract and introduction accurately reflect DISCO’s technical contributions to solving CO problems. It introduces analytical denoising methods to accelerate solution generation, and residue-guided diffusion models to improve solution quality. We also report extensive experimental results of DISCO on various CO problems, demonstrating its superiority in both efficiency and solution quality.

  5. Guidelines:

     * •

The answer NA means that the abstract and introduction do not include the
claims made in the paper.

     * •

The abstract and/or introduction should clearly state the claims made,
including the contributions made in the paper and important assumptions and
limitations. A No or NA answer to this question will not be perceived well by
the reviewers.

     * •

The claims made should match theoretical and experimental results, and reflect
how much the results can be expected to generalize to other settings.

     * •

It is fine to include aspirational goals as motivation as long as it is clear
that these goals are not attained by the paper.

  6. 2.

Limitations

  7. Question: Does the paper discuss the limitations of the work performed by the authors?

  8. Answer: [Yes]

  9. Justification: The paper discusses the limitations of the work in Sec. 6.

  10. Guidelines:

     * •

The answer NA means that the paper has no limitation while the answer No means
that the paper has limitations, but those are not discussed in the paper.

     * •

The authors are encouraged to create a separate "Limitations" section in their
paper.

     * •

The paper should point out any strong assumptions and how robust the results
are to violations of these assumptions (e.g., independence assumptions,
noiseless settings, model well-specification, asymptotic approximations only
holding locally). The authors should reflect on how these assumptions might be
violated in practice and what the implications would be.

     * •

The authors should reflect on the scope of the claims made, e.g., if the
approach was only tested on a few datasets or with a few runs. In general,
empirical results often depend on implicit assumptions, which should be
articulated.

     * •

The authors should reflect on the factors that influence the performance of
the approach. For example, a facial recognition algorithm may perform poorly
when image resolution is low or images are taken in low lighting. Or a speech-
to-text system might not be used reliably to provide closed captions for
online lectures because it fails to handle technical jargon.

     * •

The authors should discuss the computational efficiency of the proposed
algorithms and how they scale with dataset size.

     * •

If applicable, the authors should discuss possible limitations of their
approach to address problems of privacy and fairness.

     * •

While the authors might fear that complete honesty about limitations might be
used by reviewers as grounds for rejection, a worse outcome might be that
reviewers discover limitations that aren’t acknowledged in the paper. The
authors should use their best judgment and recognize that individual actions
in favor of transparency play an important role in developing norms that
preserve the integrity of the community. Reviewers will be specifically
instructed to not penalize honesty concerning limitations.

  11. 3.

Theory Assumptions and Proofs

  12. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

  13. Answer: [Yes]

  14. Justification: We provide theoretical analysis about the equivalence between DISCO and previous diffusion processes in App. A, supporting the effectiveness of our method.

  15. Guidelines:

     * •

The answer NA means that the paper does not include theoretical results.

     * •

All the theorems, formulas, and proofs in the paper should be numbered and
cross-referenced.

     * •

All assumptions should be clearly stated or referenced in the statement of any
theorems.

     * •

The proofs can either appear in the main paper or the supplemental material,
but if they appear in the supplemental material, the authors are encouraged to
provide a short proof sketch to provide intuition.

     * •

Inversely, any informal proof provided in the core of the paper should be
complemented by formal proofs provided in appendix or supplemental material.

     * •

Theorems and Lemmas that the proof relies upon should be properly referenced.

  16. 4.

Experimental Result Reproducibility

  17. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

  18. Answer: [Yes]

  19. Justification: We provide detailed descriptions of the experiment settings in Sec. 5.1, more implementation details can be found in App. B and App. G. We also provide the code, pre-trained models, and documentation in the Supplementary Material.

  20. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

If the paper includes experiments, a No answer to this question will not be
perceived well by the reviewers: Making the paper reproducible is important,
regardless of whether the code and data are provided or not.

     * •

If the contribution is a dataset and/or model, the authors should describe the
steps taken to make their results reproducible or verifiable.

     * •

Depending on the contribution, reproducibility can be accomplished in various
ways. For example, if the contribution is a novel architecture, describing the
architecture fully might suffice, or if the contribution is a specific model
and empirical evaluation, it may be necessary to either make it possible for
others to replicate the model with the same dataset, or provide access to the
model. In general. releasing code and data is often one good way to accomplish
this, but reproducibility can also be provided via detailed instructions for
how to replicate the results, access to a hosted model (e.g., in the case of a
large language model), releasing of a model checkpoint, or other means that
are appropriate to the research performed.

     * •

While NeurIPS does not require releasing code, the conference does require all
submissions to provide some reasonable avenue for reproducibility, which may
depend on the nature of the contribution. For example

       1. (a)

If the contribution is primarily a new algorithm, the paper should make it
clear how to reproduce that algorithm.

       2. (b)

If the contribution is primarily a new model architecture, the paper should
describe the architecture clearly and fully.

       3. (c)

If the contribution is a new model (e.g., a large language model), then there
should either be a way to access this model for reproducing the results or a
way to reproduce the model (e.g., with an open-source dataset or instructions
for how to construct the dataset).

       4. (d)

We recognize that reproducibility may be tricky in some cases, in which case
authors are welcome to describe the particular way they provide for
reproducibility. In the case of closed-source models, it may be that access to
the model is limited in some way (e.g., to registered users), but it should be
possible for other researchers to have some path to reproducing or verifying
the results.

  21. 5.

Open access to data and code

  22. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

  23. Answer: [Yes]

  24. Justification: We provide the code, pre-trained models, as well as specified user documentation in the Supplementary Material.

  25. Guidelines:

     * •

The answer NA means that paper does not include experiments requiring code.

     * •

Please see the NeurIPS code and data submission guidelines
(https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.

     * •

While we encourage the release of code and data, we understand that this might
not be possible, so “No” is an acceptable answer. Papers cannot be rejected
simply for not including code, unless this is central to the contribution
(e.g., for a new open-source benchmark).

     * •

The instructions should contain the exact command and environment needed to
run to reproduce the results. See the NeurIPS code and data submission
guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more
details.

     * •

The authors should provide instructions on data access and preparation,
including how to access the raw data, preprocessed data, intermediate data,
and generated data, etc.

     * •

The authors should provide scripts to reproduce all experimental results for
the new proposed method and baselines. If only a subset of experiments are
reproducible, they should state which ones are omitted from the script and
why.

     * •

At submission time, to preserve anonymity, the authors should release
anonymized versions (if applicable).

     * •

Providing as much information as possible in supplemental material (appended
to the paper) is recommended, but including URLs to data and code is
permitted.

  26. 6.

Experimental Setting/Details

  27. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?

  28. Answer: [Yes]

  29. Justification: We provide detailed descriptions of the experiment settings in Sec. 5.1, more implementation details can be found in App. B and App. G.

  30. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The experimental setting should be presented in the core of the paper to a
level of detail that is necessary to appreciate the results and make sense of
them.

     * •

The full details can be provided either with the code, in appendix, or as
supplemental material.

  31. 7.

Experiment Statistical Significance

  32. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

  33. Answer: [Yes]

  34. Justification: We present a statistical analysis in Appendix G, supporting our findings.

  35. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The authors should answer "Yes" if the results are accompanied by error bars,
confidence intervals, or statistical significance tests, at least for the
experiments that support the main claims of the paper.

     * •

The factors of variability that the error bars are capturing should be clearly
stated (for example, train/test split, initialization, random drawing of some
parameter, or overall run with given experimental conditions).

     * •

The method for calculating the error bars should be explained (closed form
formula, call to a library function, bootstrap, etc.)

     * •

The assumptions made should be given (e.g., Normally distributed errors).

     * •

It should be clear whether the error bar is the standard deviation or the
standard error of the mean.

     * •

It is OK to report 1-sigma error bars, but one should state it. The authors
should preferably report a 2-sigma error bar than state that they have a 96%
CI, if the hypothesis of Normality of errors is not verified.

     * •

For asymmetric distributions, the authors should be careful not to show in
tables or figures symmetric error bars that would yield results that are out
of range (e.g. negative error rates).

     * •

If error bars are reported in tables or plots, The authors should explain in
the text how they were calculated and reference the corresponding figures or
tables in the text.

  36. 8.

Experiments Compute Resources

  37. Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

  38. Answer: [Yes]

  39. Justification: We introduce our computer resources for experimentation in Sec. 5.1.

  40. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The paper should indicate the type of compute workers CPU or GPU, internal
cluster, or cloud provider, including relevant memory and storage.

     * •

The paper should provide the amount of compute required for each of the
individual experimental runs as well as estimate the total compute.

     * •

The paper should disclose whether the full research project required more
compute than the experiments reported in the paper (e.g., preliminary or
failed experiments that didn’t make it into the paper).

  41. 9.

Code Of Ethics

  42. Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

  43. Answer: [Yes]

  44. Justification: We have carefully reviewed the NeurIPS Code of Ethics to ensure compliance.

  45. Guidelines:

     * •

The answer NA means that the authors have not reviewed the NeurIPS Code of
Ethics.

     * •

If the authors answer No, they should explain the special circumstances that
require a deviation from the Code of Ethics.

     * •

The authors should make sure to preserve anonymity (e.g., if there is a
special consideration due to laws or regulations in their jurisdiction).

  46. 10.

Broader Impacts

  47. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

  48. Answer: [Yes]

  49. Justification: We give a discussion about the broader impacts of our work in Sec. 7.

  50. Guidelines:

     * •

The answer NA means that there is no societal impact of the work performed.

     * •

If the authors answer NA or No, they should explain why their work has no
societal impact or why the paper does not address societal impact.

     * •

Examples of negative societal impacts include potential malicious or
unintended uses (e.g., disinformation, generating fake profiles,
surveillance), fairness considerations (e.g., deployment of technologies that
could make decisions that unfairly impact specific groups), privacy
considerations, and security considerations.

     * •

The conference expects that many papers will be foundational research and not
tied to particular applications, let alone deployments. However, if there is a
direct path to any negative applications, the authors should point it out. For
example, it is legitimate to point out that an improvement in the quality of
generative models could be used to generate deepfakes for disinformation. On
the other hand, it is not needed to point out that a generic algorithm for
optimizing neural networks could enable people to train models that generate
Deepfakes faster.

     * •

The authors should consider possible harms that could arise when the
technology is being used as intended and functioning correctly, harms that
could arise when the technology is being used as intended but gives incorrect
results, and harms following from (intentional or unintentional) misuse of the
technology.

     * •

If there are negative societal impacts, the authors could also discuss
possible mitigation strategies (e.g., gated release of models, providing
defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms
to monitor how a system learns from feedback over time, improving the
efficiency and accessibility of ML).

  51. 11.

Safeguards

  52. Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?

  53. Answer: [N/A]

  54. Justification: The article does not involve data or models that have high risks.

  55. Guidelines:

     * •

The answer NA means that the paper poses no such risks.

     * •

Released models that have a high risk for misuse or dual-use should be
released with necessary safeguards to allow for controlled use of the model,
for example by requiring that users adhere to usage guidelines or restrictions
to access the model or implementing safety filters.

     * •

Datasets that have been scraped from the Internet could pose safety risks. The
authors should describe how they avoided releasing unsafe images.

     * •

We recognize that providing effective safeguards is challenging, and many
papers do not require this, but we encourage authors to take this into account
and make a best faith effort.

  56. 12.

Licenses for existing assets

  57. Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

  58. Answer: [Yes]

  59. Justification: All codes, data, and models used in the paper are properly credited.

  60. Guidelines:

     * •

The answer NA means that the paper does not use existing assets.

     * •

The authors should cite the original paper that produced the code package or
dataset.

     * •

The authors should state which version of the asset is used and, if possible,
include a URL.

     * •

The name of the license (e.g., CC-BY 4.0) should be included for each asset.

     * •

For scraped data from a particular source (e.g., website), the copyright and
terms of service of that source should be provided.

     * •

If assets are released, the license, copyright information, and terms of use
in the package should be provided. For popular datasets,
paperswithcode.com/datasets has curated licenses for some datasets. Their
licensing guide can help determine the license of a dataset.

     * •

For existing datasets that are re-packaged, both the original license and the
license of the derived asset (if it has changed) should be provided.

     * •

If this information is not available online, the authors are encouraged to
reach out to the asset’s creators.

  61. 13.

New Assets

  62. Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

  63. Answer: [Yes]

  64. Justification: We provide detailed asset documentation in the Supplementary Material.

  65. Guidelines:

     * •

The answer NA means that the paper does not release new assets.

     * •

Researchers should communicate the details of the dataset/code/model as part
of their submissions via structured templates. This includes details about
training, license, limitations, etc.

     * •

The paper should discuss whether and how consent was obtained from people
whose asset is used.

     * •

At submission time, remember to anonymize your assets (if applicable). You can
either create an anonymized URL or include an anonymized zip file.

  66. 14.

Crowdsourcing and Research with Human Subjects

  67. Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

  68. Answer: [N/A]

  69. Justification: This paper does not involve crowdsourcing or research with human subjects.

  70. Guidelines:

     * •

The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.

     * •

Including this information in the supplemental material is fine, but if the
main contribution of the paper involves human subjects, then as much detail as
possible should be included in the main paper.

     * •

According to the NeurIPS Code of Ethics, workers involved in data collection,
curation, or other labor should be paid at least the minimum wage in the
country of the data collector.

  71. 15.

Institutional Review Board (IRB) Approvals or Equivalent for Research with
Human Subjects

  72. Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

  73. Answer: [N/A]

  74. Justification: This paper does not involve crowdsourcing or research with human subjects.

  75. Guidelines:

     * •

The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.

     * •

Depending on the country in which research is conducted, IRB approval (or
equivalent) may be required for any human subjects research. If you obtained
IRB approval, you should clearly state this in the paper.

     * •

We recognize that the procedures for this may vary significantly between
institutions and locations, and we expect authors to adhere to the NeurIPS
Code of Ethics and the guidelines for their institution.

     * •

For initial submissions, do not include any information that would break
anonymity (if applicable), such as the institution conducting the review.