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

## Abstract

Abstract Combinatorial Optimization (CO) problems are fundamentally important in numerous real-world applications across diverse industries, characterized by entailing enormous solution space and demanding time-sensitive response.
Despite recent advancements in neural solvers, their limited expressiveness struggles to capture the multi-modal nature of CO landscapes.
While some research has shifted towards diffusion models, these models still sample solutions indiscriminately from the entire NP-complete solution space with time-consuming denoising processes, which limit their practicality for large problem scales.
We propose DISCO , an efficient DI ffusion S olver for large-scale C ombinatorial O ptimization problems that excels in both solution quality and inference speed.
DISCO’s efficacy is twofold:
First, it enhances solution quality by constraining the sampling space to a more meaningful domain guided by solution residues, while preserving the multi-modal properties of the output distributions.
Second, it accelerates the denoising process through an analytically solvable approach, enabling solution sampling with minimal reverse-time steps and significantly reducing inference time.
DISCO delivers strong performance on large-scale Traveling Salesman Problems and challenging Maximal Independent Set benchmarks, with inference duration up to 5.28 5.28 5.28 5.28 times faster than existing diffusion solver alternatives.
By incorporating a divide-and-conquer strategy, DISCO can well generalize to solve unseen-scale problem instances off the shelf, even surpassing models specifically trained for those 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 (Ma et al., ; Li et al., ),
production scheduling (Ye et al., ; Zhang et al., ),
and resource allocation (Zhao et al., ; ).
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 (Garey & Johnson, ), 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 CO problem solving (Choo et al., ; Kim et al., ).
However, these learning-based solvers are susceptible to being misled by the multi-modal landscapes in CO problems (Khalil et al., ), wherein the learning agent is required to identify a set of optimal solutions. This multi-modal property complicates the learning, hindering efficient convergence to desired solutions, particularly when confronted with large problem scale (Chen & Tian, ; Wu et al., ).
Diffusion probabilistic models (Ho et al., ; Song et al., ) have demonstrated robust capabilities in generation tasks.
Of particular interest,
Chi et al. () and Huang et al. () 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 methods to CO.

We are not the first to apply diffusion models to CO problems.
Graikos et al. () tackle Euclidean Traveling Salesman problems (TSP) by converting each instance into a low-resolution greyscale image and then utilizing a Convolutional Neural Network (CNN) (LeCun et al., ) for denoising the solution.
Sun & Yang () propose DIFUSCO to explicitly model problem structures with Graph Neural Networks (GNNs) (Gori et al., ). Li et al. () further develop DIFUSCO with an objective-guided, gradient-based search during deployment.
Although these approaches show improved performance, they still indiscriminately sample solutions from the entire NPC solution space, simulating a Markov chain for generation with many steps.
The incurred time overhead for unproductive solution sampling is a critical bottleneck in applying diffusion solvers to real-world instances,
especially when dealing with large problem scales (Xu et al., ).

We contend that the potential of diffusion models in addressing large-scale CO problems has yet to be fully discovered.
We propose DISCO, an efficient DIffusion Solver for large-scale Combinatorial Optimization problems.
DISCO improves solution quality by restricting the sampling space to a more meaningful domain, guided by solution residues, and enables rapid solution generation with minimal denoising steps.
DISCO delivers strong performance on large-scale TSP instances and challenging Maximal Independent Set (MIS) benchmarks, with inference duration up to $5.28$ times faster than other diffusion solver alternatives.
Through further leveraging the multi-modal property and efficiency of DISCO, we can well generalize it to solve unseen-scale instances with a traditional divide-and-conquer strategy (Fu et al., ; Ye et al., ) off the shelf, even outperforming models specifically trained for 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 (Bello et al., ; Kool et al., ),
production scheduling (Ye et al., ; Zhang et al., ), and resource allocation (Zhao et al., ; ).
However, the exponential growth of the solution space, as the problem scale escalates for these NPC problems (Garey & Johnson, ), 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 (Lawler & Wood, ; Schrijver et al., ), such as dynamic programming (Cormen et al., ) and cutting-plane methods (Wolsey & Nemhauser, ), 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 (Hochba, ; Vazirani, ) and heuristic (Glover & Kochenberger, ; Michalewicz & Fogel, ) 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 (Helsgaun, ; Taillard & Helsgaun, ) 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 search processes,
researchers have widely explored neural solvers for CO problems.
These approaches encompass both supervised learning (SL) (Vinyals et al., ) and reinforcement learning (RL) (Mnih et al., ).
From a practical perspective, the choice between SL and
RL depends on the availability of problem data.
For online operation problems (Seiden, ; Borodin & El-Yaniv, ), 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 (Zhao et al., ; ).
Conversely, for offline problems (Papadimitriou & Steiglitz, ),
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 (Croes, ; Kool et al., ; Graikos et al., )
has become a common practice (Deudon et al., ).
Most CO problems can be modeled as decision problems on graphs (Yolcu & Póczos, ; Li & Si, ; Zhang et al., ).
Notably, TSP (Bi et al., ) and MIS (Darvariu et al., ) stand out as two foundations regarding edge and node decision problems.
DISCO leverages anisotropic GNNs (Bresson & Laurent, ; Joshi et al., ) as the backbone to produce embeddings for both graph edges and nodes, adequately demonstrating its superiority on both large-scale TSP and MIS instances through extensive evaluations.

#### Diffusion Probabilistic Model

Diffusion probabilistic models (DPMs) (Ho et al., ; Song et al., ) are primarily utilized for high-quality generation and have exhibited robust capabilities in generating images (Huang et al., ), audios (Luo et al., ), and videos (Ho et al., ).
This impressive method was initially formulated by Sohl-Dickstein et al. () and further extended by Ho et al. () 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 (Dhariwal & Nichol, ) 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 (Goodfellow et al., ; Radford et al., ), 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 (Huang et al., ). This multi-modal property particularly benefits CO problem solving, where multiple optimal solutions may exist and confront the limited expressiveness of previous neural solvers (Gu et al., ; Li et al., ).
Some attempts have been made.
Graikos et al. () convert TSP instances into low-resolution greyscale images encoded by CNN.
Sun & Yang () propose DIFUSCO to incorporate GNN for problem representation while Li et al. () further develop DIFUSCO with an objective-guided, gradient-based search during deployment.
These efforts overlook the inefficient solution sampling from enormous NPC solution space and the slow reverse process of diffusion models, which significantly hampers their practicality for large-scale real-world applications (Xu et al., ).
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 (Huang et al., ) to quickly produce high-quality solutions with very few denoising steps, while reducing solution space associated with NPC problems by introducing solution residues (Liu et al., ). This enhanced efficiency on both solution quality and inference speed further amplifies DISCO’s advantages in generalizing to the CO challenge of unseen 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})$ (Papadimitriou & Steiglitz, ).
The optimal solution $\mathbf{X}^{*}_{s}$ is defined as:

