DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
Authors: Zhiqing Sun
Yiming Yang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: neural-symbolic reasoning
combinatorial optimization
diffusion models
TL;DR: We developed the first diffusion model-based solver on graphs for combinatorial optimization problems.

Abstract: Neural network-based Combinatorial Optimization (CO) methods have shown promising results in solving various NP-complete (NPC) problems without relying on hand-crafted domain knowledge. This paper broadens the current scope of neural solvers for NPC problems by introducing a new graph-based diffusion framework, namely DIFUSCO. It formulates NPC problems into a discrete {0, 1}-vector space and uses graph-based denoising diffusion models to generate high-quality solutions. Specifically, we explore diffusion models with Gaussian and Bernoulli noise, respectively, and also introduce an effective inference schedule to improve the generation quality. We evaluate our methods on two well-studied combinatorial optimization problems: Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Experimental results show that DIFUSCO strongly outperforms the previous state-of-the-art neural solvers, improving the performance gap between ground-truth and neural solvers from 1.76% to 0.46% on TSP-500, from 2.46% to 1.17% on TSP-1000, and from 3.19% to 2.58% on TSP-10000. For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark. Our code is available at [this url](https://github.com/Edward-Sun/DIFUSCO).

DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
Zhiqing Sun' Language Technologies Institute Carnegie Mellon University zhiqings@cs. cmu.edi
Yiming Yang Language Technologies Institute Carnegie Mellon University yimingocs cmu. cmu.edu
Abstract
Neural network-based Combinatorial Optimization (CO) methods have shown promising results in solving various NP-complete (NPC) problems without relying on hand-crafted domain knowledge. This paper broadens the current scope of neural solvers for NPC problems by introducing new graph-based diffusion framework, namely DIFUSCO. Our framework casts NPC problems as discrete {0, 1)-vector optimization problems and leverages graph-based denoising diffusion models to generate high-quality solutions. We investigate two types of diffusion models with Gaussian and Bernoulli noise, respectively, and devise an effective inference schedule to enhance the solution quality. We evaluate our methods on two well-studied NPC combinatorial optimization problems: Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Experimental results show that DIFUSCO strongly outperforms the previous state-of-the-att neural solvers, improving the performance gap between ground-trutt truth and neural solvers from 1.76% to 0.46 on TSP-500, from 2.46% to 1.17% on TSP-1000, and from 3.19% to 2.58 % on TSP-10000, For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.
Introduction
Combinatorial Optimization (CO) problems are mathematical problems that involve finding the optimal solution in a discrete space. They are fundamental challenges in computer science, especially the NP-Complete (NPC) class of problems, which are believed be intractable in polynomial time. Traditionally, NPC solvers rely integer programming (IP) or hand-crafted heuristics, which demand significant expert efforts to approximate near-optimal solutions [4, 31].
Recent development in deep learning has shown new promise in solving NPC problems. Existing neural CO solvers for NPC problems can be roughly classified into three categories based how the solutions are generated, i.e., the autoregressive constructive solvers, the non-autoregressive constructive solvers, and the improvement heuristics solvers. Methods in the first category use autoregressive factorization to sequentially grow valid partial solution [6, 64]. Those methods typically suffer from the costly computation their sequential decoding parts and hence are difficult to scale to large problems [27]. Methods in the second category rely on -on-autoreeressvve modeling for scaling up. with a conditional independence assumption among variables as typical [53, 55, 92]. Such an assumption, however, unavoidably limits the capability of those methods to capture the multimodal nature of the problems [57, 33], for example, when multiple optimal solutions exists for the same graph. Methods in the third category (improvement heuristics solvers) use Markov decision process (MDP) to iteratively refines an existing feasible solution with neural network-guided local operations such 2-opt [71, 2] and node swap [17, 113]. These methods
"Our code is available at https://githur www//owarrreeeeee Sun/DIFUSCO.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

have also suffered from the difficulty in scaling up and the latency in inference, partly due to the sparse rewards and sample efficiency issues when learning improvement heuristics a reinforcement learning (RI.) framework [113,79] 79].
Motivated by the recent remarkable success of diffusion models in probabilistic generation [102, 40, 94, 120, 96], we introduce a novel approach named DIFUSCO, which stands for the graph-based DIFIUsion Solvers for Combinatorial Optimization. To apply the iterative denoising process of diffusion models to graph-based settings, we formulate each NPC problem as to find {0, 1 J-valed vector that indicates the optimal selection of nodes or edges in candidate solution for the task. Then we use message passing based graph neural network [61, 36, 29, 107] to encode each instance graph and to denoise the corrupted variables. Such a graph-based diffusion model overcomes the limitations of previous neural NPC solvers from a new perspective. Firstly, DIFUSCO can perform inference on all variables in parallel with a few (< N) denoising steps (Sec. 3.3), avoiding the sequential generation problem of autoregressive constructive solvers. Secondly, DIFUSCO can model a multimodal distribution via iterative refinements, which alleviates the expressiveness limitation of previous von-autoregressive constructive models. Last but not least, DIFUSCO is trained in an efficient and stable manner with supervised denoising (Sec. 3.2), which solves the training scalability issue of RL-based improvement heuristics methods.
We should point out that the idea of utilizing diffusion- based generative model for NPC problems has been explored recently in the literature. In particular, Graikos et al. [32] proposed an image- diffusion model to solve Euclidean Traveling Salesman problems by projecting each TSP instance onto a 64 x 64 greyscale image space and then using Convolutional Neural Network (CNN) to generate the predicted solution image. The main difference between such image-based diffusion solver and our graph-based diffusion solver is that the latter can explicitly model the node/edge selection process via the corresponding random variables, which is a natural design choice for formulating NPC problems (since most of them are defined over a graph), while the former does not support such desirable formalism. Although graph-based modeling has been employed with both constructive [64] and improvement heuristics [20] solvers, how to use graph-based diffusion models for solving NPC problems has not been studied before, to the best of our knowledge.
We investigate two types of probabilistic diffusion modeling within the DIFUSCO framework: continuous diffusion with Gaussian noise [16] and discrete diffusion with Bernoulli noise [5, 44]. These two types of diffusion models have been applied to image processing but not to NPC problems so far. We systematically compare the two types of modeling and find that discrete diffusion performs better than continuous diffusion by significant margin (Section 4). We also design effective inference strategy to enhance the generation quality of the discrete diffusion solvers.
Finally, we demonstrate that a single graph neural network architecture, namely the Anisotropic Graph Neural Network [9, 54], can be used as the backbone network for two different NP-complete combinatorial optimization problems: Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Our experimental results show that DIFUSCO outperforms previous probabilistic NPC solvers on benchmark datasets of TSP and MIS problems with various sizes.
2
Related Work
2.1 Autoregressive Construction Heuristics Solvers
Autoregressive models have achieved state-of-the results as constructive heuristic solvers for combinatorial optimization (CO) problems, following the recent success of language modeling in the text generation domain [106, 11]. The first approach proposed by Bello et al. [6] uses a neural network with reinforcement learning to append one new variable to the partial solution at each decoding step until a complete solution is generated. However, autoregressive models [64] face high time and space complexity challenges for large-scale NPC problems due to their sequential generation scheme and quadratic complexity in the self-attention mechanism [106].
2.2 Non-autoregressive Construction Heuristies Solvers
Non-autoregressive (or heatmap) constructive heuristics solvers [53, 27, 28, 92] are recently proposed to address this scalability issue by assuming conditional independence among variables in NPC problems, but this assumption limits the ability to capture the multimodal nature [57, 33] of high-

---

quality solution distributions. Therefore, additional active search [6. 92] or Monte-Carlo Tree Search (MCTS) [27, 98] are needed to further improve the expressive power of the con-autoregrresive scheme.
DIFUSCO can be regarded as member in the non-autorrgrressive constructive heuristics category and thus can be benefited from heatmap search techniques such as MCTS. But DIFUSCO uses an iterative denoising scheme generate the final heatmap. which significantly enhances its expressive power compared to previous non-autoregressivv methods.
2.3 Diffusion Models for Discrete Data
Typical diffusion models [100, 102, 40, 103, 85, 56] operate in the continuous domain, progressively adding Gaussian noise to the clean data in the forward process, and learning to remove noises in the reverse process in a time framework.
Discrete diffusion models have been proposed for the generation of discrete image bits or texts using binomial noises [100] and multinomial/categriica noises [5, 44]. Recent research has also shown the potential of discrete diffusion models in sound generation [118], protein structure generation [77], molecule generation [108], and better text generation [52, 38].
Another line of work studies diffusion models for discrete data by applying continuous diffusion models with Gaussian noise on the embedding space of discrete data [30, 69, 24], the {-1.0, 1.0} real-number vector space [16], and the simplex space [37]. The most relevant work might be Niu et al. [86], which proposed a continuous score-based generative framework for graphs, but they only evaluated simple non-NP-hard CO tasks such as Shortest Path and Maximum Spanning Tree.
3 DIFUSCO: Proposed Approach
3.1 Problem Definition
Following a conventional notation [88], we define X,- = 10 as the space of candidate solutions {x] for CO problem instance s, and c₂ : X, + R the objective function for solution x E Xg: (x) = cost(xx55) s) + valid s).
(1)
Here cost(-) is the task-specific cost of candidate solution (e.g., the tour length in TSP), which is often simple linear function of x in most NP-complete problems, and valid(-) is the validation term that returns for feasible solution and +oo for an invalid one. The optimization objective is find the optimal solution x** for given instance $ as:
arrgmin C3 (x).
xEX,
This framework is generically applicable to different NPC problems. For example, for the Traveling Salesman Problem (TSP), x E 1 is the indicator vector for selecting a subset from N edges; the cost of this subset is calculated as: costrsr (x, s) E, x; d(e), where d!") denotes the weight of the i-th edge in problem instance s, and the valid(-) part of Formula (1) ensures that x is tour that visits each node exactly once and returns to the starting node at the end. For the Maximal Independent Set (MIS) problem, x E {0, 1J is the indicator vector for selecting a subset from N nodes; the cost of the subset is calculated as: costMis (x, s) = E, (1 æz)., and the corresponding valid(-) validates x is an independent set where each node in the set has no connection to any other node in the set.
Probabilistic neural NPC solvers [6] tackle instance problem by defining parameterized condi- tional distribution Po (x(s). such that the expected cost ExEx, (x(x) p(([ss) s) is minimized. Such probabilistic generative models are usually optimized by reinforcement learning algorithms [111, 63). In this paper, assuming the optimal (or high-quality) solution x is available for each training in- stance we optimize the model through supervised learning. Let S = {s:)] } be independently and identically distributed (IID) training samples for type of NPC problem, we aim to maximize the likelihood of optimal (or high-quality) solutions, where the loss function L is defined as:
I((I)= E,es [- lo [x*
Next, we describe how to use diffusion models to parameterize the generative distribution Pa- For brevity, we omit the conditional notations of 8 and denote x** as Xy as a convention in diffusion models for all formulas in the the rest of the paper.
3

---

3.2 Diffusion Models in DIFUSCO
From the variational inference perspective [60], diffusion models [100, 40, 102] are latent variable models of the form pe (x)) = J ) where XI...., .r are latents of the same dimen-
sionality as the data Xo ~ (xx)). The joint distribution pe (x p(xT) IT Pe (x (xx) is the learned reverse (denoising) process that gradually denoises the latent variables toward the data distribution, while the forward process (xx1://x0) =
I (xx((xx-1) gradually corrupts the data into noised latent variables. Training is performed by optimizing the usual variational bound on negative log- ligllikei:ooo:
(Xo:T)
- log po (xo)] 2 E,g
log
(x11 (xo)
(4)
Egg
DKL
xx)] (xo
+ +C
1>1
where a constant.
Discrete Diffusion In discrete diffusion models with multinomial noises [5, 44]. the forward
3,)
²r
process is defined as: (xx()x(1)) Cat (xrip = x where Q:
3r (1 [c] is
the transition probability matrix; E {0, 1] Nx2 is converted from the original vector x E {0, 1] with one-hot vector per row; and X computes a row-wise vector-matrix product.
Here, 3r denotes the corruption ratio. Also, we want IT (1 - 3₂) = 0 such that Xy ~ Uniform(.).
The t-step marginal can thus be written
(xx)(xo) Cat (x,; k X Q₂)
where Q
Q1Q2 Q2Q.... ... Q.. And the posterior at time t - can be obtained by Bayes' theorem:
(xx1-1xx,xx)) xo) q(x,/xx, Xx (x) (xo)
x Q 2 0x
Cat xt-1;p=
(5)
(x, Xo)
X Q
where @ denotes the element-wise multiplication.
According to Austin et al. [5], the denoising neural network is trained to predict the clean data po(X) (Xo xt), and the reverse process is obtained by substituting the predicted X, as Xg in Eq. 5:
Σ
=
Continuous Diffusion for Discrete Data The continuous diffusion models [102, 40] can also be directly applied to discrete data by lifting the discrete input into continuous space [16]. Since continuous diffusion models usually start from a standard Gaussian distribution 6 A/(0, I),
Chen et al. [16] proposed to first rescale the {0, 1-valued variables to the {-1, 1} domain as kg. and then treat them as real values. The forward process in continuous diffusion defined as: (xx, 11) = (xx vI 3, B,1).
Again, 3r denotes the corruption ratio, and we want II (1 B,) such that xy -V()). The t-step marginal can thus be written as: (( = N (xx: v / (1 - I) where a 3e and ār II Cr., Similar to Eq. 5, the posterior at time t 1 can be obtained by Bayes' theorem:
g (x,-1 Xr xo) = q(x,, 1 X (x, -11x)
ql (8,1)8))
which is closed-form Gaussian distribution [40]. In continuous diffusion, the denoising neural network trained to predict the unscaled Gaussian noise é; = (&, va, (erko)/VT.. a = (x 1).
The reverse process [40] can use point estimation of xn in the posterior:
*; vi - (x,,
Po ( =
(8)
Vau
For generating discrete data, after the continuous data No generated, thresholding/guunnizaiii operation is applied to convert them back to {0, ---uud variables xo the model's prediction.

---

3.3 Denoising Schedule for Fast Inference
One way to speed up the inference of denoising diffusion models is to reduce the number of steps in the reverse diffusion process, which also reduces the number of neural network evaluations. The denoising diffusion implicit models (DDIMs) [101] are class of models that apply this strategy in the continuous domain, and similar approach can be used for discrete diffusion models [5].
Formally, when the forward process is defined not on all the latent variables X1:7, but on a subset
fx+ ....:................. Xrar ), where is increasing sub-sequence of [1, [I..... T with length M, x,, = 1 and XTMr = T, the fast sampling algorithms directly models ((x Xx,, Xu). Due to the space limit, the detailed algorithms are described in the appendix.
We consider two types denoising scheduled for r given the desired card(r) < T: linear and cosine. The former uses timesteps such that = Lee] for some and the latter uses timesteps such that 7; [cos( (1=o)) T| for some c. The intuition for the cosine schedule is that diffusion models can achieve better generation quality when iterating more steps in the low-noise regime [85, 121, 13].
3.4 Graph-based Denoising Network
The denoising network takes as input a set of noisy variables x, and the problem instance s and predicts the clean data Xg. To balance both scalability and performance considerations, an anisotropic graph neural network with edge gating mechanisms [9, 54] as the backbone network for both discrete and continuous diffusion models, and the variables in the network output can be the states of either nodes, as in the case of Maximum Independent Set (MIS) problems, or edges, as in the case of Traveling Salesman Problems (TSP). Our choice of network mainly follows previous work [54, 92], as AGNN can produce the embeddings for both nodes and edges, unlike typical GNNs such as GCN [62] or GAT [107], which are designed for node embedding only. This design choice is particularly beneficial for tasks that require the prediction of edge variables.
adopt
Anisotropic Graph Neural Networks Let h and ely denote the node and edge features at layer the sinusoidal features [106] of denoising
é associated with node and edge ij, respectively. timestep t. The features at the next layer is propagated with an anisotropic message passing scheme:
(+1 = + Qh + R'n e
+ 1)) + (t),(t), h h + a(BN(U' ASEN (o(e(t)) o v(n))),
19 = e + MLP.,BNNC
where Uh, V pd Q' R² E Rddd are the learnable parameters of layer f, a denotes the ReLU [66] activation, BN denotes the Batch Normalization operator [51], A denotes the aggregation function SUM pooling [116], o is the sigmoid function, O is the Hadamard product, NG denotes the neighborhoods of node i, and (LP(.) denotes a 2-layer multi-layer perceptron.
For TSP, el are initialized as the corresponding values in x4, and h. are initialized as sinusoidal features of the nodes. For MIS. ei, initialized zeros, and h initialized as the corresponding values in X,. A 2-neuron and 1 -neuron classification/reersssioo head is applied to the final embeddings of x, (fe,g) }o for edges and (h,} for nodes) for discrete and continuous diffusion models, respectively.
Hlype-parammter For all TSP and MIS henchmarks, we use a 12-layer Anisotropic GNN with a width of 256 as described above.
3.5 Decoding Strategies for Diffusion-basel Solvers
After the training of the parameterized denoising network according to Eq. 4, the solutions are sampled from the diffusion models po (x)])))) for final evaluation. However, probabilistic generative models such as DIFUSCO cannot guarantee that the sampled solutions are feasible according to the definition of CO problems. Therefore, specialized decoding strategies are designed for the two CO problems studied in this paper.
5

---

Heatmap Generation The diffusion models Po(-Is) produce discrete variables x as the final pre- dictions by applying Bernoulli sampling (Eq. 6) for discrete diffusion or quantization for continuous diffusion. However, this process discards the comparative information that reflects the confidence of the predicted variables, which is crucial for resolving conflicts in the decoding process. To preserve this information, we adapt the diffusion models to generate heatmaps [53, 92] by making the following appropriate modifications: 1) For discrete diffusion, the final score of po (xo = 1[s) is preserved the heatmap scores; 2) For continuous diffusion, we remove the final quantization and use ($0, + 1) as the heatmap scores. Note that different from previous heatmap approaches [53, 92] that produce single conditionally independent distribution for all variables, DIFUSCO can produce diverse multimodal output distribution by using different random seeds.
TSP Decoding Let {A,} be the heatmap scores generated by DIFUSCO denoting the confidence of each edge. We evaluate two approaches as the decoding method following previous work [32, 92];
1) Greedy decoding [32], where all the edges are ranked by (Aig + A - Cý and are inserted into the partial solution if there are no conflicts. 2-opt heuristics [71] are optionally applied. 2) Monte Carlo Tree Search (MCTS) [27]. where k-opt transformation actions are sampled guided by the heatmap scores to improve the current solutions. Due to the space limit, detailed description of
two decoding strategies can be found in the appendix.
MIS Decoding Let {a;} } be the heatmap scores generated by DIFUSCO denoting the confidence of each node. A greedy decoding strategy is used for the MIS problem, where the nodes are ranked by a, and inserted into the partial solution if there are no conflicts. Recent research [8] pointed out that the graph reduction and 2-opt search [2] can find near-optimal solutions even starting from randomly generated solution, so we do not use any post-proesssing for the greedy-dccoded solutions.
Solution Sampling A common practice for probabilistic CO solvers [64] is to sample multiple solutions and report the best one. For DIFUSCO, we follow this practice by sampling multiple heatmaps from po (x)]s) with different random seeds and then applying the greedy decoding algorithm described above to each heatmap.
Experiments with TSP
We use 2-D Euclidean TSP instances to test our models. We generate these instances by randomly sampling nodes from a uniform distribution over the unit square. We use TSP-50 (with 50 nodes) the main benchmark compare different model configurations. We also evaluate our method on larger TSP instances with 100, 500, 1000, and 10000 nodes to demonstrate its scalability and performance against other tfateoff-the-at methods.
4.1 Experimental Settings
Datasets We generate and label the training instances using the Concorde exact solver [3] for TSP-50/100 and the I.H-3 heuristic solver [39] for TSP-500/1000/10000 We use the same test instances as [54, 64] for TSP-50/100 and [27] for TSP-500/1000/10000
Graph Sparsification We use sparse graphs for large-scale TSP problems reduce the computa- tional complexity. We sparsify the graphs by limiting each node to have only i edges to its nearest neighhors based on the Euclidean distances. We set l to 50 for TSP-500 and 100 for TSP-110001000 This way, we avoid the quadratic growth of edges in dense graphs as the number of nodes increases.
Model Settings T= 1000 denoising steps are used for the training of DIFUSCO on all datasets. Following Ho et al. [40]. Graikos et al. [32], use simple linear noise schedule for 1T where 31 = 10 and BT 0.02. We follow Graikos et al. [32] and use the Greedy decoding 2-opt scheme (Sec. 3.5) the default decoding scheme for experiments.
Evaluation Metries In order to compare the performance of different models, we present three metrics: average tour length (Length), average relative performance gap (Gap), and total run time (Time). The detailed description can be found in the appendix.

---

10001
Liea solcout:
Table I: Comparing results TSP-50 and TSP-100. denotes the baseline for computing the performance gap. indicates that the diffusion model samples single solution as its greedy decoding scheme. Please refer to Sec. 4 for details.
090
Costre scteddde
ALGORITHM
TYPE
TSP-50 LENGTHL
GAP(N)) LENGTH 4 GAP(S)
TSP-100
2010 STQ 2053
CONCORDE
EXACT
5.69
0.00
7.76
0.00
3.6
Contino.s cocuns
2-OPT
HEURISTICS
5.86
2.95
8.03
3,54
Conten-sttneer
5.80
1.76
8.12
4.53
0.8
GCN
GREENY
5.87
3.10
8.41
8.38
TRANSFORMER
GREEDY
5,71
0.31
7.88
1.42
POMO
GREEDY
7.84
1.07
0.2
SYM-NCO
DPDP
JE-MPROVEMEETS
GREEDY
5.70
0.14
7.89
7.84
0.94
1.62
DIFFUSION
5.76
1.23
7.92
2.11
OURS
GREEDY!
5.70
0.10
7.78
0.24
202
Offfudan shrps
Lkx SAMPLING
2.26
GCN
21 2 SAMPLING
5.70
0.01
7.87
1.39
Figure 1: Comparison of continu- (Gaussian noise) and discrete (Bernoulli noise) diffusion models with different inference diffusion steps and inference schedule (linear V.S. cosine).
TRANSFORMER
24 SAMPLING
5.69
0.00
7.76
0.39
7.77
SYM-NCO
100> SAMPLING
7.79
0.39
MDAM
30x SAMPLING
5,70
0.03
7.79
0.38
DPDP
100%-IMPROWMMEN IMPROVMMENTS
5.70
0.00
0.00
OURS
16x5 AMPLING
5.69
-0.01
7.76
-0.01
ORT
642
002
0.0
DJ344
8065
0007
335
12A4
10:5
8.00
DIMAA
2035
0.35
10
3124 Samples
33
4 Samples
0.09
0.35
DC5
005
0.25
0:34
0.332
0.225
1,023
220
20
1.3
0.323
100%
+0 06
0.05
12
Diffuskon
DiTlasion
Diffusionn stops
(a) Continuous difffusion
(b) Discrete diffusion
(c) Runtime
Figure 2: The performance Gap (%) are shown for continuous diffusson (a) and discrete diffusion (b) models on TSP-50 with different diffusion steps and number of samples. Their corresponding per-instance run-time (sec)
are shown in (c), where decomposed analysis (neural network greedy decoding + 2-opt) can found the appendix.
4.2 Design Analysis
Discrete Diffusion v.s. Continuous Diffusion We first investigate the suitability of two diffusion approaches for combinatorial optimization, namely continuous diffusion with Gaussian noise and discrete diffusion with Bernoulli noise (Sec. 3.2). Additionally, we explore the effectiveness of different denoising schedules, such as linear and cosine schedules (Sec. 3.3), on CO problems. To efficiently evaluate these model choices, we utilize the TSP-50 benchmark.
Note that although all the diffusion models are trained with a T = 1000 noise schedule, the inference schedule can be shorter than T, as deseribed in Sec. 3.3. Specifically, models with 1, 2, 5, 10, 20, 50, 100, and 200 diffusion steps.
interested in diffusion
Fig. 1 demonstrates the performance of two types of diffusion models with two types of inference schedules and various diffusion steps. We can see that discrete diffusion consistently outperforms the continuous diffusion models by large margin when there more than 5 diffusion steps?. Besides, the cosine schedule is superior to 1 linear on discrete diffusion and performs similarly on continuous diffusion. Therefore, we use cosine for the rest of the paper.
More Diffusion Iterations v.s. More Sampling By utilizing effective denoising schedules, diffu- sion models are able to adaptively infer based on the available computation budget by predetermining the total number of diffusion steps. This is similar to changing the number of samples in previous probabilistic neural NPC solvers [64]. Therefore, we investigate the trade-off between the number of diffusion iterations and the number of samples for diffusion-based NPC solvers.
We also observe similar patterns TSP-100, where the results reported in the appendix.
7

---

Table 2: Results on large-scale TSP problems. RL, SI., AS, G. S. BS, and MCTS denotes Reinforcement Learning, Supervised Learning, Active Search, Greedy decoding, Sampling decoding, Ream-search, and Monte Carlo Tree Search, respectively. * 'idiccates the baseline for computing the performance gap. Results of baselines are taken from Fu et al. [27] and Qiu et al. [92]. so the runtime may not be directly comparable. See Section 4 and appendix for detailed descriptions.
TSP-500
TSP-1000
TSP-10000
ALGORITHM
TYPE
LENGTH
GAP
TIME L LENGTH
GAP L
TIME
LENGTH
GAP
TIME
CONCORDE
EXACT
16.55"
37.66m
23.12"
6.65h
N/A
N/A
NIA
GUROBI
EXACT
16.55
0.00%
45.63h
N/A
NIA
N/A
N/A
N/A
N/A
LKH-3 (DEFAULT)
HEURISTICS
16.55
0.00%
3.03m 46.28m
23.12
0.00%
2.57h
71.77"
8.8h
LKH-3 (LESS TRAILS)
HEURISTICS
16.55
0.00%
23.12
0.00%
7.73m
71.79
51.27m
FARTHEST INSERTION
HEURISTICS
18.30
10.57%
Os
25.72
11.25%
0s
80.59
12.29%
AM
RL+G
20.02
20.99%
1.51m
31.15
34.75%
3.18m
141.68
97.39%
5.99m
GCN
S1.+G
29.72
79.61%%
6.67m
48.62
110.29%
28.52m
N/A
N/A
NIA
POMO+EAS EMB
RL+AS+G
19.24
16.25%
12.80h
N/A
NIA
N/A
N/A
N/A
N/A
POMO+EAS-TAN
RL++A++G
24.54
48.22%%
11.61h
49.56
114.36%
63.45h
N/A
N/A
N/A
DIMES
RL+G
18.93
14.38%
0.97m
26.58
14.97%
2.08m
86.44
20.44%
4.65m
DIMES
RL+AS+G
17.81
7.61%
2.10h
24.91
7.74%
4.49h
80.45
12.09%
3.07h
(DIFUSCO)
SL+G|
10.85%
m.61
26.14
11.86m
98.15
36.75%
OURS (DIFUSCO)
S1.+
16.80
1.49
3.65m
23,56
1.90%
12.06m
73.99
3.10%
35.38m
EAN
RL+S+2-OPT
23.75
43. 53.57%
57. 76m
47.73
106.46%
5.39h
N/A
N/A
N/A
18.03%
21.99m
29.90
29.23%
1.64h
129.40
80.28%
1.81h
GCN
SL+BS
30.37
83.55%
38.02m
51.26
121.73%
51.67m
N/A
N/A
N/A
DIMES
18.84
1.06m
26.36
2.38m
85.75
DIMES
RL+AS+S
17.80
7.55%
2.1
24.89
7.70%
4,53h
80.42
12.05%
3.12h
OURS (DIFUSCO)
SL+S
17.23
4.08%
11.02m
25.19
8.95%
46.08m
95.52
33.09%
6.59h
OURS (DIFUSCO)
SL+S+2-OPT
16.65
0.57 %
11.46m
23.45
1.43%
48.09m
73.89
2.95% %
6.72h
ATT-GCN
SL+MCTS
16.97
2.54%
2.20m
23.86
3.22%
4. 4.10m
74.93
4.39%
21.49m
DIMES
RL+MCTS
16.87
1.93%
2.92m
23.73
2.64%
6.87m
74.63
3.98%
29.83m
DIMES
RL+AS+MCTS
16.84
1.76%
2.15h
23.69
2.46%
4.62h
74.06
3.19%
3.57h
OURS (DIFUSCO)
SL+MCTS
16.63
0.46%
10.13m
23.39
1.17%
24.47m
73.62
2.58%
47.36m
Fig. 2 shows the results of continuous diffusion and discrete diffusion with various diffusion steps and number of parallel sampling. as well as their corresponding total run-time. The cosine denoising schedule is used for fast inference. Again, we find that discrete diffusion outperforms continuous diffusion across various settings. Besides, we find performing more diffusion iterations is generally more effective than sampling more solutions, even when the former uses less computation. For exam- (
ple, 20 (diffusion steps) x 4 (samples) performs competitive to 1 (diffusion steps) x 1024 (samples), while the runtime of the former is 18.5x less than the latter.
In general, we find that 50 (diffusion steps) x (samples) policy and 10 (diffusion steps) x 16 (samples) policy make good balance between exploration and exploitation for discrete DI- FUSCO models and use them as the Greedy and Sampling strategies for the rest of the experiments.
4.3 Main Results
Comparison to SOTA Methods We compare discrete DIFUSCO other state-of- the-art neural NPC solvers on TSP problems across various scales. Due to the space limit, the description of other baseline models can be found in the appendix.
Tab. compare discrete DIFUSCO with other models on TSP-50 and TSP-100, where DIFUSCO achieves the state-of-the-art performance in both greedy and sampling settings for probabilistic solvers.
Tab. 2 compare discrete DIFUSCO with other models on the larger-scale TSP-500, TSP-1000, and TSP- 10000 problems. Most previous probabilistic solvers (except DIMES [92]) becomes untrainable on TSP problems of these scales, so the results of these models are reported with 1SP-100 trained models. The results are reported with greedy, sampling, and MCTS decoding strategies, respectively. For fair comparisons [27, 92], MCTS decoding for TSP is always evaluated with only one sampled heatmap. From the table, we can see that DIFUSCO strongly outperforms the previous neural solvers on all three settings. In particular, with NCTSSbaase decoding, DIFUSCO significantly improving the performance gap between ground-truth and neural solvers from 1.76% to 0.46% % on TSP-500, from 2.46% to 1.17% on TSP-1000, and from 3.19% to 2.58% % TSP-10000
8

---

Table 3: Results on MIS problems. indicates the baseline for computing the optimality gap. RL. SL. G, S, and TS denote Re- inforcement Learning, Supervised Learning. Greedy decoding, Sampling decoding, and Tree Search, respectively. Please refer to Sec. 5 and appendix for details.
15P-50
0.097
0:44
<4
19
Training Data
T5P-100
0.2
74
14
7.6
TSP 500
2.6
1.
13
11
54
TSP 1900
2.6
1.
1.6
1.1
25
SATLIB
CR UR-1700-8000
TSF110000
25
266
25
11
METHOD
TYPE
Size
GAP
TIME 4 Size GAP
TIME.
1SP.50
1303000
T3R5500
7S% 1000
TSP320000
GUROBI
KAMIS
HRURISTICS
ВXACT
425.96"
425.95
0.00%
37.58m
26. 26.00m
44,87"
41.38
7.78%
50.00m
$2. 13m
INTEL
SL+G
420,66
1.48%
23.05m
34.86
22.31%
6.06 666
Evsluetion
INTRI
SL4TS
N/A
N/A
NIA
13.43%
20.00M
Figure 3: Generalization tests of DIFUSCO trained and evaluated on TSP problems across various scales. The performance Gap (%) with greedy decoding and 2-opt is re- ported.
DGL
SL+TS
N/A
N/A
NIA
37.26
16.96%
22.71m
TWD
RI.48
422.22
0.88%
18.83m
41.17
8.25%
6.33m
DIMES
RL+GG
421.24
1.11%
24.17m
38.24
14.78%
6.12m
DIMES
RL+S
423,28
0.63%
20.26m
42.06
6.26%
12.01m
OURS
SL+G
424.50
0.34%
8.76m
38.83
12.40%
8.80m
OURS
SL4S
425.13
0.21% %
23.74m
41.12
8.36%
26.67m
Generalization Tests Finally, we study the generalization ability of discrete DIFUSCO trained on set of TSP problems of specific problem scale and evaluated on other problem scales. From Fig. 3, we can see that DIFUSCO has a strong generalization ability. In particular, the model trained with TSP-50 perform well on even TSP-1000 and TSPO-10000. This pattern is different from the bad generalization ability of RL-trained or SL-trained non non-autoregressive methods as reported in previous work [54].
5 Experiments with MIS
For Maximal Independent Set (MIS), experiment on two types of graphs that recent work [70, 1, 8, 92] shows struggles against, i.e., SATLIB [46] and Erdōs-Rényi (ER) graphs [26]. The former is of graphs reduced from SAT instances in CNF, while the latter are random graphs We use ER-[700-800 for evaluation, where [R-[n-N] indicates the graph contains n to N nodes. Following Qiu et al. [92], the pairwise connection probability p set 0.15.
Datasets The training instances of labeled by the KaMIS heuristic solver. The split of test instances on SAT datasets and the andom-generaan ER test graphs are taken from Qiu et al. [92].
Model Settings The training schedule the same as the TSP solver (Sec. 4.1). For SATLIB, we use discrete diffusion with 50 (diffusion steps) x1 (samples) policy and 50 (diffusion steps) x4 (samples) policy as the Greedy and Sampling strategies, respectively. For ER graphs, we use continuous diffusion with 50 (diffusion steps) (samples) policy and 20 (diffusion steps) x 8 (samples) policy as the Greedy and Sampling strategies, respectively.
Evaluation Metrics We report the average size of the independent set (Size), average optimality gap (Gap), and latency time (Time). The detailed description can be found in the appendix. Notice that we disable graph reduction and 2-opt local search in all models for fair comparison since is pointed out by [8] that all models would perform similarly with local search post-processing.
Results and Analysis Tab. 3 compare discrete DIFUSCO with other baselines on SATLIB and ER-[700-800] benchmarks. We can see that DIFUSCO strongly outperforms previous ofate-of-the-art methods on SATLIB benchmark, reducing the gap between ground-truth and neural solvers from 0.63% to 0.21 %. However, we also found that DIFUSCO (especially with discrete diffusion in our preliminary experiments) does not perform well on the ER-[700-808 800] data. We hypothesize that this because the previous methods usually use the nase- graph neural networks such as GCN [62] or GraphSage [36] as the backbone network, while we use an edge-based Anisotropic GNN (Sec. 3.4), whose inductive bias may be not suitable for ER graphs.
(MIT License)

---

Concluding Remarks
We proposed DIFUSCO, a novel graph-based diffusion model for solving Nomcoelee combinatorial optimization problems. We compared variants of graph-based diffusion models: one with continuous Gaussian noise and one with discrete Bernoulli noise. We found that the discrete variant performs better than the continuous one. Moreover, designed a cosine inference schedule that enhances the effectiveness of our model. DIFUSCO achieves state-of-the-ar results on TSP and MIS problems, surpassing previous probabilistic NPC solvers in both accuracy and scalability.
For future work, we would like to explore the potential of DIFUSCO in solving a broader range of NPC problems, including Mixed Integer Programming (discussed in the appendix). We would also like to explore the use of equivariant graph neural networks [117, 7, 45] for further improvement of the diffusion models on geometrical NP-complete combinatorial optimization problems such as Euclidean TSP. Finally, we are interested in utilizing (higher-order) accelerated inference techniques for diffusion model-based solvers, such those inspired by the continuous time framework for discrete diffusion [12, 105].
References
[1] Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what defer for maximum independent sets. In International Conference on Machine Learning, pages 134-144. PMLR, 2020.
[2] Diogo V Andrade, Mauricio GC Resende, and Renato F Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18(4):525-55) -475555-7,455 2012.
[3] David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver. attps://wwe math. uwaterloo.. ca/tap/concorde. index. .tml,, 2006.
[4] Sanjeev Arora. Polynomial time approximation schemes for euclidean tsp and other geometric problems. In Proceedings of 37th Conference on Foundations of Computer Science, pages 2-11. IEEE, 1996.
[5] Jacob Austin, Daniel Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 14:11981-17993 2021.
[6] Irwan Bello, Hicu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, arXiv preprint arXiv:1611.0961 2016.
[7] Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. Advances in Neural Information Processing Systems, 2022.
[8] Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization. In International Conference on Learning Representations, 2022. URL https://opperreiess net/forum? id=mkOHzddy771.
[9] Xavier Bresson and Thomas Laurent. An experimental study of neural networks for variable graphs. 2018.
[10] Xavier Bresson and Thomas Laurent. The transformer network for the traveling salesman problem. arXiv preprint arXiv:2103.03012 2021.
[11] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877- 1901, 2020.
10

---

[12] Andrew Campbell, Joe Benton, Valentin De Bortoli, Tom Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. In Al- ice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL id-DmI862YAieeY
[13] Huiwen Chang, Han Zhang, Lu Jiang, Ce Liu, and William Freeman. Maskgit: Masked generative image transformer. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 11315-11325, 2022.
[14] Nanxin Chen, Yu Zhang, Heiga Zen, Ron Weiss, Mohammad Norouzi, and William Chan. Wavegrad: Estimating gradients for waveform generation. In International Conference on Learning Representations, 2020.
[15] Nanxin Chen, Yu Zhang, Heiga Zen, Ron J Weiss, Mohammad Norouzi, Najim Dehak, and William Chan. Wavegrad 2: Iterative refinement for text-to- text-to-speech synthesis. arXiv preprint arXiv:2 I06,0600 2021.
[16] Ting Chen, Ruixiang Zhang, and Geoffrey Hinton. Analog bits: Generating discrete data using diffusion models with self coff-condiioninn, arXiv preprint arXiv:2208.042 04202, 2022.
[17] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances Neural Information Processing Systems, 32, 2019.
[18) Jinho Choo, Yeong-Das Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tiemney and Youngjune Gwon. Gimulation-guided heam search for neural combinatorial optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https: /ttpps://opee /ttp///pppeeeeeeeeeeeeeeeeeeeeee net/forum? id=tYAS1Rpys5.
[19] Georges A Croes. A method for solving traveling problems. Operations research, 6 (6):791-812, 1958.
[20] Paulo R d O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, pages 465-480. PMLR, 2020.
[21] Paulo R de O da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-OPT heuristics for the traveling salesman problem via deep reinforcement learning. arXiv preprint arXiv:2004.0 01608, 2020.
[22] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Martinn Rousseau. Learning heuristics for the TSP by policy gradient. In International conference on the integration of constraint programming, artificial intelligence, and operations research, pages 170-181. Springer, 2018.
[23] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 34:8780-8794, 2021.
[24] Sander Dieleman, Laurent Sartran, Arman Roshannai, Nikolay Savinov, Yaroslav Ganin, Pierre Richemond, Arnaud Doucet, Robin Strudel, Chris Dyer, Conor Durkan, et al. Contin- uous diffusion for categorical data. arXiv preprint arXiv:2211. 2022.
[25] Iddo Drori, Anant Kharkar, William R Sickinger, Brandon Kates, Qiang Ma. Suwen Ge, Eden Dolev, Brenda Dietrich, David P Williamson, and Madeleine Udell. Learning solve combinatorial optimization problems on worl-world graphs in linear time. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 19-24. IEEE, 2020.
[26] Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 166): 1960.

---

[27] Zhang Huun Fu, 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. volume 35, pages 7474-7482, 2021.
[28] Simon Geisler, Johanma Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adver- sarial robustness. In International Conference on Learning Representations, 2022. URL https://openrevie
[29] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pages 1263-1272. PMLR, 2017.
[30] Shansan Gong, Mukai Li, Jiangtao Feng. Zhiyong Wu, and LingPeng Kong. Diffuseq: Sequence to sequence text generation with diffusion models, arXiv preprint urXiv:2210.08933, 2022.
[31] Teofilo F Gonzalez. Handbook of approximation algorithms and metaheuristics. Chapman and Hall/CRC, 2007.
[32] Alexandros Graikos, Nikolay Malkin, Nebojsa Jojic, and Dimitris Samaras. Diffusion models allugandd-layy priors. In Thirty-Sixth Conference on Neural Information Processing Systems, 2022. URL httpp:://rxii...tt.////
pdf.f.
[33] Jiatao Gu, James Bradbury, Caiming Xiong, Victor OK Li, and Richard Socher. Non- autoregressive neural machine translation. In International Conference on Learning Rep- resentations, 2018.
[34] Shuyang Gu, Dong Chen, Jianmin Bao, Fang Wen, Bo Zhang, Dongdong Chen, Lu Yuan, and Baining Guo. Vector quantized diffusion model for text-to-image synthesis. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10696-10706, 2022.
[35] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2018.
[36] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[37] Xiaochuang Han, Sachin Kumar, and Yulia Tsvetkov. Ssd-Im: Semi-auttoeerrssivee simplex- based diffusion language model for text generation and modular control. arXiv preprint vrXiv:2200.17432. 2022.
[38] Zhengfu He, Tianxiang Sun, Kuanning Wang, Xuanjing Huang, and Xipeng Qiu. Diffusion- bert: Improving generative masked language models with diffusion models. arXiv preprint arXiv:2211. 150.29991. 2022.
[39] K. Helsgaun. An extension of the Lin- Sermighan-Helsgann TSP solver for constrained traveling salesman and vehicle routing problems. Technical report, Roskilde University. 2017.
[40] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models, Advances in Neural Information Processing Systems, 33:6840-6885 2020.
[41] Jonathan Ho, William Chan, Chitwan Saharia, Jay Whang, Ruiqi Gao, Alexey Gritsenko, Diederik P Kingma, Ben Poole, Mohammad Norouzi, David Fleet, et al. Imagen video: High definition video generation with diffusion models. arXiv preprint 10X:v:2210..2303, 2022.
[42] Jonathan Ho, Chitwan Saharia, William Chan, David J Fleet, Mohammad Norouzi, and Tim Salimans. Cascaded diffusion models for high fidelity image generation. J. Mach. Learn, Res., 23:47-1, 2022.
[43] Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David J Fleet. Video diffusion models. arXiv preprint 2244v.2204.03458, 2022.
12

---

[44] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34:12454-12465, 2021.
[45] Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3d. In International Conference on Machine Learning, pages 8867-8887. PMLR, 2022.
[46] Holger H Hoos and Thomas Stützle, SATLIB: An online resource for research on SAT. Sat, 2000:283-292 2000.
[47] André Hottung and Kevin Tiemny. Neural large neighborhood search for the capacitated vehicle routing problem. arXiv preprint arXiv:1911.09539 2019.
[48] André Hottung, Yeong-Dae Kwon, and Kevin Tiemey. Efficient active search for combinatorial optimization problems. arXiv preprint arXiv:2106.05126, 2021.
[49] Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. International Con- ference on Learning Representations, 2022. URL https:://///// htpphtss///ooeerreeeee www./eeennootteee. id= ar92oEoaBIg.
[50] Capgemini Research Institute. Capgemini research institute, the last-mile delivery chal- lenge, 2023. URL https://wwe capgemini www/wpo-ooottteeoee content/ wowtent/uploads////0/0 /ttpp/llll/1/////0////// Report- Digittl-alll---- aÄs- -As--ast---------aa----aa----a--
pdf.
[51] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448 456. PMLR, 2015.
[52] Daniel D Johnson, Jacob Austin, Rianne van den Berg, and Daniel Tarlow. Beyond in- place corruption: Insertion and deletion in denoising probabilistic models. arXiv preprint arXiv:2107.07675. 2021.
[53] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 01227, 2019.
[54] Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, pages 1-29, 2022.
[55] Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning frame- work for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33:6659-666 2020.
[56] Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion-based generative models. arXiv preprint arXiv:2206.003: 2022.
[57] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[58] Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve NP-hard routing problems. Advances in Neural Information Processing Systems, 34, 2021.
[59] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combinatorial optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openrew
net/forum? htt///oummddd-xrr/o EeviiHrrrvviis
[60] Diederik Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. Advances in neural information processing systems, 34:21696-21777, 2021.
13

---

[61] Thomas N Kipf and Max Welling. Semi-superviee classification with graph convolutional networks. arXiv preprint orXiv:1609.02077 2016.
[62] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional
networks. In International Conference on Learning Reprexentations, 2017. URL https:
//openrviiew mettforrumidd-SJeeee.
[63] Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural informa- tion processing systems, pages 1008-1014, 2000.
[64] Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
[65] Wouter Kool, Herke van Hoof, and Max Welling. Buy REINFORCE samples, get baseline for free! In Deep Reinforcement Learning Meets Structured Prediction, ICLR 2019 Workshop. 2019.
[66] Alex Krizhevsky and Geoff Hinton. Convolutional deep belief networks on cifar-10. Unpub- lished manuscript, 40(7):1 1-9, 2010.
[67] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. arXiv preprint
2020.
[68] Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon. Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Infor- mation Processing Systems, 34, 2021.
[69] Xiang Lisa Li, John Thickstun, Ishaan Gulrajani, Percy Liang, and Tatsunori Hashimoto. Diffusion-LLM improves controllable text generation. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https: /owp//eeeeeeeeeeeeeeeeeeeeeeeeee
[70] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, 31, 2018.
[71] Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the aaveling-salesmee problem. Operations research, 21(2):498-516, 1973.
[72] Jinglin Liu, Chengxi Li. Yi Ren, Feiyang Chen, and Zhou Zhao Diffsinger: Singing voice synthesis via shallow diffusion mechanism. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 1020-11025. 2022.
[73] Luping Liu, Yi Ren, Zhijie Lin, and Zhou Zhao. Pseudo numerical methods for diffusion models manifolds. In International Conference Learning Representations, 2021.
[74] Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Dpm-solver: fast ode solver for diffusion probabilistic model sampling in around 10 steps. arXiv preprint urXiv:2206.00927 2022.
[75] Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Dpm- solver++: Fast solver for guided sampling of diffusion probabilistic models. arXiv preprint arXiv:2211.01095 2022.
[76] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning- based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
[77] Shitong Luo, Yufeng Su, Xingang Peng, Sheng Wang, Jian Peng, and Jianzhu Ma. Antigen- specific antibody design and optimization with diffusion- generative models for protein structures. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URI. URt.https:/oopeneeee /ttp////ppe/.../////////// net/f htt///rrrmiddjSrrr2nnnni
14

---

[78] Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial opti- mization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv: 00991.1146666 2019.
[79] Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang. Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34:1 1096-11 107, 2021.
[80] Cedric Malherbe, Antoine Grosnit, Rasul Tutunov, Haitham Bou Ammar, and Jun Wang. Optimistic tree searches for combinatorial black-box optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https:t..... http::::////ppevieeeeeee nett/forumiiddJJLWWDVV
[81] Chenlin Meng, Yang Song, Jiaming Song, Jiajun Wu, Jun- Yan Zhu, and Stefano Ermon. Sdedit: Image synthesis and editing with stochastic differential equations. arXiv preprint arXiv:2108.0000 2021.
[82] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoguue, Nicolas Somnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13344 2020.
[83] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforce- ment learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[84] Alex Nichol, Prafulla Dhariwal, Aditya Ramesh, Pranav Shyam, Pamela Mishkin, Bob Mc- Grew, Ilya Sutskever, and Mark Chen. Glide: Towards photorealistic image generation and editing with text-guided diffusion models. arXiv preprint 1rXiv:2112.1003 2021.
[85] Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International Conference Machine Learning, pages 8162-8171. PMLR, 2021.
[86] Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics, pages 4474-4484 PMLR, 2020.
[87] Wenbin Ouyang, Yisen Wang. Shaochen Han, Zhejian Jin, and Paul Weng. Improving general- ization of deep reinforcement learning-based tsp solvers. arXiv preprini urXiv:2110.02845 2021.
[88] Christos Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
[89] Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59(11):330--377, 2021.
[90] Bo Peng. Jiahai Wang, and Zizhen Zhang. deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In International Symposium on Intelligence Computation and Applications, pages 636-650. Springer, 2019.
[91] pitney bowes. Pitney bowes parcel shipping index, 2023. URL wwtp:wwwwwbbwwss..tttt. wew.gg-iidxxx.hiee
[92] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. In Advances Neural Information Processing Systems, 2022.
[93] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents, arXiv preprint arXiv:2204.0611 2022.
15

---

[94] Robin Rombach, Andreas Blatimann. Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High-resolution image synthesis with latent diffusion models. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10684-10695, 2022.
[95] Chitwan Saharia, William Chan, Huiwen Chang. Chris Lee, Jonathan Ho, Tim Salimans, David Fleet, and Mohammad Norouzi. Palette: Image-to-imagg diffusion models. In ACM SIGGRAPH 2022 Conference Proceedings, pages 1-10, 2022.
[96] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gontijo Lopes, et al. Photorealistic text-to-image diffusion models with deep language understanding. arXiv preprint arXiv:2205. 1487, 2022.
[97] Paul Shaw. A new local search algorithm providing high quality solutions to vehicle routing problems. APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scotland, UK, 46, 1997.
[98] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587);
484-489, 2016.
[99] Uriel Singer, Adam Polyak, Thomas Hayes, Xi Yin, Jie An, Songyang Zhang, Qiyuan Hu, Harry Yang, Oron Ashual, Oran Gafni, al. Make-a-video: Text-to-video generation without text-video data, arXiv preprint arXiv:2209. 14792, 2022.
[100] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep un- supervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages 2256-2265. PMLR, 2015.
[101] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations, 2021. URL
net/forum?? iid-tt 1g.
[102] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
[103] Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. Advances neural information processing systems, 33:12438- 2020.
[104] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021.
[105] Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous- time discrete diffusion models. arXiv preprint arXiv:2211. 2022.
[106] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017.
[107] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Leurning Represen- lations, 2018
[108] Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 14734, 2022.
[109] Chenguang Wang, Yaodong Yang, Oliver Slumbers, Congying Han, Tiande Guo, Haifeng Zhang, and Jun Wang. game-theoretic approach for improving generalization ability of TSP solvers. arXiv preprint
2021.
16

---

[110] Runzhong Wang. Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang. Jun Zhou, and Xiaokang Yang. bi-level framework for learning to solve combinatorial optimization graphs. arXiv preprint arXiv:2 2021.
[111] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist rein- forcement learning. Machine learning, 8(3):229-22) 1992.
[112] Lemeng Wu, Chengyue Gong, Xingchao Liu, Mao Ye, and Qiang Liu. Diffusion- based molecule generation with informative prior bridges. arXiv preprint arXiv:2209.0008: 2022.
[113] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim, Learning improvement heuristics for solving routing problems.. IEEE transactions on neural networks and learning systems, 2021.
[114] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with em- bedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12042-12049 2021.
[115] Liang Xin, Wen Song. Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining deep learning model with Lin Ain-Kernighan- -eeniigann-Hessaun heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34, 2021.
[116] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL
https://openreviees net/ h/t.ru/ommm ieterummiddrryee id=ryGa6iA5Kmm
[117] Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. Geodiff: A geometric diffusion model for molecular conformation generation. International Conference Learning Representations, 2021.
[118] Dongchao Yang, Jianwei Yu, Helin Wang, Wen Wang, Chao Weng, Yuexian Zou, and Dong Yu. Diffsound: Discrete diffusion model for text-to-sound generation. arXiv preprint 0tt1:2207709988. 2022.
[119] Emre Yolcu and Barnabás Póczos. Learning local search heuristics for boolean satisfiability. In NeurlPS, pages 1990-8001, 2019.
[120] Jiahui Yu, Yuanzhong Xu, Jing Yu Koh, Thang Luong, Gunjan Baid, Zirui Wang, Vijay Vasudevan, Alexander Ku, Yinfei Yang. Burcu Karagol Ayan, al. Scaling autoregressive models for content-rich text-to-image generation. Transactions on Machine Learning Research.
[121] Lijun Yu, Yong Cheng, Kihyuk Sohn, José Lezama, Han Zhang, Huiwen Chang, Alexander G Hauptmann, Ming-Hsuan Yang, Yuan Hao, Irfan Essa, et al. Magvit: Masked generative video transformer. arXiv preprint arXiv:2212.05 199, 2022.
[122] Cong Zhang, Wen Song. Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Chi Xu. Learn- ing to dispatch for job shop scheduling via deep reinforcement learning. arXiv preprint arXiv:2010.12367, 2020.
17