$$ $\operatorname*{arg\,min}_{\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 (Vinyals et al., ; Sun & Yang, ) or reinforcement learning (Bello et al., ; Kool et al., ) 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 (Khalil et al., ; Gu et al., ). Thanks to recent advances in generative models, DPMs have exhibited promising prospects for generating a wide variety of distributions (Ho et al., ; Huang et al., ) 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. () with the 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. Song et al. () 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 (Einstein, ).

## 4 Method

At the outset, we introduce solution residues in Sec. 4.1, which restricts the sampling space for large-scale CO problems to a more meaningful domain, ensuring solution effectiveness while preserving diversity.
In Sec. 4.2, we present our analytical denoising process to generate high-quality solutions with minimal reverse-time steps.
In Sec. 4.3, we further leverage the multi-modal property and efficiency of DISCO to generalize it to unseen scales with a traditional divide-and-conquer strategy.

### 4.1 Residue-Constrained Solution Generation

Figure: Figure 1: In comparing DISCO’s solution sampling with traditional diffusion methods. We define darker colors to represent higher solution quality. (a) Traditional diffusion generation indiscriminately spans the entire mixed-quality solution space, i.e., a significant proportion of the samples do not satisfy problem constraints. (b) DISCO constrains the generations close to the high-quality label $\mathbf{X}_{s}$ by introducing residues, resulting in a more meaningful, yet smaller, solution space, while preserving the multi-modal properties of the output distributions.
Refer to caption: x1.png

The NPC solution space of CO problems grows exponentially with problem scales.
The reverse generation covering such an enormous space is inefficient since many samples do not even adhere to problem constraints, as depicted in Fig. 1 (a).
We propose our DISCO method to restrict the sampling from the entire NPC space to a more meaningful domain while still preserving the multi-modal property of output distributions.
We achieve this by introducing solution residues (Liu et al., ) 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 (Zhao et al., ; Zhang et al., ).

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 (Fu et al., ; Sun & Yang, ). Subsequently,
task-specific decoding processes (Croes, ; Kool et al., ) are employed to transform predicted $\mathbf{x}_{0}$ into discrete solution $\mathbf{X}_{s}$.
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.
By introducing the residue $x_{res}$, the forward diffusion process is the mapping from the high-quality solution to the mixture of noise and degraded solution:

$$ $\mathbf{x}_{t}=\mathbf{x}_{0}+(1-\alpha_{t})\mathbf{x}_{res}+\beta_{t}\bm{ \epsilon},\quad\bm{\epsilon}\sim\mathcal{N}(\bm{\epsilon};\mathbf{0},\mathbf{I }),$ (4) $$

where $\mathbf{x}_{0}=\mathbf{X}_{s}$ denotes the high-quality solution label and $\mathbf{x}_{t}$ is the noisy solution.
According to the reversed process of DDPM (Ho et al., ), we can derive the transition probability of the reversed process that is defined as:

$$ $\begin{split}&q(\mathbf{x}_{t-1}|\mathbf{x}_{t},\mathbf{x}_{0})\propto\exp \left\{-\frac{(\mathbf{x}_{t-1}-\mathbf{u})^{2}}{2\sigma^{2}\mathbf{I}}\right \},\\ &\mathbf{u}=\frac{\alpha_{t-1}\alpha_{t}\beta_{t-1}^{2}+\alpha_{t-1}^{2}- \alpha_{t}^{2}}{\alpha_{t-1}\beta_{t}^{2}}\mathbf{x}_{t}+\frac{(\alpha_{t}^{2} -\alpha_{t-1}^{2})(1-\alpha_{t})}{\alpha_{t-1}\beta_{t}^{2}}\mathbf{x}_{res}+ \frac{\alpha_{t}^{2}-\alpha_{t-1}^{2}}{\alpha_{t-1}\beta_{t}}\bm{\epsilon},\\ &\sigma^{2}=\frac{(\alpha_{t-1}^{2}-\alpha_{t}^{2})\beta_{t-1}^{2}}{\alpha_{t- 1}^{2}\beta_{t}^{2}}.\end{split}$ (5) $$

The residue prioritizes certainty while the noise emphasizes diversity, so that the solution space for sampling is effectively constrained. For the learning process,
the diffusion model only needs to learn the residue between the high-quality label $\mathbf{X}_{s}$ and the proposed degraded solutions $\mathbf{X}_{d}$ rather than the original $\mathbf{X}_{s}$, which simplifies the learning.
For the inference process, the generations are confined close to the high-quality label $\mathbf{X}_{s}$ by introducing residues, allowing the model to efficiently find high-quality solutions while leveraging this meaningful diversity to further improvement.

### 4.2 Analytically Solvable Denoising Process

The residue-constrained denoising process allows for the efficient generation of high-quality solutions; however, typical DDPM usually takes 900$\sim$1000 sampling steps for the inference.
The slow solving speed significantly limits the practical application of diffusion solvers in real-world CO problems, particularly considering many time-sensitive demands, such as on-call routing (Ghiani et al., ) and on-demand hailing service (Xu et al., ), 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) (Huang et al., ),
the original mapping in Eq. 4 can be decoupled into an analytical high-quality solution to degraded solution and a zero-to-noise mapping:

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

where $\mathbf{x}_{0}+\int_{0}^{t}\mathbf{x}_{res}dt$ represents the solution to degradation, and $\sqrt{t}\bm{\epsilon}$ denotes the zero-to-noise process.
More importantly, since there is an analytical solution-to-degradation in the forward process, we can derive the corresponding reversed process with a similar analytical form. In this way, the efficiency of the reversed process can be improved by much fewer evaluation steps, e.g., inference with 1 or 2 steps. More specifically, 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\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\bm {\epsilon}/\sqrt{t},\quad\sigma^{2}=\Delta t(t-\Delta t)/t,\end{split}$ (7) $$

where $\bm{\epsilon}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$.
Benefiting from the analytical solution to degradation, we 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.

We provide a theoretical analysis of the equivalence between DISCO and DDM in App. A, supporting the effectiveness of our method.
It is important to note that DDMs are not directly adopted by DISCO. We integrate our residue-constrained design with DDMs, leading to refined diffusion processes and training objectives.
DISCO can efficiently achieve high-quality solutions by sampling from the constrained solution space with fewer denoising steps, meeting the requirements of large-scale CO.

#### Training

We adopt anisotropic GNNs (Bresson & Laurent, ; Joshi et al., ) as the network architecture of DISCO.
Unlike typical GNNs such as GCN (Kipf & Welling, ) or GAT (Velickovic et al., ) 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 $\bm{\theta}$, predicting the parameterized residue $\mathbf{x}_{res}^{\bm{\theta}}$ and noise $\bm{\epsilon}^{\bm{\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 (Ma et al., ; Wu et al., ), especially at large scales. The training objective is defined as:

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

Once trained, the model 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 (Graikos et al., ), Sample (Kool et al., ), 2-opt (Croes, ),
to achieve the final solution.

#### Sampling

Eq. 6 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 $\bm{\epsilon}$ sampled from the normal distribution, we set $\mathbf{x}_{1}=\mathbf{X}_{d}+\bm{\epsilon}$ ($t=1$). Sampling from $\mathbf{x}_{1}$ instead of $\bm{\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}^{\bm{\theta}}$ and noise $\bm{\epsilon}^{\bm{\theta}}$. In this way, we can solve the reversed process via Eq. 7 iteratively, obtaining the high-quality solution $\mathbf{x}_{0}$ until $t=0$.
After we sample a probability distribution $\mathbf{x}_{0}$ from $p_{\bm{\theta}}(s)$ for instance $s$, we adopt the same operation as Sun & Yang () to obtain the normalized heatmap score $\mathbf{h}=0.5(\mathbf{x}_{0}+1)$.

### 4.3 Multi-Modal Graph Search

Parameterized solvers trained on specific scales often struggle to generalize well to test instances of different scales (Fu et al., ).
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.
Leveraging the efficiency advantage of DISCO in both
solution quality and inference speed,
combined with the assistance of the SL approach in discovering common solution patterns,
we can utilize its multi-modal output to further enhance solution diversity through a traditional divide-and-conquer strategy (Fu et al., ; Ye et al., ).
Increasing the solution diversity broadens the exploration of the solution space, decreasing the likelihood of getting stuck in sub-optimal solutions (Zhang et al., ) and improving generalization performance.

Figure: Figure 2: Our multi-modal 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}$.
Refer to caption: x2.png

Figure: Algorithm 1 Multi-Modal Graph Search

Specifically, we leverage a model $p_{\bm{\theta}}$ trained on a smaller scale as a base to construct heatmaps for sub-problems $\mathbf{g}$, which are decomposed from the original graph $G$.
The scale of sub-problem $g\in\mathbf{g}$ is fixed and close to the training scale of $p_{\bm{\theta}}$, thereby we can better solve $g$ and smoothly generalize $p_{\bm{\theta}}$ to the original scale.
A detailed pipeline is provided in Fig. 2.
For sub-problem 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*{arg\,min}(\mathbf{o}_{v})$ as the cluster center
and select the remaining nodes with the k-nearest neighbor rule (Cover & Hart, ), 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 trained DISCO model $p_{\bm{\theta}}$,
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:

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

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.
The scalar $o_{ij}$ records the occurrence count of edge $ij$ across all subgraphs.
Subsequently, we decode the merged heatmap $\mathbf{H}$ into the final solution $\mathbf{X}$.

We leverage the multi-modal output of DISCO to enhance the solution diversity and avoid the final solution from getting stuck in the sub-optimum.
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 can be $\exp_{q}(|\mathbf{g}|)$ possible trial combination, we observe that performance asymptotically converges,
so we limit the sampling to finite $n$ trials.
A detailed description of our algorithm is provided 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.
Subsequently, we conduct ablations on DISCO components in Sec. 5.3, verify its generalization ability to unseen problem scales in Sec. 5.4, and 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, our evaluations primarily focus on the most representative TSP problem, as it is a common challenge in the machine learning community with established competitors, providing a solid benchmark to demonstrate our method’s superiority.
Our evaluation metrics include the average length (Length) of tours and the clock time (Time) required for solving 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 conduct an extensive comparison of DISCO with a diverse set of baselines,
including exact solvers, heuristic solvers, and state-of-the-art learning methods. For exact solvers, our comparisons include Concorde (Applegate et al., ) and Gurobi (LLC Gurobi Optimization, ). Regarding heuristic solvers, we evaluate against LKH-3 (Helsgaun, ), 2-opt (Croes, ) and a simple Farthest Insertion principle (Cook et al., ).
In terms of learning-based methods, we compare with recent advances including AM (Kool et al., ), ELG-POMO (Gao et al., ), BQ-NCO (Drakulic et al., ), and GLOP (Ye et al., ), and diffusion-based solvers DIFUSCO (Sun & Yang, ) and T2T (Li et al., ).
Note that, T2T is currently the most powerful neural solver for TSP problems.

We label the large-scale training instances using the LKH-3 heuristic solver (Helsgaun, ) and generate the test instances following the same principle as Fu et al. () and Sun & Yang ().
All experiments are conducted on a single NVIDIA A100 GPU, paired by AMD EPYC 7662 CPUs @ 2.00GHz.
Some learning-based solvers struggle with large problem scales; for instance, Image Diffusion (Graikos et al., ) 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 GCN (Joshi et al., ), Transformer (Bresson & Laurent, ), POMO (Kwon et al., ), Sym-NCO (Kim et al., ), DPDP (Ma et al., ), and MDAM (Xin et al., ).
Our codes, the mentioned baselines, pre-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. G, S, and BS denotes Greedy decoding, Sampling decoding, and Beam Search (Sutskever et al., ), respectively. The symbol * indicates the baseline for computing the performance gap. The symbol ${\dagger}$ denotes that the diffusion model samples once. N/A indicates that results could not be produced within 24 hours (Qiu et al., ), and OOM signifies running out of memory on a machine with 80GB of GPU memory.**
| Algorithm | Type | TSP-5000 | TSP-8000 | TSP-10000 |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Length $\downarrow$ | Gap $\downarrow$ | Time $\downarrow$ | Length $\downarrow$ | Gap $\downarrow$ | Time $\downarrow$ | Length $\downarrow$ | Gap $\downarrow$ | Time $\downarrow$ |  |  |
| Concorde | Exact | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A |
| Gurobi | Exact | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A |
| LKH-3 (default) | Heuristics | 51.94^∗ | — | 6.57$\mathrm{m}$ | 65.21^∗ | — | 16.23$\mathrm{m}$ | 71.77^∗ | — | 8.8$\mathrm{h}$ |
| LKH-3 (less trials) | Heuristics | 52.22 | 0.54% | 5.17$\mathrm{m}$ | 66.11 | 1.38% | 13.83$\mathrm{m}$ | 71.79 | 0.03% | 51.27$\mathrm{m}$ |
| raw 2-OPT | Heuristics | 58.99 | 13.57% | 6.16$\mathrm{m}$ | 79.29 | 21.59% | 14.15$\mathrm{m}$ | 91.16 | 27.02% | 28.49$\mathrm{m}$ |
| Farthest Insertion | Heuristics | 57.20 | 10.13% | 0.97$\mathrm{m}$ | 72.28 | 10.84% | 5.78$\mathrm{m}$ | 80.59 | 12.29% | 13.25$\mathrm{m}$ |
| BQ-NCO | RL+G | 175.34 | 237.58% | 75.72$\mathrm{m}$ | 725.67 | 1012.82% | 4.98$\mathrm{h}$ |  | OOM |  |
| AM | RL+G | 89.35 | 72.03% | 1.68$\mathrm{m}$ | 122.42 | 87.73% | 3.95$\mathrm{m}$ | 141.51 | 97.17% | 7.68$\mathrm{m}$ |
| ELG-POMO | RL+G | 59.96 | 15.44% | 51.18$\mathrm{m}$ | 76.71 | 17.64% | 2.02$\mathrm{h}$ |  | OOM |  |
| GLOP | RL+G | 53.39 | 2.79% | 0.51$\mathrm{m}$ | 67.51 | 3.53% | 0.53$\mathrm{m}$ | 75.29 | 4.90% | 1.90$\mathrm{m}$ |
| DIFUSCO | SL+G${\dagger}$ | 53.31 | 2.64% | 8.65$\mathrm{m}$ | 67.51 | 3.53% | 19.38$\mathrm{m}$ | 73.99 | 3.10% | 35.38$\mathrm{m}$ |
| T2T | SL+G${\dagger}$ | 53.17 | 2.37% | 25.88$\mathrm{m}$ | 67.43 | 3.40% | 1.11$\mathrm{h}$ | 73.87 | 2.92% | 1.52$\mathrm{h}$ |
| DISCO (Ours) | SL+G${\dagger}$ | 52.48 | 1.04% | 5.72$\mathrm{m}$ | 66.11 | 1.38% | 14.32$\mathrm{m}$ | 73.85 | 2.90% | 25.12$\mathrm{m}$ |
| AM | RL+BS | 83.93 | 61.59% | 19.07$\mathrm{m}$ | 114.82 | 76.08% | 1.13$\mathrm{h}$ | 129.40 | 80.28% | 1.81$\mathrm{h}$ |
| GLOP | RL+S | 53.28 | 2.58% | 0.54$\mathrm{m}$ | 67.41 | 3.37% | 0.59$\mathrm{m}$ | 75.27 | 4.88% | 5.96$\mathrm{m}$ |
| DIFUSCO | SL+S | 53.15 | 2.33% | 21.07$\mathrm{m}$ | 67.41 | 3.37% | 50.18$\mathrm{m}$ | 73.90 | 2.97% | 1.83$\mathrm{h}$ |
| T2T | SL+S | 53.10 | 2.23% | 47.85$\mathrm{m}$ | 67.40 | 3.36% | 1.86$\mathrm{h}$ | 73.81 | 2.84% | 2.47$\mathrm{h}$ |
| DISCO (Ours) | SL+S | 52.44 | 0.96% | 9.06$\mathrm{m}$ | 66.06 | 1.30% | 22.82$\mathrm{m}$ | 73.81 | 2.84% | 48.77$\mathrm{m}$ |

We compare DISCO to alternative NPC solvers across various large-scale problem instances, including TSP-5000, TSP-8000, and TSP-10000.
Given that generating heatmaps with parameterized solvers and transforming them into solutions through decoding strategies has become standard practice (Deudon et al., ), we report parameterized solvers’ performance decoding with different strategies. Xia et al. () highlight that the MCTS strategy (Fu et al., ) heavily relies on TSP-specific heuristics, and is less suited to other problem types.
Therefore, we focus on general decoding strategies,
including Greedy (Graikos et al., ), Sampling (Kool et al., ), and 2-opt (Croes, ), which represents local search, to evaluate each method’s general CO-solving capability.
These strategies are introduced in App. F.
We align DISCO’s decoding settings with DIFUSCO and T2T to demonstrate its superiority as a diffusion solver.
To ensure fairness, we apply 2-opt to all learning-based methods, as some solvers like DIFUSCO and T2T use it while others do not.
Follow Graikos et al. (), we use the Greedy+2-opt strategy by default, and Sampling is conducted 4 times across all problem scales.
Unless otherwise noted, DISCO’s denoising steps are set to 1 to highlight its efficiency, while DIFUSCO uses 50 steps and T2T uses 20 steps in inference and 3 iterations $\times$ 10 steps in gradient search. Additional details are provided in App. G.

The comprehensive results are summarized in Tab. 1.
We observe that DISCO outperforms all the previous methods on all problem scales, including T2T which is the current state-of-the-art solver for TSP problems.
Diffusion-based methods generally outperform other learning-based approaches, highlighting the significance of diffusion as a choice. Its inherent multi-modal expressiveness makes it particularly well-suited for optimization problems.
Notably, beyond its performance advantage, DISCO also demonstrates a significant advantage in inference speed compared to the other two diffusion alternatives, DIFUSCO and T2T, with its inference duration achieving up to $5.28$ times speedup, better satisfying many real-world applications that require time-sensitive responses.
Since T2T requires gradient-based search during deployment, its computational resource demands
are obviously higher than DISCO and DIFUSCO. A detailed comparison is provided in App. H.
We also evaluate DISCO on real-world TSP scenarios from TSPLIB (Reinelt, ) 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 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 performance advantage.
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.
We further test the generalization ability of DISCO as a probabilistic solver to unseen problem distributions in App. H.

### 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 these two modules,
which can also be regarded as
an equal implementation of DIFUSCO, 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 with just 1 step, 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.

Figure: (a) W/o residue.
Refer to caption: x3.png

### 5.4 Multi-Modal Graph Search for Generalization

Benefiting from DISCO’s verified advantage in both solution quality and inference speed, we can
generalize a pre-trained DISCO model $p_{\bm{\theta}}$ to solve the unseen-scale problem instances off the shelf by a traditional divide-and-conquer strategy. We train the base model $p_{\bm{\theta}}$ on TSP-100 instances and transfer it to TSP-5000/8000/10000 instances.
The decomposed sub-problems $\mathbf{g}$ should jointly cover the global graph problem $G$ at least $\omega=1$ time.
For each sub-problem $g\in\mathbf{g}$, we generate a set of heatmaps $\mathcal{H}$ with $q=2$ different noises.
The results are summarized in Tab. 3.
We organize the experiments in the following logic: First, we test diffusion models trained on different problem scales to verify the existence of performance degradation. In addition, we validate that the multi-modal graph search method allows trained models to transfer to unseen problem scales off the shelf. Finally, we propose potential methods to further enhance the performance of our graph search approach.

**Table 3: Results on multi-modal graph search. GS means graph search. T indicates training on the corresponding problem scale. ‘Best Inter.’ refers to selecting the best intermediate $\mathbf{h}$ with the greedily decoded solution from heatmap set $\mathcal{H}$ for each subgraph $g$, rather than random selection to maintain trial diversity.**
| Algorithm | Type | Trial | TSP-5000 | TSP-8000 | TSP-10000 |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Length $\downarrow$ | Gap $\downarrow$ | Time $\downarrow$ | Length $\downarrow$ | Gap $\downarrow$ | Time $\downarrow$ | Length $\downarrow$ | Gap $\downarrow$ | Time $\downarrow$ |  |  |  |
| LKH-3 (default) | Heuristics | 10000 | 51.94^∗ | — | 6.57$\mathrm{m}$ | 65.21^∗ | — | 16.23$\mathrm{m}$ | 71.77^∗ | — | 8.8$\mathrm{h}$ |
| Att-GCN | SL+MCTS | 1 | 77.20 | 48.64% | 13.30$\mathrm{m}$ | 105.41 | 61.64% | 25.95$\mathrm{m}$ | 74.93 | 4.39% | 21.49$\mathrm{m}$ |
| GLOP | RL | 1 | 53.39 | 2.79% | 0.51$\mathrm{m}$ | 67.51 | 3.53% | 0.53$\mathrm{m}$ | 75.29 | 4.90% | 1.90$\mathrm{m}$ |
| DISCO (TSP-5000, T) | SL+G${\dagger}$ | 1 | 52.48 | 1.04% | 5.72$\mathrm{m}$ | 67.42 | 3.39% | 17.52$\mathrm{m}$ | 74.98 | 4.47% | 25.37$\mathrm{m}$ |
| DISCO (TSP-8000, T) | SL+G${\dagger}$ | 1 | 52.97 | 1.98% | 5.10$\mathrm{m}$ | 66.11 | 1.38% | 17.32$\mathrm{m}$ | 74.60 | 3.94% | 25.70$\mathrm{m}$ |
| DISCO (TSP-10000, T) | SL+G${\dagger}$ | 1 | 53.21 | 2.44% | 5.82$\mathrm{m}$ | 67.27 | 3.16% | 17.46$\mathrm{m}$ | 73.85 | 2.90% | 25.12$\mathrm{m}$ |
| DIFUSCO (Best Inter.) | SL+GS+G${\dagger}$ | 1 | 52.78 | 1.62% | 1.31$\mathrm{h}$ | 66.86 | 2.53% | 2.16$\mathrm{h}$ | 74.33 | 3.57% | 4.91$\mathrm{h}$ |
| DIFUSCO | SL+GS+G${\dagger}$ | 50 | 52.67 | 1.41% | 2.11$\mathrm{h}$ | 66.61 | 2.15% | 4.81$\mathrm{h}$ | 74.35 | 3.60% | 5.93$\mathrm{h}$ |
| DISCO (Best Inter.) | SL+GS+G${\dagger}$ | 1 | 52.77 | 1.60% | 8.12$\mathrm{m}$ | 66.56 | 2.07% | 19.82$\mathrm{m}$ | 74.45 | 3.73% | 36.43$\mathrm{m}$ |
| DISCO | SL+GS+G${\dagger}$ | 50 | 52.65 | 1.37% | 32.40$\mathrm{m}$ | 66.52 | 2.01% | 1.34$\mathrm{h}$ | 74.24 | 3.44% | 1.82$\mathrm{h}$ |
| DISCO | SL+GS+G${\dagger}$ | 100 | 52.62 | 1.31% | 57.53$\mathrm{m}$ | 66.52 | 2.01% | 2.31$\mathrm{h}$ | 74.22 | 3.41% | 3.76$\mathrm{h}$ |
| DISCO ($\omega=4$) | SL+GS+G${\dagger}$ | 50 | 52.60 | 1.27% | 35.45$\mathrm{m}$ | 66.48 | 1.95% | 1.40$\mathrm{h}$ | 74.23 | 3.43% | 2.18$\mathrm{h}$ |
| DISCO | SL+GS+MCTS | 50 | 52.32 | 0.73% | 41.98$\mathrm{m}$ | 66.12 | 1.40% | 1.59$\mathrm{h}$ | 73.69 | 2.68% | 2.10$\mathrm{h}$ |

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_{\bm{\theta}}$ trained only on TSP-100, exhibits better performance than direct generalization.
Att-GCN (Fu et al., ) and GLOP (Ye et al., ) also adopt the divide-and-conquer mechanism for generalization.
However, their parameterized solver lacks the ability to generate
diverse trials, which causes the final solution may get stuck in the sub-optimum.
Our DISCO method increases the diversity of solution samples and broadens exploration in the solution space, enhancing the likelihood of finding higher-quality solutions and being more effective than Att-GCN and GLOP.
Although DIFUSCO
also possesses the multi-modal property, its inference speed is prohibitively slow.
DISCO achieves at least 3.26 times faster inference speed than DIFUSCO for graph search, while also delivering superior results.

While our graph search approach offers $\exp_{q}(|\mathbf{g}|)$ possibilities for enriching solution diversity, its performance asymptotically converges to the number of sampled trials, as confirmed by the generalization results on TSP-1000 in Fig. 4.
The required trial 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 diverse trials—specifically, selecting the best intermediate $\mathbf{h}$ with the greedily decoded solution from heatmap set $\mathcal{H}$ for each subgraph $g$—and find that this version generally performs worse.
This amplifies the importance of solution diversity for solving 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 enhancements can even lead to better performance than models trained on the corresponding scale.
These conclusions are corroborated in Table 3.

Figure: Figure 4: Asymptotic performance of multi-modal graph search with trial number.
Refer to caption: x5.png

### 5.5 Evaluations on Maximal Independent Set

Besides TSP, we 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 (Hoos & Stützle, ) and Erdős-Rényi (ER) (Erdős & Rényi, ) graph sets, which exhibit challenge for recent learning-based solvers (Li et al., ; Ahn et al., ; Böther et al., ; Qiu et al., ; Zhang et al., ).
Training instances are labeled using the KaMIS heuristic solver (Lamm et al., ), with test instances aligned with Qiu et al. ().
We adopt the same 50 denoising steps and 4 sample times as DIFUSCO
to distinguish model capabilities.
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 a clear performance advantage over most competitors.

## 6 Conclusion

We propose DISCO, an efficient diffusion solver for large-scale CO problems. DISCO obtains
improved solution quality by restricting the sampling space to a more meaningful domain guided by solution residues, and enables rapid solution generation with minimal denoising steps.
DISCO delivers strong performance on large-scale TSP instances and challenging MIS benchmarks SATLIB and Erdős-Rényi, with inference duration up to $5.28$ times faster than existing diffusion solver alternatives.
Through further combining a traditional divide-and-conquer strategy, DISCO can be generalized to solve unseen-scale problem instances off the shelf, even outperforming models trained specifically on those scales.

This work has two limitations. First, DISCO relies on supervised learning and decoding strategies to transform output heatmaps, limiting it to offline operations where iterative optimization is feasible.
For online operations, DISCO must generate immediate high-quality solutions across the NPC problem space.
Future work should explore integrating trial-and-error methods for online applications.
Second, DISCO’s multi-modal graph search can lead to exponential growth in trial variance.
While this variance aids in exploring the solution space and finding optimal solutions, it also increases computational costs.
Developing a lightweight policy for smarter trail sampling is promising.

## 7 Code Of Ethics

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 (Ghiani et al., ; Xu et al., ).

## 8 Reproducibility

We provide detailed descriptions of the experiment settings in Sec. 5.1, more implementation details can be found in App. B and App. G.
The code for DISCO, the mentioned baselines, pre-trained models, and detailed accompanying documentation are also included in the Supplementary Material to ensure reproducibility.

## 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 (Khalil et al., ; Gu et al., ; Li et al., ). In contrast, diffusion probabilistic models (DPMs) (Ho et al., ) have shown promising prospects for generating a wide variety of distributions suitable for CO solving. An obvious 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) (Huang et al., ),
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}),$ (10) $$

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}),$ (11) $$

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}\bm{\epsilon}$ with $\bm{\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\},$ (12) $$