---

A Frequently Asked Questions
A.1 Does DIFUSCO rely on high-quality solutions collected in advance?
DIFUSCO does not require exact optimal solutions to train the diffusion model-based solver. For instance, in TSP-500/1000/10000, we utilize the heuristic solver LKH-3 generate near-optimal solutions, which is nearly fast as the neural solvers themselves (refer to Table 2 for details). Empirically (in 15P-500/1000/10000 (000/00000), DIFUSCO still attains state-of-the-ar performance even when trained on such near-optimal solutions rather than exact optimal ones. The training data sizes are reported in Appendix E.
A.2
This work simply applies discrete diffussin models to combinatorial optimization problems. Could you clarify the significance of this work in the field?
is essential to highlight that our work introduces a novel approach to solving NP-complete problems using graph-based diffusion models. This approach has not been previously explored in the context of No-complete problems, and we believe that the significant improvements in performance over the state-of-the-art on benchmark datasets emphasize the value of our work.
Drawing a parallel to the application of diffusion models in image generation and subsequent extension to videos, our work explores a similar expansion of the scope. While denoising diffusion models have been extensively researched and applied to image generation, DIFUSCO represents the first instance where these models are applied to NP-complete CO problems. Such novelty in problem formulation is fundamental for solving NP-complete problems instead incremental ones from methodological point of view.
The formulation of No-complete problems into discrete {0, 1--ecco space and the use of graph- based denoising diffusion models to generate high-quality solutions make our approach unique. Additionally, we explore diffusion models with Gaussian and Bernoulli noise and introduce an effec- tive inference schedule to improve the generation quality, which further underlines the significance of our work.
In conclusion, we believe that our work makes a significant and novel contribution to the field by introducing new graph-based diffusion framework for solving NP-complete problems. The application of diffusion models, which have been primarily used for image and video generation, to the realm of combinatorial optimization highlights the innovative aspects of our research. We hope that this clarification demonstrates its importance in the field.
A.3 How can DIFUSCO produce diverse multimodal output distribution?
Such ability comes from the characteristics of diffusion models, which are known for generating wide variety of distributions as generative models (like diverse images). A more comprehensive understanding can be found in the related literature, such as DDPM.
A.4
Why is there no demonstration for the time-cost the results shown in Table 1, and why are there some conflicts in the metrics of Length and Gaps?
The time is not reported Table as these baseline methods are evaluated on very different hardware, which makes the runtime comparison not too meaningful. As for the "confficts", the results (both length and optimality gap) of all the baseline methods are directly copied from previous papers. The "conflicts" may be caused by rounding issues when reporting numerical numbers in previous papers, as our best guess.
The -0.01 gap in DIFUSCO is because the Concorde solver only accepts integer coordinates as the inputs, which may lead it to produce inaccurate non-optimal solutions due to rounding issues.
A.5 How can we effectively evaluate the usefulness of the proposed method when the training time is also a consideration?
important to clarify that in the context of neural combinatorial optimization solvers and general machine learning research, the primary focus is typically inference time. This is because, after
18

---

0.8
0.8
7.4
2.8
0.4
0.15
0.089
7.7
67
0.18
0.038
0.388
# Samples
5.4
0.72
0.011
0.005
0.6
4.2
2.6
0.033
0.0028
0.6
64
0.016
64
144
0.0027
0.4
256
0.022
0.2
256
0.52
0.2
233
-0.0
1024
0.17
-0.0
20
Diffusion steps
Diffusion steps
(b)
Figure 4: The performance Gap (%) of continuous diffusion (a) and discrete diffusion (b) models on TSP-50 with different diffusion steps and number of samples. (e): The results reported with greedy decnding without 2-opt post-processing.
a.cocs
6016
a.00d
0.14
3.23
12P
0.00076 01DCH COOGB COASEDOOCU...COEE
60332
C02S 6 CO1S DOCT4 6.011 0013
0.22
0.099
D/CCD 0022 0002 08028 0.007
0.003
0.6090
C0R2
00042
a Samples
132k 256 64 16
0:113
0041
6.15
63
Sumples
AIE091 6085-0 6974 nATEA
Sumples
0.00X
0.50
0017
2.15
01:
23
0.56
0/038
0.033
003
0:98
0.03
607
045
0.00
0:13
013
20n>
1324 2Mh
23
0.22
10
1.8
06
13
30
Diffusion steps
Diffusion
Diffusion
(b)
Figure 5: The inference per-instance run-time (sec) diffusion models on TSP-50, where the total run-time decomposed to neural network (a) + greedy decoding (b) + 2-opt (c).
the model has been trained, can be applied to virtually unlimited number of unseen examples (graphs) during deployment. On the other hand, the training time is often considered negligible in comparative evaluations, partly due to the fact that traditional NCP solvers are hand-crafted instead and partly because the training cost for learnable models is out weighted by the benefits of their numerous applications.
of
A.5.1
Can you name a real application that has many test instances and require such a model?
is worth noting that the routing problem a fundamental and perhaps the most important combina- torial optimization problem in real-world scenarios. One example is the food delivery problem, where a pizza shop is planning to deliver pizzas to four different addresses and then return to the store. The routing problem has significant implications for industries such retail, quick service restaurants (QSRs), consumer packaged goods (CPG), and manufacturing. In 2020, parcel shipping exceeded 131 billion in volume globally and is projected more than double by 2026 [91]. With the changing economic and geopolitical landscape within the transport and logistics industry. Last Mile Delivery (LMD) has become the most expensive portion of the logistics fulfillment chain, representing over 41% % of overall supply chain costs [50].
B Extended Related Work
Autoregressive Constructive Solvers Since Bello et al. [6] proposed the first autoregressive CO solver, more advanced models have been developed the years since [22, 64, 90, 25, 68], including better network backbones [106, 64, 9I), more advanced deep reinforcement learning algorithms [57, 78, 65, 67, 87, 114, 109, 18], improved training strategies [59, 7], and for wider range of NPC problems such as Capacitated Vehicle Routing Problem (CVRP) [83]. Job Shop Scheduling Problem
(ISSP) [122, 89], Maximal Independent Set (MIS) problem [57, 1, 80, 92], and boolean satisfiability
problem (SAT) [119].
19

---

TSP-0
0.88
5B
24
Training Data
Traininu Data
TSP 100
13
15
12
10
TSP 500
16
10
11
67
1.
TSP 000
18
10
TSP-10000
18
1014
10
T3R50
7SP
TSP
10000
TSP30
TSP
1010
TSP-10000 1000
T3P
Evaluation Data
Evaluation Data
(b)
Figure 6: Generalization tests of discrete DIFUSCO trained and evaluated on TSP problems across various scales. The results are reported with (a) and without (b) 2-opt post poose-rocsssin..
Table 4: Comparing discrete diffusion and continuous diffusion on TSP-100 with various diffusion steps and numbers of parallel sampling. cosine schedule used for fast sampling.
DuvUSIoN Sters
NSAMPLE
DISCRETE DIFFSIOON (Gap%)
w/ 20PT
w/o 20PT
CONTINHOUS DIFFUSION (Gap%)
w/ 2OPT
w/o 20FT
PER-INSTANCR RUNTIME (see)
NN
GD
2-OPT
0,23869
1.45374
1.46146
7.66379
0.50633
0.00171
0.00210
100
0,23366
1.48161
1.32573
7.02117
1.00762
0,00170
0.00207
1.65264
1.52401
10
16
-0.01870
0.00519
0.13015
0.54983
1.12550
0.02581
0.02228
16
-0.02322
-0,0099
0.09407
0.30712
5.63712
0.02525
0.02037
Improvement Heuristics Solvers Unlike construction heuristics, DRL-based improvement heuris- ties solvers neural networks iteratively enhance the quality of the current solution until the computational budget is exhausted. Such DRL-based improvement heuristics methods are usu- ally inspired by classical local search algorithms such as 2-opt [19] and the large neighborhood search (LNS) [97], and have been demonstrated with outstanding results by many previous works [17, 47, 21, 20, 115, 79, 113, 76, 10, 58, 49].
Improvement heuristics methods, while showing superior performance compared to construction heuristics methods, come at the cost of increased computational time, often requiring thousands of actions even for small-scale problems with hundreds of nodes [20, 110]. This due to the sequential application of local operations, such as 2-opt, on existing solutions, resulting in bottleneck for latency. On the other hand, DIFUSCO has the advantage of denoising all variables in parallel, which leads to reduction in the number of network evaluations required.
Continuous Diffusion Models Diffusion models were first proposed by Sohl-Dickstein al. [100] and recently achieved impressive success various tasks, such as high-resolution image synthesis [23, 42], image editing [81, 95], text-lo-image generation [84, 96, 94, 93, 34], waveform generation [14, 15, 72]. video generation [43, 41, 99], and molecule generation [117, 45, 112].
Recent works have also drawn connections to stochastic differential equations (SDEs) [104] and ordinary differential equations (ODEs) [101] in continuous time framework. leading to improved sampling algorithms by solving discretized SDEs/ODES with higher-order solvers [73, 75, 74] or implicit diffusion [101].
C Additional Results
Discrete Diffusion v.s. Continuous Diffusion on TSP-100 We also compare discrete diffusion and continuous diffusion on the TSP-100 benchmark and report the results in Tab. 4. We can see that on TSP-100, discrete diffusion models still consistently outperform their continuous counterparts in various settings.
More Diffusion Steps v.s. More Sampling (w/o 2-opt) Fig. report the results of continuous diffusion and discrete diffusion with various diffusion steps and numbers of parallel sampling, without using 2-opt post-processing. The cosine denoising schedule is used for fast inference. Again, we find that discrete diffusion outperforms continuous diffusion across various settings.
20

---

Table 5: Comparison to DIMES w/ 2-opt
TSP-500
TSP-1000
TSP--10000
Length
Gap
Length
Gap
Length
Gap
DIMES
21+S+2OPT
17.63
6.52%
24.81
7.31 %
77.18
7.54%
DIMES
17.30
4.53%
24.32
5.19%
75.94
5.81%
DIFUSCO
SL+G+20PT
16.80
1.49%
23.56
1.90%
73.99
3.10%
DIFUSCO
SL+S+20PT
16.65
0.57%
23.45
1.43%
73.89
2.95%
Table 6: Solution quality and computation time for leaming- based methods using models trained synthetic data (all the other baselines are trained with TSP-100) and evaluated on TSPLIB instances with 50 to 200 nodes and 2D Fuclidean distances. Other haseline results are taken from Hudson et al. [49].
Method
Kool et al.
Joshi et al.
O. da Costa et al.
Hudson et al.
Ours (TSP-50)
Ours (TSP-100)
Instance
Time (s) Gap (%)
Time (s) Gap (%)
Time (s) Gap (%)
Time (s) Gap (%)
Time (s) Gap (%)
Time (s) Gap (%)
ci151
0.125
1.628
3.026
8,339
28.051
0.067
10.074
0.000
0.482
0.000
0,519
0.117
herlin52
0.129
4.169
3.068
33.225
31.874
0.449
10.103
0.142
0.527
0.000
0.526
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
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
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
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
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
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
kroC100
0.352
0.972
5,641
35.506
34.333
0,349
10.172
1.571
1.199
1.712
L.168
0,000
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
kroE100
0.352
1.470
5.650
26.589
34.475
1.32
10.270
1.216
1,208
0.274
1.197
0.274
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
eil101
0.359
2.994
5,790
26.701
23.842
0.387
10,276
0.201
1.222
1,215
0.000
lin105
0.380
1.739
5.938
34,902
39.517
18677
10.330
0.606
1.321
0.040
1,280
0.000
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
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
bier127
0.522
5.908
7.242
45.561 56.61
39.029
3.044
10,260
1.948
1.938
1.011
1.915
0.366
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
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
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
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
kroA150
0.695
3.784
8.450
45.411
39.
0.724
10.331
2,984
2.617
3.753
2.601
0.000
k5oB150
0.696
2.437
8,573
56.745
29.005
0.886
10.018
3.258
2.626
1.839
2.592
0.067
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
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
rai195
1.114
6,893
11.236
24.968
34.425
0,743
12.295
1.666
4,400
1.540
4.428
0.767
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
kroA220
1.150
7.106
11.702
40.885
33.832
1.441
11.088
2.029
4.710
6.187
4.686
0.065
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
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
Besides, we find that without the 2-opt post-processing, performing more diffussoon iterations much more effective than sampling more solutions, even when the former uses less computation. For example, 20 (diffusion steps) x (samples) not only significantly outperforms (diffusion steps) x 1024 (samples), but also has 18.5x less runtime.
Runtime Analysis We report the decomposed runtime (neural network greedy decoding + 22-opt for diffusion models on TSP-50 in Fig. 5. We can see that while neural network execution takes the majority of total runtime, 2-opt also takes a non-negligible portion of the runtime, especially when only few diffusion steps (like 1 or 2) are used.
Generalization Tests (w/o 2opt) without 2-opt post-processing in F (b).
We also report the generalization tests of discrete DIFUSCO
Comparison to DIMES w/ 2opt We compare DIMES with 2-opt to DIFUSCO in Tab. 5. We can see that while 2-opt can further improve the performance of DIMES on large-scale TPS problem instances, there is still a significant gap between DIEMS and DIFUSCO when both are equipped with 2-opt post-processing.
21

---

Table 7: Results of DIFUSCO with multiple samples for MCTS
TSP-500
TSP-1000
TSP-
100000000
Length
Gap
Length
Gap
Length
Gap
PREVIOUS SOTA
16.84
1.76%
23.69
2.46%
74.06
3.19%
DIFUSCO 1XMCTS
16.64
0.46%
23.39
1.17%
73.62
2.58%
DIFUSCO 2XMCTS
16.57
0.09%
23.32
0.56%
73.60
2.55%
DIFUSCO 4XMCTS
16.56
0.02%
23.30
0.46%
73.54
2.48%
Generalization to Real-World Instances In many cases, there might not be enough real-world problem instances available to train a model. As result, the model needs be trained using synthetically generated data. Hence, it becomes crucial to assess the effectiveness of transferring knowledge from the simulated environment the real world. we evaluated the DIFUSCO models trained on TSP-50 and TSP-100 on TSPLib graphs with 50-200 nodes and comparison to other methods (trained TSP-100) [64, 53, 20, 49] is shown in Tab.
We can see that DIFUSCO achieves significant improvements over other baselines on the real-world TSPLIB data (0.29% gap v.s. 1.48% in the best baseline). Besides, DIFUSCO also shows strong generalization ability across problem scales, where DIFUSCO trained on TSP-50 data achieves competitive performance with the best baseline Hudson et al. [49] trained TSP-100.
MCTS with Multiple Difflusion Samples One may wonder what if DIFUSCO with MCTS is allowed have more than one sample. To evaluate the impact of using multiple samples in DIFUSCO with MCTS, we conducted experiments with 1x, 2x, and 4x greedy heatmap generation (50 diffusion steps) combined with MCTS using different random seeds, and report the results in Tab. 7.
Our findings show that DIFUSCO's performance significantly improves when MCTS decoding is applied to diverse heatmaps. We would like to highlight that the diverse heatmap MCTS decoding approach unique to diffusion model-based neural solvers like DIFUSCO, as previous methods (e.g., Att-GCN and DIMES) that employ MCTS only yield unimodal distribution. While it true that using 2x or 4x MCTS decoding would increase the runtime of DIFUSCO, we believe there is a similar exploitation versus exploration trade-off between MCTS time and MCTS seeds, akin the trade-off between diffusion steps and the number of samples demonstrated in Figure of our paper.
D Discussion on the {0, 1 Vector Space of CO Problems
The design of the f0, 1 vector space can also represent con-grapph-bet baspdd NP-complete combinato- rial optimization problems. For example, on the more general Mixed Integer Programming (MIP) problem, we can let X, be 0/1 indication set of all extended variables*. cost(-) can be defined as linear/quadratic function of x, and valid(.) a function validating all linear/quadratic constraints, bound constraints, and integrality constraints.
E
Additional Experiment Details
Metrics: TSP For TSP, Length is defined as the average length of the system- preeeetedeeeeed tour for each test-set instance. Gap is the average of the relative decrease in performance compared to baseline method. Time is the total clock time required to generate solutions for all test instances, and presented in seconds (s), minutes (m), hours (h).
Metrics: MIS For MIS. Size (the larger, the better) is the average size of the gystem-predieet maximal independent set for each test-set graph, Gap and Time are defined similarly in the TSP case.
Hardware All the methods trained with 8x NVIDIA Tesla V100 Volta GPUs and evaluated on a single NVIDIA Tesla V100 Volta GPU, with 40x Intel(R) Xeon(R) Gold 6248 CPUs 2.50GHz.
For an integer variable that can be assigned values from finite set with cardinality card(z), any target value can be represented sequence of [log, (card(z))) bits [82, 16).
22

---

Random Seeds Since the diffusion models can generate an arbitrary sample from its distribution even with the greedy decoding scheme, we report the averaged results across different random seeds when reporting all results.
Training Details All DIFUSCO models are trained with a cosine learning rate schedule starting from 2e-4 and ending at O.
TSP-50: We use 1502000 random instances and train DIFUSCO for 50 epochs with a batch size of
512.
TSP-100: We use 1502000 random instances and train DIFUSCO for 50 epochs with a batch size
of 256.
TSP-500: We use 128000 random instances and train DIFUSCO for 50 epochs with a batch size of
64. We also apply curriculum learning and initialize the model from the TSP-100 checkpoint.
TSP-1000: We use 64000 random instances and train DIFUSCO for 50 epochs with a batch size of
64. We also apply curriculum learning and initialize the model from the TSP-100 checkpoint.
TSP-10000: We use 6400 random instances and train DIFUSCO for 50 epochs with a batch size of
8. We also apply curriculum learning and initialize the model from the TSP-500 checkpoint.
SATLIB: We use the training split of 49500 examples from [46, 92] and train DIFUSCO for 50 epochs with batch size of 128.
FER-1700-800): We use 16384) random instances and train DIFUSCO for 50 epochs with a hatch size of 32.
Decoding Strategies
Greedy Decoding We use simple greedy decoding scheme for diffusion models, where we sample one solution from the learned distribution pe (xn). We compare this scheme with other autoregressive constructive solvers that also use greedy decoding.
Sampling Following Kool al. [64], also sampling scheme where sample multiple solutions in parallel (i.e., each diffusion model starts with a different noise xT) and report the best one.
Monte Carlo Tree Search For the TSP task, we adopt a more advanced reinforcement learning- based search approach, i.c., Monte Carlo search (MCTS), find high-quality solutions. MCTS, we sample k-opt transformation actions guided by the heatmap generated by the diffusion model to improve the current solutions. The MCTS repeats the simulation, selection, and back soee-propggttion steps until no improving actions are found in the sampling pool. For more details, please refer to [27].
G Fast Inference for Continuous and Discrete Diffusion Models
We first describe the denoising diffusion implicit models (DDIMs) [101] algorithm for accelerating inference for continuous diffusion models.
Formally, consider the forward process defined not on all the latent variables XI:7, but on a subset (x.,...., XTM where is increasing sub-sequence of [1...., 7) with length M, x, 1 and Xyx =.
For continuous diffusion, the marginal can still be defined as:
q(x+,1x0 = N(x,) / ār, Xo, (1 ār. I)
(9)
And it's (deterministic) posterior is defined by:
- ?n. ( (x,, (xn- 11-111 + v an,, (,),
q(x+,-1 1x,,, Xo) N(x
(10)
Cn,
where ह.. = (X7; xo) TT the (predicted) diffusion noise.
Next, describe its analogy in the discrete domain, which is first proposed by Austin et al. [5].
23

---

Figure 7: Qualitative illustration of how diffusion steps affect the generation quality of continuous diffusion models. The results are reported without any post-pros poosesrocssing. Continuous DIFUSCO with 50 (first row), 20 (second row), (third row), (last row) diffusion steps in cosine schedule are shown.
For discrete diffusion, the marginal can still be defined
((x,,
Cat (xr, ip Xo x1Qr.).
(11)
while the posterior becomes:
g(XT, Xx. (x)))(Xx,, (x0)
q( 1x,, xo)
a(x,; (x0)
(12)
Xr. Q
3 x. Q T
Cat Xr XT-1ip-
Xo x
where Q Qu+1 ... Q
H Experiment Baselines
TSP-50/100 We evaluate DIFUSCO on TSP-50 and TSP-100 against 10 baselines, which belong to two categories: traditional Operations Research (OR) methods and learning- based methods.
Traditional OR methods include Concorde [3], an exact solver, and 2-opt [7 I. heuristic method.
Learning-baat based methods include AM [64], GCN [53], Transformer [10], POMO [67], Sym- NCO[59], DPDP [79], Image Diffusion [32], and MDAM [114]. These are the state-of-the methods in recent benchmark studies.
TSP-500/100//0000 We compare DIFUSCO on large-scale TSP problems with 9 baseline methods, which fall into two categories: traditional Operations Research (OR) methods and learning-base based methods.
Traditional OR methods include Concorde [3] and Gurobi [35], which are exact solvers, and LKH-3 [39], which is a strong heuristic solver. We use two settings for LKH-3: (i) defaulr: 10000 trials (the default configuration of LKH-3); (ii) less trials: 500 trials for TSP-500/1000 and 250 trials for 100-10000. We also include Farthest Insertion, a simple heuristic method, as a baseline. Learning- methods include EAN [22], AM [64], GCN [53], POMO+EAS [67, 48), Att-GCN
[27], and DIMES [92]. These are the state-of-the-art methods in recent benchmark studies. They

---

Figure Qualitative illustration of how diffusion steps affect generation quality of discrete diffusion models. The results are reported without any post processing. Discrete DIFUSCO with 50 (first row), 20 (second row), 10 (third row), and (last row) diffusion steps in cosine schedule are shown.
Figure Qualitative illustration of how diffusion schedules affect generation quality continuous diffusion models. The results are reported without any post-processing. Continuous DIFUSCO with linear schedule (first row) and cosine schedule (second row) with 20 diffusion steps are shown.
can be further divided into reinforcement learning (RL) and supervised learning (SL.) methods. Some RI. methods can also use an Active Search (AS) stage [6] to fine-tune each instance. We take the results the baselines from Fu et al. [27] and Qiu al. [92]. Note that except for Au-GCN and DIMES, the baselines are trained small graphs and tested on large graphs.
MIS For MIS, we compare DIFUSCO with other MIS solvers on the same test sets, including two traditional OR methods (i.e., Gurobi and KaMIS) and four learning-based methods. Gurobi solves MIS as an integer linear program, while KaMIS soaming-basees methods can be divided into the reinforcement learning (RL) category, ie., LwD (1]) and DIMES [92], and the supervised learning (SL) category, i.c., Intel [70] and DGL [8].
heuristics solver for MIS. The four
25

---

Figure 10: Qualitative illustration of how diffusion schedules affect the generation quality of discrete diffusion models. The results are reported without any past-pracessing. Diserete DIFUSCO with linear schedule (first row) and cosine schedule (second row) with 20 diffusion steps are shown.
Figure 11: Qualitative illustration of discrete DIFUSCO TSP-50, TSP-100 and TSP-500 with 50 diffusion steps and cosine schedule.
Figure Success (left) and failure (right) examples on TSP-100 100, where the latter fails form a single tour that visits each node exactly once. The results are reported without any post-processing
26


Reviews:
[{"review_id": "JTuGU3PPNt", "reviewer": "Reviewer_b1y4", "summary": "This paper investigates using diffusion models to solve combinatorial optimization problems. The authors propose two alternative methods to adapt diffusion models to this task: (1) a discrete diffusion model with Bernoulli noise, and (2) a more standard continuous diffusion model, where post-processing is needed to produce a discrete prediction. ", "questions": "1.\tSolution times are missing from Table 1.", "limitations": "Not presented, but not particularly relevant.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.\tThe paper is well-written. My background is more in combinatorial optimization, and I am familiar with standard diffusion models. The authors very clearly explain the presented methods, which is quite impressive given the space limitations. \n2.\tThe methodologies appear sound, and the design decisions are presented with accompanying rationale.\n3.\tThe computational experiments are very thorough and show the proposed algorithms give high quality solutions in low computational times. The results are discussed clearly.\n", "weaknesses": "1.\tThe feasibility of a solution is only treated as a Boolean (zero or infinity in eq. 1). This removes information that could be given to the solver regarding how close to feasible a particular solution is. \n2.\tIt is slightly that most implementation details (sections 3.3, 3.4, etc.) are in the appendix. It would be nice to give some summaries in the main text, especially of key components such as decoding strategies, but I understand this may not be possible given the space limitations.\n3.\tThe solution generalizability is slightly limited. In combinatorial optimization, the best solution strategy often changes depending on the graph (problem) sparsity. It would be a nice result to investigate sensitivity to problem sparsity for TS or pairwise connection probability for MIS.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time and effort the reviewer put into examining our work and providing valuable feedback. We would like to address your concerns as follows:\n\n> The feasibility of a solution is only treated as a Boolean.\n\nIn our current design, feasibility is treated as a binary-valued variable. This is because assigning a continuous score to represent the feasibility of a solution for complex CO problems like TSP remains an open challenge in the field and is beyond our current focus. However, we agree with the reviewer about the potential benefits of such a treatment (using continuous scores), and further investigation on that topic is a meaningful direction.\n\n> Most implementation details are in the appendix.\n\nWe are grateful for your understanding regarding the space limitations. In the revised version of our paper (with an additional page), we aim to provide more summary-level insights into key components such as decoding strategies within the main text.\n\n> Solution generalizability.\n\nThank you for pointing out this aspect. Please notice that in Figure 3 of our paper, we explored the solution generalizability across different scales and levels of sparsity. We tested our model on real-world TSPLIB graphs, and the results are presented in Table 3 in the Appendix. We hope those are satisfactory for this concern.\n\n> Solution times are missing from Table 1.\n\nWe appreciate your attention to this detail. Please refer to Appendix B.4 in the Frequently Asked Questions section, where we have addressed this issue. In short, the runtime may vary significantly based on hardware configuration and other factors, hence was not included in Table 1.\n"}, {"review_id": "hXTWl4u4wb", "reviewer": "Reviewer_6WFF", "summary": "This paper proposes a new, non-autoregressive, approach to Neural Combinatorial Optimization. As in similar non-autoregressive NCO works, a heat map characterizing the likelihood of a node being part of a solution is generated. The novelty is in the use of a generative model based on diffusion, trained in a supervised way on a sample of problem instances with pre-computed solutions as ground-truth. Two standard variants of diffusion, discrete and continuous, are proposed and experimented, as well as a (standard) trick to speed up test time diffusion. Performance comparisons with a number of NCO baselines are provided, both when test and training data are from the same distribution and when test instances are an order of magnitude larger than the training ones. The approach is tested on two distinct CO problems: TSP and MIS.\n", "questions": "1. Could the authors motivate the formula of line 211 to rank the edges. Is it likely to apply to other CO problems beyond TSP?\n\n1. In Table 1, how is the optimality gap computed exactly? The reported value of -0.01% implies that the solutions are better than the optimal solutions returned by Concorde.\n ", "limitations": "Technical limitations are not explicitly mentioned. Societal impact is not discussed either, but none is apparent, beyond the non-specific impact due to being part of AI research.\n", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a novel diffusion approach for CO, that nicely extends a previous work that was based on image diffusion [22], to better represent the generation process for CO problem solving\n1. The resulting proposal is fairly original, clear, and of good quality. \n1. The fact that two distinct problems can be addressed by the same architecture is a favorable indicator of the breadth of the method.\n1. The comparison with prior work is fairly extensive.\n\n", "weaknesses": "1. The performance on large TSP instances seems to significantly rely on the 2-opt heuristic. Indeed the addition of 2-opt allows to gain about one order of magnitude in the results of DIFUSCO: Table 2 -- e.g. for TSP10000, the opt gap drops from more than 30% with a greedy or sampling strategy to about 3% after applying a 2-opt.\n1. In general the use of 2-opt in the greedy decoding (line 242) considerably biases the results of Table 2. The performance of any of the compared models would likely also be boosted if the same 2-opt were applied at the end.\n1. Autoregressive models are criticized for the \"quadratic complexity\" in their attention mechanism (line 83). One (standard) way to mitigate it is by limiting a priori (using a mask) the number of tokens allowed to influence a token. DIFUSCO is presented as a solution to this complexity bottleneck, but it actually faces the same problem in another form and uses a similar solution (Sec 4.1, paragraph \"Graph sparsification\", line 238).\n1. Section 3.2 and Eqs. (4)-(8) are essentially a copycat of the cited sources, in particular [5,12,28]. It is too detailed for cursory reading, but not detailed enough to really understand without going back to the source. A Bayesian network diagram specifying the class of conditional probability of each variable could be more clear.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our sincere gratitude to the reviewer for providing us with valuable insights on our paper. We would like to address your concerns as follows:\n\n> The performance on large TSP instances seems to significantly rely on the 2-opt heuristic\n\nWe value your suggestion on the application of the 2-opt heuristic. We'd like to note that we have included results with 2-opt post-processing for both DIFUSCO and DIMES in Table 2 of Appendix D: Additional Results. The results indicate that DIFUSCO continues to outperform DIMES, even when 2-OPT is applied.\n\n> About the quadratic complexity of autoregressive models\n\nWe would like to point out that there is no evidence in the neural CO literature suggesting that autoregressive models can work well with a limited context window.  Thus, the quadratic complexity is generically true for those models. Furthermore. their autoregressive generation nature slows down the inference, as supported by the literature on non-autoregressive sequence generation [1, 2].\n\n> Section 3.2 and Eqs. (4)-(8) are too detailed for cursory reading, but not detailed enough to really understand. A Bayesian network diagram could be more clear.\n\nOur intent with the section in question was to provide a detailed yet concise description of the diffusion models. As noted by Reviewer b1y4, \"The authors very clearly explain the presented methods, which is quite impressive given the space limitations.\" Our writing logic follows this structure:\n\n1. VAE (Bayesian) interpretation of diffusion models\n2. Marginal distribution, posterior, and predicted posterior of discrete diffusion\n3. Marginal distribution, posterior, and predicted posterior of continuous diffusion for discrete data\n\n> Could the authors motivate the formula of line 211 to rank the edges.\n\nThe formula we used to rank the edges is taken directly from previous work [3] in order to maintain a fair comparison. Our interpretation of this formula from [3] is that it tries to convert a weighted directed graph into a weighted undirected graph with a distance heuristic.\n\n> In Table 1, how is the optimality gap computed exactly?\n\nPlease refer to Appendix B.4 in the Frequently Asked Questions section for a detailed explanation of how the optimality gap was calculated.\n\n---\n\n[1]: Non-Autoregressive Neural Machine Translation\n\n[2]: Step-unrolled Denoising Autoencoders\n\n[3]: Diffusion models as plug-and-play priors\n"}, {"review_id": "pgi5joyEti", "reviewer": "Reviewer_NgPq", "summary": "The paper, \"DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization,\" introduces a novel methodology for solving NP-Complete combinatorial optimization problems using graph-based diffusion models, named DIFUSCO. By formulating each NP-Complete problem as a {0, 1}-valued vector with N variables that represent node or edge selection in candidate solutions, and employing a message passing-based graph neural network for instance graph encoding and variable denoising, DIFUSCO addresses the limitations of existing solution generation methods. Specifically, it performs parallel inference with fewer denoising steps, models a multimodal distribution via iterative refinements, and uses efficient, stable supervised denoising for training. The authors show DIFUSCO's superior performance over previous probabilistic solvers for two NP-complete problems, the Traveling Salesman Problem and Maximal Independent Set, using benchmark datasets.", "questions": "see the weakness", "limitations": "N/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Novel Approach: The paper introduces DIFUSCO, a novel approach that combines discrete diffusion models with improved fast unfolding of communities for combinatorial optimization problems. This new methodology could potentially open up new research directions in the field.\n\nThorough Experiments: The authors have conducted comprehensive experiments to validate the performance of DIFUSCO, considering different model configurations and problem scales. The experiments and the comparison with existing methods are rigorous and well-documented.\n\nBalancing Exploration and Exploitation: The authors consider the trade-off between the number of diffusion steps and the number of samples, which is a critical aspect in the field of optimization.", "weaknesses": "Computational results: the numerical results on the benchmark problems don't show very significant improvement. The traditional heuristic method still performs better.\n\nComplexity: The DIFUSCO model and its components, such as the discrete diffusion and the unfolding of communities, can be quite complex. This might make it difficult for some practitioners to fully understand and implement the method.\n\nDependency on External Solvers: The model relies on external solvers (like Concorde and LKH-3) for generating and labeling training instances, which might limit its applicability in settings where these solvers are not available or not preferred.\n\nLimited Benchmark Problems: While the TSP is a widely used benchmark, it would be helpful to see how DIFUSCO performs on other combinatorial optimization problems to demonstrate its generality.\n\nComputationally Expensive: The method seems to require substantial computational resources, especially for large-scale problems, which could limit its practical application in resource-constrained settings.\n\nLack of Analysis on Hyperparameters: There seems to be a limited discussion about how different hyperparameters, such as the number of diffusion steps or the noise schedule, affect performance. Some more insights into these aspects would enhance the utility of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer NgPq for their time and feedback on our work. Let's address your concerns:\n\n> The traditional heuristic method still performs better.\n\nIt's critical to highlight that our proposed method, in its simplicity, surpasses other neural solvers consistently. To date, there has been no singular neural solver able to robustly outperform heuristic solvers across the board, which sets a realistic benchmark for performance expectations.\n\n> The diffusion models are quite complex\n\nWe would like to argue that diffusion models present an elegant probabilistic framework. With their proven success in other domains like image generation, we are proud to show its applicability and success in solving NP-complete problems in this paper, just as pointed out by reviewer WFYx and others.  We do believe that such cutting-edge machine learning algorithms can be mastered by ML practitioners. Our open-source code should further facilitate the understanding and adoption of our methodology.\n\n> The model relies on external solvers (like Concorde and LKH-3)\n\nWe have discussed this in Appendix B.1 of the Frequently Asked Questions section. We acknowledge the potential limitation where external solvers may not be available or preferred. We would be more than willing to discuss such issues for concrete cases when they occur. However, to our knowledge so far, we haven't encountered such situations.\n\n> About more Benchmark Problems\n\nWe would like to cite the comments by reviewer WFTx: “It is extremely solid study in all regards.  .. The experiments are impressive in their breadth.”  We truly appreciate such an understanding.\n\nOn the other hand, we must point out that solving all the NP-complete problems in a single paper is not realistic and has not been the reality in the literature of both combinatorial optimization and machine learning. We focus on the TSP and MIS problems because they are adequately representative of edge-based and node-based NP-complete CO problems, respectively, and have been commonly studied by the machine learning community for neural solvers on NP-complete problems.\n\n> It could limit its practical application in resource-constrained settings.\n\nWe would argue that large-scale neural network models have been already successfully applied to many real-world problems, as the most impressive evidence for the success of AI in the past ten years.  There is no reason for us to believe that diffusion models would be an exception. In fact, one of the advantages of neural diffusion models is their capability to scale, as parallel computing is naturally suitable for diffusion models.\n\n> Lack of Analysis on Hyperparameters:\n\nPlease find our detailed analysis in Figure 2 and on lines 260 - 264. Please let us know if there are specific aspects you feel overlooked.\n\n> About \"unfolding of communities\" in your summary of our approach\n\nWould you kindly clarify what you mean by this phrase and why it is relevant to our paper?"}, {"review_id": "XKdJwxClRj", "reviewer": "Reviewer_WFYx", "summary": "This paper proposes and evaluates the use of diffusion models for solving combinatorial optimization problems on graphs.\n\nThe goal is to construct a probability distribution on the solution space that puts weight on high-quality solutions.\nFirst, a dataset of optimal or near-optimal solutions is generated offline with a problem-specific solver.\nThen, a diffusion model is trained in a supervised manner to maximize the likelihood of these solutions.\nFinally, during inference, new solutions are generated from white noise, and put through a post-processing step to ensure feasibility.\n\nSince many combinatorial problems exhibit a graphical structure, the diffusion model is based on a message-passing graph neural network.\nTo handle binary vectors, both discrete and continuous diffusion schemes are explored. \nAn accelerated inference scheme is suggested, along with several solution decoding and improvement heuristics. \n\nAn extensive set of benchmarks underlines the efficiency of the method compared to numerous alternatives from the state of the art.", "questions": "L49: Why are non-autoregressive models limited in expressiveness?\n\nL75: For symmetry maybe you could include related work on the third avenue from the state of the art, namely iterative improvement methods?\n\nL83: Do all best-performing methods use attention nowadays?\n\nL130: Would some form of regularization help in the loss?\n\nL182: The justification of your choice of network is a bit vague, can you elaborate?\n\nL236: Is sparsification done before or after exact solving with Concorde / LKH?\n\nL244: I feel like tour length and drop are redundant, even though the averaging over instances makes them different. Why include both? Also, the combinatorial optimization world usually prefers \"(optimality) gap\" in terms of nomenclature.\n\nL279 (Table 2): If the runtimes are not comparable, why include them?\n\nL321: Can you elaborate on the inductive bias of your architecture for ER graphs?\n\nAppendix L40: If the runtime is not meaningful in Table 1, why report it in Table 2?\n\nAppendix L220: Which benchmark studies are you referring to?", "limitations": "Limitations are well discussed in the paper.\n\nSocietal impact is irrelevant.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "### Originality\n\nThe main innovation here is the adaptation of diffusion models from image generation to combinatorial optimization.\nIt comes with a shift from convolutional to message-passing neural architectures, as well as other design questions like choosing the best type of noise process.\nThe combination of these known ideas is more than sufficient in terms of novelty.\n\n### Quality\n\nIt is an extremely solid study in all regards.\nThe new methods are carefully justified and well-situated with respect to previous work.\nThe experiments are impressive in their breadth, and they do highlight the performance and promise of graph-based diffusion models.\n\n### Clarity\n\nI really enjoyed reading this paper.\nThe authors are clear and honest, they do not resort to useless mathematical details to obfuscate their main contributions.\nThe appendix is very thoughtfully designed, especially the FAQ section at the beginning which underlines the main motivations.\n\n### Significance\n\nThe change of paradigm from images to graphs in diffusion models is a great foundation for future work.\nWhile it is not a huge theoretical leap, it takes some good ideas and craftsmanship to get it right, and that's what the authors showed.\nI am excited to see what comes out of it.", "weaknesses": "### Originality\n\nn.a.\n\n### Quality\n\nn.a.\n\n### Clarity\n\nIt would help to specify why distribution multimodality is so important for solution generation, since that seems to be a main argument in favor of diffusion models.\n\n### Significance\n\nThe main limitation that I see is that this approach requires access to a dataset of high-quality solution, which is costly to generate.\nI think the method also generalizes to unsupervised learning without much additional headache, maybe that is worth discussing as a perspective?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable insights and constructive feedback on our paper. Below we address your comments and suggestions:\n\n> Distribution Multimodality and Non-autoregressive Model Limitations\n\nThe expressiveness of non-autoregressive models tends to be limited when confronted with multiple optimal solutions for the same graph [1]. Approaches such as multiple outputs have been suggested [1] to alleviate this issue. Our diffusion model framework presents a more principled way to address the distribution multimodality problem by iterative denoising. We will make this point more clear in the revised version of our paper.\n\n> Generalization of the current method with unsupervised learning\n\nYour suggestion in this direction is very insightful and certainly deserves exploration as future work. Our diffusion models, being probabilistic in nature [2], could potentially be trained with reinforcement learning without supervised labels in principle. However, the sparse reward issue (discussed in line 37) might pose a challenge.\n\n> Iterative Improvement Methods\n\nDue to space constraints, we have provided a detailed analysis of iterative improvement methods in our extended related work section in Appendix C.\n\n> Attention in Best-Performing Methods\n\nIn autoregressive methods, the attention mechanism is essential to capture sequential order in the solution, as per previous work [3]. Variants like linear attention (Transformer as RNN) might be possible, but they have not been explored in sufficient depth in the literature so far.\n\n> Regularization in Loss\n\nOur primary goal was to keep our framework as simple as possible, and thus we did not include any additional terms in our loss function. We are also unaware of the effectiveness of regularization in diffusion models literature, which might be a good future topic to explore.\n\n> Choice of Network\n\nOur choice of network mainly follows previous work [4,5]. The Anisotropic GNN was selected because it can produce the embeddings for both nodes and edges, unlike typical GNNs such as GCN or GAT, which are designed for node embedding only. This design choice is particularly beneficial for tasks that require the prediction of edge variables like TSP. We will incorporate this clarification in the revised version of the paper.\n\n> Sparsification\n\nSparsification was not applied to Concorde / LKH, as these solvers typically have internal mechanisms to effectively handle tasks with Euclidean distances and large-scale coordinate inputs.\n\n> Nomenclature Preferences\n\nWe appreciate your advice on the usage of \"gap\" instead of \"drop\". We will incorporate this change in the revised version of the paper.\n\n> Runtime Inclusion\n\nWhile the runtime may not be directly comparable due to different hardware configurations and other factors, it was reported to provide readers with an understanding of our method's performance speed under different decoding strategies. We also wish to note that the runtime of traditional methods is not significantly impacted by hardware as they use CPUs.\n\n> Elaboration on the Inductive Bias for ER Graphs\n\nOur interpretation is that the Anisotropic GNN may not be ideal for MIS (ER) graphs because MIS is essentially a node selection task while the Anisotropic GNN is essentially designed for edge representation learning and related edge selection tasks (like TSP). Using an edge-based method to solve a node-based prediction task would unavoidably lead to wasteful computation and unnecessary complexity in modeling.  We appreciate the reviewer’s question on this and consider the in-depth investigation of this hypothesis and potential remedies as a future research topic.\n\n> Benchmark Studies Reference\n\nWe are referring to published results reported on the popular TSP-N benchmark.\n\n---\n\n[1]: Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search\n\n[2]: Score-Based Generative Modeling through Stochastic Differential Equations\n\n[3]: Attention, Learn to Solve Routing Problems!\n\n[4]: An experimental study of neural networks for variable graphs\n\n[5]: Dimes: A differentiable meta solver for combinatorial optimization problems"}, {"review_id": "sZc25CZItG", "reviewer": "Reviewer_zZSi", "summary": "This paper introduces DIFUSCO, a novel graph-based diffusion model for solving NP-complete combinatorial optimization problems. The authors propose two variants of the diffusion model: one with continuous Gaussian noise and one with discrete Bernoulli noise. Through extensive experiments on the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS) problems, they demonstrate that the discrete diffusion model outperforms the continuous one. The proposed DIFUSCO model achieves state-of-the-art results on TSP and MIS problems, surpassing previous probabilistic NPC solvers in both accuracy and scalability.", "questions": "The authors hypothesize that the poor performance due to the use of an edge-based Anisotropic GNN, whose inductive bias may not be suitable for ER graphs. Could the authors elaborate more on this issue? Are there potential modifications to the model that could improve its performance on ER graphs?\nCould the authors provide more details on the performance of the model without post-processing? Furthermore, are there potential improvements to the model that could reduce its dependency on post-processing?\n", "limitations": "Societal impact of the work is not discussed in this paper. Furthermore, limitations of the proposed technique need further discussions. Maybe solving a real-world application can be helpful.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novelty: The paper introduces a new graph-based diffusion model for solving NP-complete combinatorial optimization problems, which is a novel technique to the field.\nPerformance: The proposed DIFUSCO model outperforms previous state-of-the-art methods on TSP and MIS problems, demonstrating its effectiveness.The DIFUSCO model shows good scalability, able to handle larger problem instances that previous methods struggle with. The DIFUSCO model exhibits good generalization ability, with the model trained on TSP-50 performing well on even TSP-1000 and TSP-10000.\n", "weaknesses": " The paper focuses on TSP and MIS problems, and it is unclear how well the proposed model would perform on other types of NP-complete problems.\nThe DIFUSCO model, especially with discrete diffusion, does not perform well on ER graphs. \nThe performance of the DIFUSCO model relies on 2-opt local search post-processing. Which of the model and 2-opt is the major contribution to the final performance?\nThe proposed DIFUSCO shares similar representation with GNN-based solvers. What are the substantial advantage over the GNN-based ones?\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewers taking the time to evaluate our work. Please find our responses to your concerns below:\n\n> About more Benchmark Problems\n\nWe would like to cite the comments by reviewer WFTx: “It is extremely solid study in all regards.  .. The experiments are impressive in their breadth.”  We truly appreciate such an understanding.\n\nOn the other hand, we must point out that solving all the NP-complete problems in a single paper is not realistic and has not been the reality in the literature of both combinatorial optimization and machine learning. We focus on the TSP and MIS problems because they are adequately representative of edge-based and node-based NP-complete CO problems, respectively, and have been commonly studied by the machine learning community for neural solvers on NP-complete problems.\n\n> Which of the model and 2-opt is the major contribution to the final performance?\n\nWe've compared results with 2-opt post-processing for both DIFUSCO and DIMES in Table 2 of Appendix D: Additional Results. Evidently, DIFUSCO outperforms DIMES, even when 2-OPT is applied to both.\n\n> The proposed DIFUSCO shares similar representation with GNN-based solvers.\n\nWe would like to clarify that while DIFUSCO does use GNN as a neural network backbone, it's a broader probabilistic framework for tackling graph-based NP-complete CO problems. The novelty lies in the framework, not in the neural network architecture.\n\n> Elaboration on the Inductive Bias for ER Graphs\n\nOur interpretation is that the Anisotropic GNN may not be ideal for MIS (ER) graphs because MIS is essentially a node selection task while the Anisotropic GNN is essentially designed for edge representation learning and related edge selection tasks (like TSP). Using an edge-based method to solve a node-based prediction task would unavoidably lead to wasteful computation and unnecessary complexity in modeling.  We appreciate the reviewer’s question on this and consider the in-depth investigation of this hypothesis and potential remedies as a future research topic.\n\n> Are there potential modifications to the model that could improve its performance on ER graphs?\n\nWe speculate that node-based GNNs, such as GAT or GIN, as utilized in state-of-the-art neural MIS solvers [1], could potentially improve performance on ER graphs.\n\n> Could the authors provide more details on the performance of the model without post-processing?\n\nPerformance data without post-processing is presented in Table 2, and a more detailed analysis is provided in Figure 3 of the appendix.\n\n> Are there potential improvements to the model that could reduce its dependency on post-processing?\n\nOur post-processing design is borrowed from prior work [2]. It would indeed be intriguing if the neural model could produce high-quality results without any post-processing. However, given that the 2-opt post-processing has been commonly used since 2018 [3] and is much more efficient than other neural or heuristic parts, we consider it as a common practice.\n\n> Societal impact of the work is not discussed in this paper.\n\nWe haven't explicitly discussed societal impact as it has not been apparent yet as in the early stage of research, as pointed out by reviewers WFYx, 6WFF, and b1y4.  Nonetheless, we do believe that good learnable neural solvers for NP-complete problems will have a huge impact on a broad range of AI problems as they are the fundamental core set.\n\n> Maybe solving a real-world application can be helpful.\n\nPlease note that we have already presented results on the real-world TSPLIB dataset in Appendix D: Additional Results - Generalization to Real-World Instances.\n\n---\n\n[1] Learning what to defer for maximum in dependent sets\n\n[2] Diffusion models as plug-and-play priors\n\n[3] Learning heuristics for the TSP by policy gradient\n"}]

Author rebuttal:

Meta-review: Overall, I agree with the review team that this is a strong paper that should be accepted at NeurIPS. I am grateful to the authors that they have responded to all of the referees' comments in detail. I agree with two of the referees that runtime information would be useful to add to the paper, but ultimately I will leave this to the authors.

Thank you for submitting your work to NeurIPS!
Decision: Accept (spotlight)