where $\bm{\epsilon}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$, $\widetilde{\mathbf{u}}=\mathbf{x}_{t}+\mathbf{F}_{t-\Delta t}-\mathbf{F}_{t}+
\bm{\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 more meaningful one by introducing residues (Liu et al., ) to DDM, which is our DISCO method, i.e., an efficient DIffusion Solver for large-scale CO problems.
The reversed process starts from both noise and an exceedingly cost-effective degraded solution, confining the generation process in a more meaningful and smaller 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-modal property of output distributions.

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 (Huang et al., ), 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}\bm{ \epsilon}.$ (13) $$

Compared with the original forward formulation of DDM (Eq. 10), 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}^{\bm{\theta}}$ and $\bm{\epsilon}^{\bm{\theta}}$, which estimate the residue $\mathbf{x}_{res}$ and the noise $\bm{\epsilon}$, respectively. From Eq. 6, we have:

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

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}).$ (15) $$

Applying Bayes’ theorem (Jaynes, ), 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})}$ (16) $\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. 16 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)},$ (17) $$

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 (Hoos & Stützle, ) and Erdős-Rényi (ER) (Erdős & Rényi, ) graph sets, which exhibit challenge for recent learning-based solvers (Li et al., ; Ahn et al., ; Böther et al., ; Qiu et al., ; Zhang et al., ).
The training instances are labeled by the KaMIS heuristic solver (Lamm et al., ). The split of test instances on SAT datasets and the random-generated ER test graphs are taken from (Qiu et al., ).

#### 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 (Sun & Yang, ) 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 randomly sample a set of nodes from the original graph with a probability of 50% to obtain the degraded solution.

#### Baselines

We compare DISCO with 9 other MIS solvers on the same test sets, including two traditional OR methods and seven learning-based approaches.
For the traditional methods, we use Gurobi and KaMIS (Lamm et al., ) as baselines.
For the learning-based methods, we compare with LwD (Ahn et al., ), Intel (Li et al., ), DGL (Böther et al., ), DIMES (Qiu et al., ), GFlowNet (Zhang et al., ), DIFUSCO (Sun & Yang, ), and T2T (Li et al., ).

## Appendix C Comparisons on Small-Scale TSP Instances

Some learning-based solvers struggle with large problem scales, we compare them on small-scale instances for fairness.
Specifically, we compare with learning-based methods
Image Diffusion (Graikos et al., ), GCN (Joshi et al., ), Transformer (Bresson & Laurent, ), POMO (Kwon et al., ), Sym-NCO (Kim et al., ), DPDP (Ma et al., ), and MDAM (Xin et al., ).
Along with the learning-based methods works on large scales including AM (Kool et al., ), DIFUSCO (Sun & Yang, ), and T2T (Li et al., ). We compare with traditional operation methods including Concorde (Applegate et al., ) and Gurobi (LLC Gurobi Optimization, ), LKH-3 (Helsgaun, ), 2-OPT (Croes, ), and Farthest Insertion (Cook et al., ).
We label the training instances using the Concorde solver for TSP-50/100 and we take the same test instances as (Kool et al., ; Joshi et al., ). The comprehensive results are summarized in Tab. 5, with DISCO consistently maintaining its performance advantage.
We visualize the corresponding denoising processes in Fig. 5.

**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 |
| T2T | Greedy${\dagger}$ | 5.69 | 0.04 | 7.77 | 0.18 |
| 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 |
| T2T | $16\times$Sampling | 5.69 | -0.01 | 7.76 | -0.01 |
| DISCO (Ours) | $16\times$Sampling | 5.69 | -0.01 | 7.76 | 0.03 |

Figure: Figure 5: 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.
Refer to caption: x6.png

## 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 6, 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.

Figure: Figure 6: 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.
Refer to caption: x24.png

### 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. 7, 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.

Figure: Figure 7: 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.
Refer to caption: x42.png

## Appendix E Generalization to Real-World Instances

We evaluate DISCO on TSPLIB (Reinelt, ), 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. 8.

**Table 6: TSPLIB performance. We indicate the training scales for DISCO/DIFUSCO in parentheses.**
| Method |  |  |  |  | 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: Figure 8: Visualization of DISCO’s generated solutions on TSPLIB instances.
Refer to caption: x60.png

## Appendix F Decoding Strategy

For offline problems (Papadimitriou & Steiglitz, ; Martello et al., ),
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 (Deudon et al., ). We introduce the following decoding strategies combined with DISCO, including Greedy (Graikos et al., ), Sampling (Kool et al., ), and 2-OPT strategies (Croes, ).

#### 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. 7) to generate more confident solutions.

#### Sampling Strategy

Probabilistic solvers usually sample multiple solutions (Kool et al., ) 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 (Zhang et al., ).
Following this logic, we generate multiple heatmaps from $p_{\bm{\theta}}(\mathbf{x}_{0}|s)$ with different noise data $\mathbf{x}_{t}$ and then apply the greedy decoding algorithm described above to each heatmap.

#### 2-opt Strategy

We also adopt a 2-opt decoding strategy (Andrade et al., ) 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. () and use the Greedy+2-opt strategy as the default.

We conduct DISCO combined with all these strategies on TSP instances to demonstrate its robustness.
Following instructions from Böther et al. (), 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 (Velickovic et al., ) 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 $\bm{\theta}$, predicting the parameterized residue $\mathbf{x}_{res}^{\bm{\theta}}$ and noise $\bm{\epsilon}^{\bm{\theta}}$ simultaneously
with two independent convolutional layers.
We use a 12-layer anisotropic GNN with a width of 256 as DIFUSCO (Sun & Yang, ) does.
We adopt a linear schedule (Huang et al., ) to gradually reduce the noise during the model’s generation process.

Following Sun & Yang (), 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 set $k=100$.
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 results without fine-tuning.**
| Algorithm | Type | $k$ | TSP-5000 | TSP-8000 | TSP-10000 |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Length $\downarrow$ | Time $\downarrow$ | Length $\downarrow$ | Time $\downarrow$ | Length $\downarrow$ | Time $\downarrow$ |  |  |  |
| DISCO | SL+G${\dagger}$ | 50 | 52.36 | 5.03$\mathrm{m}$ | 66.14 | 13.48$\mathrm{m}$ | 73.85 | 24.80$\mathrm{m}$ |
| DISCO | SL+G${\dagger}$ | 100 | 52.48^∘ | 5.72$\mathrm{m}$ | 66.11^∘ | 14.32$\mathrm{m}$ | 73.85^∘ | 25.12$\mathrm{m}$ |
| DISCO | SL+S | 50 | 52.34 | 7.51$\mathrm{m}$ | 66.07 | 22.26$\mathrm{m}$ | 73.82 | 40.17$\mathrm{m}$ |
| DISCO | SL+S | 100 | 52.44^∘ | 9.06$\mathrm{m}$ | 66.06^∘ | 22.82$\mathrm{m}$ | 73.81^∘ | 48.77$\mathrm{m}$ |

For TSP-5000 instances, we train DISCO with instances of 64000 and batch size of 12.
For TSP-8000/10000, the model is trained using 6,400 instances with a batch size of 4.
Align with DIFUSCO,
we incorporate curriculum learning approach (Bengio et al., ) and begin the training process from the TSP-100 checkpoint.
For TSP-5000/8000/10000, we label training instances using the LKH-3 heuristic solver (Helsgaun, ) with 1000 trials.
For the TSP-50 and TSP-100 models used for the checkpoint, we generate 1502000 random instances labeled by Concorde solver, training with batch sizes of 256 and 128 respectively.

For the MIS instances, we use the training split of 49500 examples from SATLIB (Hoos & Stützle, ), training with a batch size of 64. For Erdős-Rényi graph sets (Erdős & Rényi, ), we use 60000 random instances from the ER-[700-800] variant and train DISCO with a batch size of 16. The training instances are labeled by the KaMIS heuristic solver (Lamm et al., ).

#### 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 (Qiu et al., ; Sun & Yang, ).
For small-scale TSP instances, i.e., TSP-50 and TSP-100, we evaluate on 1280 instances, while for TSP-5000/8000/10000, we use 16 instances. For MIS instances, we evaluate on 500 instances on SATLIB
and 128 instances on ER-[700-800].

## Appendix H Additional Results

### H.1 Generalization Results

We compare the generalization ability of our method with the diffusion solver DIFUSCO.
Both methods are trained on uniform distribution and tested on other different distributions for TSP-10000 instances, including
a normal distribution $\mathcal{N}(\mu,\sigma^{2})$ and a cluster distribution proposed by Bi et al. ().
For the normal distribution, we set $\mu=0.5$ and $\sigma^{2}=0.1$ to ensure a distinct difference from the training.
This generalization comparison does not include the diffusion solver T2T, due to its use of active search during deployment.
The comparisons are summarized in Tab. 8.

**Table 8: Evaluation results on different problem distributions.**
| Algorithm | Type | Uniform | Normal | Cluster |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Length $\downarrow$ | Time $\downarrow$ | Length $\downarrow$ | Time $\downarrow$ | Length $\downarrow$ | Time $\downarrow$ |  |  |
| DIFUSCO | SL+G${\dagger}$ | 73.99 | 35.38$\mathrm{m}$ | 116.76 | 29.27$\mathrm{m}$ | 37.84 | 30.25$\mathrm{m}$ |
| DISCO | SL+G${\dagger}$ | 73.85 | 25.12$\mathrm{m}$ | 116.34 | 25.57$\mathrm{m}$ | 37.74 | 28.13$\mathrm{m}$ |

### H.2 Resource Consumption Comparisons

We compare our algorithm with the state-of-the-art diffusion-based models, DIFUSCO and T2T, in terms of computational resources on TSP-10000 instances as presented in Tab. 9.

**Table 9: Comparisons on computational resources.**
| Algorithm | Type | Length $\downarrow$ | Gap $\downarrow$ | Time $\downarrow$ | GPU Memory $\downarrow$ | GPU hours $\downarrow$ |
| --- | --- | --- | --- | --- | --- | --- |
| DIFUSCO | SL+G${\dagger}$ | 73.99 | 3.10% | 35.38$\mathrm{m}$ | 14G | 0.59 |
| T2T | SL+G${\dagger}$ | 73.87 | 2.92% | 91.32$\mathrm{m}$ | 71G | 1.52 |
| DISCO | SL+G${\dagger}$ | 73.85 | 2.90% | 25.12$\mathrm{m}$ | 14G | 0.42 |

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: Please refer to the weaknesses.
soundness: 3
strengths: 1.	DISCO significantly reduces inference times by introducing an analytically solvable denoising process and constraining the sampling space.
2.	The paper is well-written.
summary: The paper introduces DISCO, a diffusion-based solver optimized for large-scale combinatorial optimization (CO) problems, such as the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Unlike traditional diffusion models, DISCO focuses on constraining the solution space to enhance quality and employs an analytically solvable denoising approach, which speeds up the process. Its twofold strategy—guided sampling and efficient denoising—achieves significantly faster inference times while maintaining high solution accuracy. DISCO's multi-modal search approach also allows it to generalize effectively to unseen problem scales.
weaknesses: 1.	The multi-modal graph search is presented as a crucial component of DISCO, with the paper asserting that its multi-modal output helps prevent sub-optimal solutions. However, the experiments do not thoroughly analyze the contribution of this module. It would be beneficial for the authors to include performance metrics with and without this module and detail the computational overhead incurred when it is enabled.
2.	The model's approach involves initially splitting the graph to find solutions, yet the problems tested (TSP, MIS) are inherently global, where localizing could risk sub-optimal outcomes. Could the authors clarify how this graph-splitting approach supports the model’s effectiveness in avoiding sub-optimal solutions for these global problems

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: From my perspective, the experiments are intensive enough to illustrate the effectiveness of the proposed method, and thus I have no more questions.
soundness: 3
strengths: 1. DISCO achieves state-of-the-art results on large-scale TSP-10000 instances and challenging MIS benchmarks, demonstrating superior performance both in terms of solution quality and speed.

2. The proposed divide-and-conquer strategy effectively generalizes DISCO to solve large-scale problem instances, highlighting the method’s scalability and versatility.

3. Beyond the previous results, the paper extends experiment results on aspects of 1) [which I think is the most significant challenge for the supervised learning framework] illustration of the generalization ability of DISCO 2) comparison of the time consumption and computational workload of DISCO 3) add more powerful baseline T2T[1] as comparison. These empirical results further validates the solidness of the paper.

[1] T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization, NeurIPS 2023.
summary: The paper presents DISCO, a novel algorithm developed to efficiently address large-scale combinatorial optimization (CO) problems. DISCO effectively manages the multi-modal complexity of CO landscapes, enabling swift solution generation and delivering high-quality results with notably fewer computational steps. Tested on extensive benchmarks, including large-scale Traveling Salesman Problems (TSP) and Maximal Independent Set (MIS), DISCO demonstrates state-of-the-art performance in both solution quality and inference speed.
weaknesses: The graph search might lead to exponential growth in trial variance.The scalability might still remain an issue. The authors have claimed the issue in limitation and leave it as future research oppurtunity.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: 1.	“X_d can be obtained by connecting vertices in the graph in a sequential order to form a tour.” I think X_d may have a huge impact on the solutions. How to ensure that X_d always guides the correct search direction? In training and testing, X_d is different. How can you ensure the effectiveness of trained model on test data?
2.	MCTS shows better performance than sampling in existing works and Table 3. The authors claim that “Xia et al. (2024) highlight that the MCTS strategy (Fu et al., 2021) heavily relies on TSP-specific heuristics, and is less suited to other problem types.”, but they are still solving TSP in Table 1. It is not reasonable to choose sampling rather than MCTS.
3.	Why the authors choose TSP-5000, 8000, and 10000? Does the proposed method still work on TSP 100, 500, 1000?
4.	In Table 3, why ATT-GCN performs very bad on TSP-5000, 8000 but performs much better and faster on TSP-10000?
soundness: 3
strengths: 1.	The idea of using a feasible solution as the residue constrain to guide the generation process sounds novel and reasonable. 
2.	Experimental results show that DISCO is both efficient and effective in solving large scale TSP problems.
summary: This paper presents a new approach, DISCO, designed to efficiently solve large-scale combinatorial optimization  problems using diffusion models. DISCO addresses two primary challenges in current diffusion solvers: sampling from extensive NP-complete solution spaces and the time-intensive denoising processes. By incorporating solution residues, DISCO focuses on meaningful solution domains, maintaining the multi-modal properties of CO problems while reducing computational overhead. The model also employs an analytically solvable denoising process that significantly cuts down inference time. DISCO demonstrates notable performance improvements on tasks such as the TSP and MIS. The method generalizes well to unseen problem scales through a divide-and-conquer approach, sometimes surpassing models trained specifically for those scales.
weaknesses: 1.	The novelty is limited. Solution residue is from [1] and multi-model is from [2]. Can you summarize the novelty of the proposed method?
2.	It is unclear why the residue term can lead to better solutions. Figure 1 is just an explanation of the intuition. More supporting analysis and evidence are needed.

[1] Liu, Jiawei, et al. "Residual denoising diffusion models." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.
[2] Fu, Zhang-Hua, Kai-Bin Qiu, and Hongyuan Zha. "Generalize a small pre-trained model to arbitrarily large tsp instances." Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 8. 2021.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: NA
soundness: 3
strengths: Strengths
The paper is well-structured and presents ideas in a clear, logical manner, and easy to read.
The proposed method demonstrates improvements on TSP and MIS.
summary: Summary
This paper introduces DISCO, a diffusion-based solver for combinatorial optimization  problems, using denoising diffusion probabilistic models (DDPM) with added solution residues to restrict search space. The forward diffusion process maps ground-truth solutions to a mixture of noise and degraded solutions. The authors also propose an accelerated sampling approach with fewer steps based on decoupled diffusion models (DDM). Experimental results on TSP and MIS demonstrate that the proposed method achieves the improved solution quality and a faster sampling.
weaknesses: Weaknesses
Incremental Innovation: While DISCO leverages DDPMs for CO problems with the inclusion of solution residues, the approach appears incremental. Prior work on CO tasks has explored conditioning on initial solutions, which limits the novelty here.
The technical methodology seems to follow the conventional DDPM structure closely. A clearer breakdown of the challenges specific to CO and the innovations made by DISCO would strengthen the contribution.
The proposed fast sampling process appears similar to existing DDM techniques, with limited innovation beyond adding residues. 
What is the performance (solution quality and sampling time) of the DIFUSCO baseline with DDM as sampler?
The performance improvement over DIFUSCO is marginal.
The claim regarding DISCO’s multi-modal property requires further justification. How this property enhances solution quality or contributes to CO performance is unclear without additional evidence or explanation.

Meta-review: (a) Summarize the scientific claims and findings: The paper claims DISCO achieves faster inference times and higher accuracy on large-scale combinatorial optimization problems like TSP and MIS by introducing residue-constrained denoising and a multi-modal graph search, but reviewers have raised concerns about the novelty and significance of these contributions.

(b) What are the strengths of the paper? The paper is well-written and presents a comprehensive evaluation of DISCO on large-scale TSP and MIS problems, demonstrating its efficiency and generalization ability.

(c) What are the weaknesses of the paper? Despite the authors' claims, reviewers find the novelty and significance of the contributions limited, particularly the use of conditional guidance and the multi-modal graph search, which are already adopted in existing diffusion models.

(d) Provide the most important reasons for your decision to reject. While the paper presents a well-executed approach, the limited novelty and marginal improvements over existing methods do not meet the bar for acceptance at this venue, where significant contributions to the field are expected.

Decision: Reject