T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization
Authors: Yang Li
Jinpei Guo
Runzhong Wang
Junchi Yan
Venue: NeurIPS 2023 poster (2023)
Keywords: Machine Learning
Combinatorial Optimization
Generative Modeling
Diffusion Model
TL;DR: This paper proposes a training to testing framework for solving combinatorial optimization problems, which learns solution distribution during training and then conducts a gradient-based search within the solution space during testing.

Abstract: Extensive experiments have gradually revealed the potential performance bottleneck of modeling Combinatorial Optimization (CO) solving as neural solution prediction tasks. The neural networks, in their pursuit of minimizing the average objective score across the distribution of historical problem instances, diverge from the core target of CO of seeking optimal solutions for every test instance. This calls for an effective search on each problem instance, while the model should serve to provide supporting knowledge that benefits the search. To this end, we propose T2T (Training to Testing) framework that first leverages the generative modeling to estimate the high-quality solution distribution for each instance during training, and then conducts a gradient-based search within the solution space during testing. The proposed neural search paradigm consistently leverages generative modeling, specifically diffusion, for graduated solution improvement. It disrupts the local structure of the given solution by introducing noise and reconstructs a lower-cost solution guided by the optimization objective.  Experimental results on Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS) show the significant superiority of T2T, demonstrating an average performance gain of 49.15% for TSP solving and 17.27% for MIS solving compared to the previous state-of-the-art.

T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization
Yang Li, Jinpei Guo, Runzhong Wang, Junchi Yan"
Dept. of Computer Science and Engineering & MoE Key Lab of AI Shanghai Jiao Tong University (yanglily, jinpei, runzhong. wang, yanjunchi] edu. cn
Abstract
Extensive experiments have gradually revealed the potential performance bottle- neck of modeling Combinatorial Optimization (CO) solving neural solution prediction tasks. The neural networks, in their pursuit of minimizing the average objective score across the distribution of historical problem instances, diverge from the core target of CO of seeking optimal solutions for every test instance. This calls for an effective search on each problem instance, while the model should serve to provide supporting knowledge that benefits the search. To this end, we propose T2T (Training to Testing) framework that first leverages the generative modeling to estimate the high-quality solution distribution for each instance during training, and then conducts gradient- based search within the solution space during testing. The proposed neural search paradigm consistently leverages generative modeling, specifically diffusion, for graduated solution improvement. It disrupts the local structure of the given solution by introducing noise and reconstructs lower-cost solution guided by the optimization objective. Experimental results on Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS) show the significant superiority of T2T, demonstrating an average performance gain of 49.15% for TSP solving and 17.27% for MIS solving compared to the previous state-of- the-art.
Introduction
Machine Learning (ML) for Combinatorial Optimization (CO abbreviated ML4CO 2 is a rapidly growing area, lying at the intersection between the two well-established communities. CO problems are essential in operational research as well as computer science, in both theory and practice. However, due to the inherent computational difficulty. e.g. NP-hardness, (approximately) solving these problems with effectiveness and efficiency poses significant challenges. Compared with traditional heuristic- -earrstiic--eeddddeee solvers, ML. has recently shown its promising potential to automatically learn heuristies in a data-driven scheme I 2 4 meanwhile with the aid of human knowledge which would normally improve the sample-efiie efficeeeff [5 6 7 g 9. Moreover, the introduction of neural networks also allows for the speedup by parallel matrix computation forward inference.
A popular framework in ML4CO is developing neural networks to directly predict a solution or generate solution with the aid of neural predictions, such that the corresponding objective score is 13 However, the neural network can only fit limited mappings from problem
minimized [0
*Correspondence author. This work was partly supported by National Key Research Development Program of China (2020A A00107600,,, NSFC (62222607) and STCSM (2251 105100). In this paper, CO problems mainly refer optimization problems on graphs I with objective function.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Solation
Denoosing Process Nuiing
Graph Instunce, cq,, CD-oodedinttss in TSP
Grddien
Search
Random Noise
Solution
Pv(s(G)
Sclation Dustbuttoo
X
X
FC-1
X
Disuibution Learning
Ieanunce
Figure 2: Diffusion modeling for CO solving where the model learns how to gradually denoise from the random noise to predict each step's data distribution, eventually modeling the solution distribution.
Figure 1: Diagram of proposed framework.
parameters to (near) optimal solutions in the training set, resulting in subpar performance on unseen Therefore, it calls for neural solvers to efficiently explore solutions tailored to each specific problem instance. In the traditional framework, the network prediction typically converges to a local optimum with little diversity, struggling further explore superior solutions. In this paper, we resort to a more effective framework that first learns to model the distribution of high- quality solutions conditioned on problem instances, then conducts a gradient- superior solution specific to the given instance, as shown in Fig. [ Existing alternative methods that conduct the tailored search in the testing phase, c.g. active search [16 17 and meta-learning (18). require updating the model weights during testing, hindering their applications in computational intensive scenarios. In contrast, we develop more efficient gradient search framework to obtain a superior solution specific to the given instance, without the need to update model weights.
test instances [14 [1
search to obtain a
We exploit the powerful generative neural CO solver [9] that learns model the distribution of high- quality solutions conditioned on specific problem instances. The generative models are welcomed in their ability to output high-quality images (20], texts (2]] and graphs [2 with great diversity, whereby these advantages are also welcomed in the ML4CO community. Some recent successes in generative learning of CO are demonstrated in classic CO problems e.g. Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS) (via Diffusion [99 and Variational Auto-Encodes (3) ) Satisfiability
Problem (SAT) and Mixed-Integer Linear Programming (MILP) (via graph generators 24 25 26))
also in more realistic applications e.g. routing for chip design (via Diffusion (27 and Generative Adversarial Network (28). Notably, the very recent adaptation of the flourishing diffusion models in probabilistic generation 19 has resulted in state-of-the art performance for solving CO problems e.g.
TSP. The diffusion modeling for CO solving is illustrated in Fig. 2 where the model is designed to estimate the solution distribution given a certain instance G, i.e. pa Xo, G). Despite its high-quality solutions, a major drawback is the unawareness of optimizing the CO objective as the generative model simply learns to fit distribution of solutions. To further improve the efficiency of the current costly from-scrated sampling, it stands crucial to introduce a more efficient search- paradigm to further explore high-quality solutions in terms of the final objective of the problem.
To this end, we propose a gradient- graddent-bbased search paradigm to further leverage the learned solution distri- bution through training, bridging the solution distribution learning during generative modeling training to gradient search during testing for CO, dubbed T2T. The proposed search paradigm well aligns with the behavior of progressive generative model especially for the SOTA embodiment i.e. diffusion. The diffusion model provides probabilistic framework that enables a smooth and flexible transition between random noises and feasible solutions, allowing for varying degrees of structure disruption, with a reference denoising process to restore a solution. Leveraging this framework, it is natural to model the local search heuristic as two stages, i.c., disrupting the local structure and reconstructing it with a better objective score. Specifically, T2T first adds certain noise to the given solution and then denoises it to reconstruct a lower-cost solution in iterations, which is achieved by incorporating the ob- jective optimization guidance into the denoising steps through gradient feedback in the loop, steering the recovered sampling towards the optimization direction, illustrated in Fig. [3] T2T enhances the solving paradigm by incorporating a search procedure with explicit objective guidance, which enables more efficient sampling and allows for deeper exploitation of the estimated solution distribution.
For the discrete nature of CO, T2T builds itself upon discrete diffusion models 29 30 3T. which
in training learns the transition between categorical noises and feasible discrete solutions that are

---

represented as probability maps of nodes/edges on graphs indicating whether each node/edge is included in the solution. The transition is tailored for each instance as it is conditioned on the corresponding instance's statistics. The training of T2T follows the standard training paradigm of diffusion models, which primarily equips the model with feasibility awareness and estimates the distribution of high-quality solutions. While during testing, we introduce the objective optimization guidance which serves as the complementary optimization and gradient search utility.
We showcase the efficacy of T2T on two typical NP-hard combinatorial optimization problems for edge-selectinn sege--electing and selesseletting types respectively, i.e., TSP and MIS, which have been attracting most attention in the community of ML4CO. Empirically, T2T exhibits strong performance superiority over existing state-of-the- tort-e---ttttttto- neural solvers on benchmark datasstss across various scales, Notably, a significant performance gain is observed when compared to the purely constructive diffusion solver 19]. thereby highlighting the effectiveness of the designed search-based paradigm.
The highlights of this paper include: 1) We introduce the framework of T2T which first estimates the high-quality solution distribution for each instance during training, and then leverages the diffusion process to perform an effective local search in the solution space during testing; 2) We incorporate the optimization objective guidance into the denoising model with theoretical analysis, which equips the model with gradient feedback directly from the instance-wise objective score, enabling it to perform optimization while ensuring general feasibility; 3) Extensive experiments show the promising performance of the proposed T2T, even when trained without high-quality solution labels.
2 Related Work
Machine Learning for CO Solving. ML solvers can be categorized into construction solvers and improvement solvers. Constructive solvers include autoregressive solvers [32] [2] 6 23 8 which step-by-step extend partial solution to produce a complete feasible solution, and non-autoregressive
solvers KK 34
14
35
19] which predict solution (typically soft constrained) in one shot. Improve-
often define local operators such as 20PT [36 377, node swapping [5] 37). sub-problem ving
ment solvers 36
37
5
38 to perform local search towards minimizing the optimization objec- tive. The algorithm pipelines generally involve selecting specific regions and locally optimizing sub-solutions. While T2T can be a rather different improvement solver, which allows for parallel op- timization across multiple sub-regions and equips the generative modeling with the search procedure.
Generative modeling for CO leverages the powerful expressive and modeling capabilities of generative models for direct CO solving (e.g. VAE 39) GAN (28 40 41]. Diffusion 27:27,
as well as GFlowNets (43 44 which, while not typical generative model itself, is closely related to generative modeling). and for supporting CO solving (2 25]. DIFUSCO [19] has
become state-of-the-art for the TSP problem by leveraging powerful diffusion models. However, no instance-specific search paradigms are introduced in existing methods to fully utilize the estimated solution distribution. Instead, they rely on multiple from-scratch samplings to leverage the distribution, which is computationally expensive. Though (23 attempts to utilize the evolution algorithm to conduct multiple iterations of sampling, it yet incurs even more significant costs without explicit objective guidance in the loop. In contrast, T2T serves as an improvement solver that locally modifies the given solution with objective guidance in the loop. It offers the flexibility to introduce any degree of disruption and rewrite without the necessity to construct the solution from scratch.
Diffusion Probabilistic Models. Diffusion models (score-based models) typically comprise noising process and a learnable denoising process, where neural networks predict the noise introduced in each step. Diffusion's 's inference can be seen as score (gradient) guided search, which general principle across different settings [45] [4) 47). Diffusion in continuous space (c.g., for image genera- 51 (52 have established and consolidated the theoretical foundations of the general diffusion framework. Several landmark works have advanced the diffusion model through vari- ous aspects. DDIM 49 generalizes DDPM via a class of mon-Markovian processes which gives rise to implicit models that produce high-quality samples much faster. For conditional generation. classifier guidance 29 (2 and classifier-free guidance [53] are introduced with the score estimate of the diffu-
tion) 29 48
42
49
50
sion models to produce conditional results. Similar paradigms are adopted in discrete diffusion models for generating discrete data using binomial noises (2] or multinomial/categoriaal noises ROO 31 Dif- fusion also demonstrates its capability to learn offline policies in reinforcement learning tasks (5455).
3

---

3 Approach
This section presents our proposed T2T framework, including the preliminaries, offline training pipeline based on generative modeling, and online testing pipeline with objective guided search.
3.1 Preliminaries: Combinatorial Optimization on Graphs
Following the notations adopted in [3 56 57 we define ç as the universe of CO problem instances represented by graphs G(V, E) E G. where V and E denote the node set and edge set respectively. CO problems can be broadly classified into two types based on the solution composition: edge- selecting problems which involve selecting subset of edges, and node-selecting problems which select a subset of nodes. Let x E {0, {0,1); 1} denote the optimization variable. For edge-selecting problems, N = n² and Zinntj indicates whether Esy is included in æ. For node-selecting problems, N = n and z; indicates whether V; is included in æ. The feasible set consists of a satisfying specific constraints as feasible solutions. A CO problem on G aims to find a feasible x that minimize the given objective function G(( {0, 1) I220
min =ff0,1 N f(x;; G) s.t. xEΩ
In this paper, we study two primary and representative CO problems: TSP and MIS. TSP defines on an undirected complete graph G = E)) where V represents n cities and each edge Egj has a non-negative weight way representing the distance between cities i and j. The problem can then be formulated as finding a Hamiltonian cycle of minimum weight in G. For MIS, given an undirected graph G (V, E), an independent set is subset of vertices S S V such that no two vertices in S are adjacent in G. MIS is the problem of finding an independent set of maximum cardinality in G.
3.2 Offline Solution Distribution Learning on Training Set based on Diffusion
The basic diffuusin modeling for solution generation in training is primarily based on [19 's design while this paper explicitly formulate the solving task as a conditional generation task. As mentioned in Sec. 3.1 the solutions of CO problems can be represented as x {0, 1) with x E St. For each entry, the model estimates Bernoulli distribution indicating whether this entry should be selected. In implementation, each entry of solution x is represented by a one-hot vector) such that x E (0, 1} x2 Generative modeling aims to model the distribution of high-quality solutions conditioned on the given instance, while feasibility constraints can be broadly captured through learning and eventually hard-guaranteed by post-processing. For the purpose of problem-solving, the generative model desired to estimate the solution distribution given a certain instance G, i.e., ())). In this section, we model this distribution through the discrete diffusion models 42] 30
Following the notations of 42 30), the general framework of diffusion includes a forward noising and reverse denoising Markov process. The noising process, also denoted as the diffusion process, takes the initial solution Xg sampled from the distribution g (xxn G) and progressively introduces noise to generate a sequence of latent variables X1:7 = X1, X2, Xy. Specifically, the noising process is formulated g(x1:7(x))
I[ q(x; (x-x) The denoising process is learned by the model, which starts from the final latent variable Xy and denoises x, at each time step to generate the preceding vari- ables X₃-1 based on the instance G, eventually recovering the target data distribution. The formulation of the denoising process expressed as pe(xo:T G)) = p(xr) II. Po (xx-1 X2, G). where 0 denotes the parameters of the model. The training optimization aims to align po (Xol G) with the data distri- bution gx,o|G) and the objective adopts the variational upper bound of the negative log- likeliioooood::
f E, log (x G) + EDRA lq(x xo) ll
G)]
+C
(2)
t>1
Specifically, the forward noising process is achieved by multiplying x, E [0, N at step t with a forward transition probability matrix Q: E [0, 1]222 where [Q:]e indicates the probability of
transforming e; each entry of x, to ey. We set Q = 1 - Be
3r
1-88
1-3
30 where 33 E [0, 1]
B
Each entry with [0, indicates that it is included in x and [1, 0) indicates the opposite.

---

such that the transition matrix is doubly stochastic with strictly positive entries, ensuring that the stationary distribution is uniform which is an unbiased prior for sampling. The noising process for each step and the (-step marginal are formulated as:
(xx,(x(-)) = Cat(xx: p- xx- and q(x: xo) p Xo Q,)
(3)
where Cat(x: p) is a categorical distribution over N one-hot variables with probabilities given by vector p and Q2 Q1 Q2 Qt. Through Bayes' theorem, the posterior can be achieved as:
xxx+11 X,, xo) (xxx X2 xo (x))(((()1(x))
Cat x Ot O Xo Q
(xx{(xo)
Xx
The neural network is trained to predict the logits of the distribution pa x,, G), such that the denoising process can be parameterized through q(x;-1 Xo):
p
x Σ ((xx_1(xe,, Xo x (Xo]xx. x,, G)
(5)
%
Specifically for implementation, the condition G is enforced as an input to the network 0, which is embodied as anisotropic graph neural network with edge gating mechanisms [33 following [1]. For TSP, the instance condition consists of 2D coordinates of the vertices. The network input includes node embeddings from the 2D coordinates, along with edge embeddings from x,, For MIS, the edges E serve as the instance condition, complemented by the inclusion of node embeddings from to collectively form the input. The output of the network is Po (xoooxxx G) E [0, 1] parameterizing N Bernoulli distributions for N entries in X
3.3 Test-stage Gradient-based Search with Instance-wise Objective Feedback
In this section, we first present the technical solution for the objective gradient incorporation in de- noising steps, and then illustrate the neural search paradigm that leverages the guided denoising steps.
3.3.1 Objective-aware Denoising Process with Gradient Feedback
In the context of combinatorial optimization, the incorporation of objective optimization is necessary and important, which enables the direct involvement of objective and effective search over the solution space towards minimizing the score. As discussed in Sec. [.2] at step the model denoise x, by
po(x;-1 xx,, G). For the purpose of objective optimization, we aim to estimate pe pe(xx-1|xx G. y²) where y" is the optimal objective score given the instance G:
y* min ((x; G) s.t.
XE
(6)
to guide the denoising process to x* = arg min (xx G). We will show later that this ability does not necessarily require the access y x", and can readily be achieved by the model learned in Sec. 3.2 without relying on any additionally trained networks. The adopted objective is defined below.
Optimization Objective. Since the generated samples are guaranteed to satisfy the hard constraints, we incorporate constraint satisfaction into the objective and utilize a relaxed ob- jective with constraint penalty, as adopted in [13 56 57 Consider a relaxed cost function (+(:)) : (0, 1) - Rzo which defined on the constraint relaxed space 1) satisfying fr = f(x; V E Ω, and a constraint penalty gr (x; G) [0,1] -> R2o where 0.(2; G) 0 if x E and gr (x; 2 1 if x & Ω the objective be formulated as:
I(x; G) (+(x;) + (g: G)
where 3 > maX fa:; G). For MIS, the constraint can be straightforwardly modeled as æ,ay
T; if (i.j) E E, thus the objective can be formulated as IMss (x; G) & - Eisign x; + E(i)) T;
While for TSP, since the constraints are difficult to explicitly express, we directly select the objective as 41SP = ④ D where D E R denotes the distance matrix.
Objective Guidance in Denoising Steps. The estimation of (x Xt. G,y") can be modeled through the following proposition, adapted from the classifier guidance technique [52]:
Proposition The optimization-enfrree denoising probability estimation po(x G.y") equals to 1x0(xx-1lxx G)p(y" (x) G)), where Z is a normalizing constant.
5

---

The proof is given in the Appendix. As p G) can be readily obtained from the trained
network, the main challenge of estimating ( Xt, y.y") lies in estimating p(y" X G). Since
Xt-1 not accessible at step i, we utilize Taylor expansion to approximate log p(y [ G) around Xt-1 = Xt, given that X
Xx:
log pogpp"xxx11.
1x G) ply Ix., G) + Vxx, logp(y" |xx, G)] (x--1 xx)
= Vxx logp(y"> (x. G)] x + logp(y' (x,, G) [Vx, log (erp(l"leer (x,, [x,
(8)
c(x))
where C(x,) is irrelevant to X Applying exponentiation, obtain:
ply x1 G) exp (lVx, logp(y"|x,, G)] (x
(9)
To determine ply" Xx, G), we utilize mnsegy-basedd modeling [58 to model the distribution p(y) X1, G). In this context, define the energy function as:
Ely, Xe, G) = -y- (xxo G)I
(10)
where xx(x:) denotes the clean target sample Xo corresponding to x, The energy function quantifies the compatibility between and (x,, G), and it reaches zero when is exactly the final objective score originating from x; with respect G. Such design enables the best y matching the inputs to
maintain the highest probability density, and the probability density is positively correlated with the matching degree. Then we employ the Gibbs distribution to characterize the probability distribution over collection of arbitrary energies:
exp(-Eig X1, G))
exp( ly - 1(x, (x,);;)(x;))))))) G)I)
p(y|x; G) [y exp(-E(y's X1, G))
(11)
Jy exp( - l8' ((xx
Let Z = exp(e 11/ (xxx G))) and substitute y², we have:
log p(y"((" p(y"(x(, G) = 1f -(xxx(x))) G) log Z and Xx, logply"" = - (xx,((x(xx) G)
(12) Note the gradient operator has removed to effect of y" as a constant, thereby eliminating the need to access y" for achieving the target. And Z as the integral over the entire distribution is not affected by x, and thus can also be removed by the gradient operator. Recall that the network is trained to predict the logits of pe (
xx) E [0, Nx2 which includes the logits of N Bernoulli distributions, [Exol, [E
satisfying [Po (xp ),
). Thus (xxx G) can be estimated using Ex, ((xo(x:); ): G) x [(Ex, (u G)
(13)
12 and 13 we obtain p(y" (x:-1 G) x exp ([- (1 Ro: G)] xx-
By Eq.
and the guided denoising probability estimation can be achieved by ps px 1kk-1/x, Xx,, G, y Zpo ( Xx, G)p(y" x,-1, G)) where Z is the normalizing constant, to realize the guided denoising.
3.3.2 The T2T Framework for Efficient Differentiable Neural Search
With the objective gradient incorporated denoising process in Sec. 3.3. now delve into T2T.
Overview. As shown in Fig. 3 the algorithm starts with an initial solution Su and conducts several iterations to enhance the given solution. Each iteration involves adding certain degree of noise to disrupt the structure, denoising with objective gradient guidance obtain a lower-cost soft- constrained solution, and subsequently post-processing to decode feasible solution E Q. The algorithm eventually reports the solution with the lowest objective score ever achieved.
Structure Disruption. Recall that X1, X2. XT are situated in spaces characterized by pro- gressively escalating levels of disruption. To introduce controlled degree of disruption to the given solution, we employ S to derive the distribution of the disrupted solution { as N Bernoulli distributions, where a serves as hyperparameter to control the degree of noise. Subsequently, the disrupted solution S.T can be sampled from ((S.T)))) (So)-
Objective Guided Solution Reconstruction. From 8,T, we employ po po(8;-1 |s,, G,y") proposed in Sec. 3.3. to perform denoising, which aimed at recovering potentially lower-cost S/ Additionally,

---

Testing
SO
2" Round
Optinization
6-0
$
1- Round
46Krr (4)
Enitial Sulution
(Stur (y)
Denoising
Denoising
XT
X
Noising
Neising
Training
Feasibility
Figure 3:
T2T iteratively adds noise to the solution and performs denoising guided by the problem objective (e.g. TSP), improve the solution shown in the orange part. The bottom blue part shows the capability of diffusion to establish a smooth transition from random noises to feasible solutions. s*: optimal solution; y": optimal objective score; 0: model parameters; G: given instance.
we utilize the fast sampling algorithm introduced in DDIM [49] to accelerate sampling. The algorithm determines M-element subset from latent variables $1:a7 to obtain {s,, " Sr } (71 1 and TM = aT'), and directly models p s G, y²). which effectively reduces the number of denoising steps. In our implementation, we uniformly perform 10-step reconstruction, i.c., M 10.
Post-inference Decoding. Note the mechanism guarantees that the recovered solution s E {0. 1] Nx2 (consisting of N one-hot vectors), but it does not necessarily satisfy E Ω. Thus, in the last step's s inference, we directly output the logits of its distribution po to produce EEs/ as the heatmap H E [0, 1jaV where each element denotes each edge/node's confidence to be selected, and then we adopt greedy decoding to obtain a feasible solution. We follow previous works [59] 35 19] to perform greedy decoding by sequentially inserting edges (for TSP) nodes (for MIS) with the highest confidence there are no confficts. For TSP, the 2OPT heuristic [60] is optionally applied.
Tradeoff' Between Guidance Accuracy and Local Rewriting Degree. Note that the objective- guided denoising process relies heavily on the accuracy of the estimation ño (Xo xx). Intuitively, easier to restore the original solution from the data that has lower noise content. And with excessive noise interference, the estimation will deviate significantly from the ground truth, resulting in faulty guidance. This is also one of the reasons why we use local rewriting mechanism. However, while the accuracy the estimation increases as it moves closer to the original solution space, also limits the degree of reconstruction in terms of the solution structure. Therefore, it is crucial to strike balance between the estimation accuracy and the extent of local rewriting. To accomplish this, we employ the aforementioned hyperparameter to control an appropriate range of perturbation.
4 Experiments
All the experiments are performed on GPUs of NVIDIA Telsla A100. All the test evaluations performed on a single GPU, while the trainings are conducted parallel with four A100 GPUs. Source code is publicly available at /t/ttpss///itthub.. com www.aa///oo/tiiaaaabbbaaaab -tw.nkaaaaaassuutto00
4.1 Experimental Setup
We test on two CO problems including TSP and MIS. The comparison includes SOTA Icarning-based solvers, heuristics, and exact solvers for each problem. For comparison fairness of learning solvers, the initial solutions of our approach are obtained by denoising random noises by Eq. (same solution as the constructive diffusion solver DIFUSCO [9]. To balance the inference time, for experiments with runtime measurement, T2T utilizes a reduced number of sampling steps for constructing the initial solutions, specifically 20 steps. While DIFUSCO, as an important baseline, adopts 120 inference steps for TSP and 50 steps for MIS. The models for both TSP and MIS are trained with 1000 denoising steps, i.e., T 1000. For gradient search, T2T generally involves 3 iterations with 10 guided denoising steps for each. See more details in Appendix.
7

---

Table 1: Greedy Decoding on TSP-50 and TSP-100. RL: Reinforcement Learning, SL: Supervised
Learning, Grdy: Greedy Decoding. denotes the baseline for the performance drop.
TSP-50
TSP-100
ALGORITHH
TYPE
LENGTHL
DROP
LENGTHL
DROPJ
Concorde
62
Exact
5.69*
0.00%
7.76'
0.00%
2OPT
64
Heuristics
5,86
2,95%
8.03
3,54%
Farthest Insertion
Heuristics
6.12
7.50%
8.72
12.36%
12
RL+Grdy
1.76%
8.12
4.53%
GCN B3
SL+Grdy
5.87
3.10%
8.41
8,38%
Transformer 66
RL++Gryy
5.71
0.31%
7.88
1.42%
POMO 6
RL+Grdy
5.73
0.64%
7.84
1.07%
Sym-NCO
RI++Grly
7.84
0,94%
Image Diffusion [59
SL+Grdy
5.76
1.23%
7.92
2.11%
DIFUSCO
19
SL+Grdy
5.72
0.48%
7.84
1.01%
12T (Ours)
SL+Giddy
5.69
0.04%
7.77
0.18%
AM [12
RL+Grdy+2OPT
5.77
1.41%
8.02
3.32%
GCN 33
SI=+Crdy+2OPT
0.12%
7.81
0.62%
Transformer 665
RL+Grdy+2OPT
5.70
0.16%
7.85
1.19%
POMO 6
RL++Gdy++0PP
5.73
0.63%
7.82
0.82%
Sym-NCO
RL+Grdy+2OPT
7.82
0.76%
DIFUSCO [19
SL+Grdy+20PT
5.69
0.09%
7.78
0,22%
T2T (Ours)
SL+GGdyy42PP
5.69
0.02%
7.76
0.06 %
4.2 Experiments for TSP
Datasets. A TSP instance includes 2-D coordinates and a reference solution obtained by heuristics. Training and testing instances are generated via uniformly sampling N nodes from the unit square [0, 1]", which a standard procedure as adopted in 12 23 33 61
35 19]. We experiment on various problem scales including 50,-50, TSP-100. 100-500, and TSP- 1000. The reference solutions
for TSP-50/100 are labeled by the Concorde exact solver [62] and the solutions for TSP-500/1000 labeled by the LKH-3 heuristic solver 663] The test set for TSP-50/100 is taken from [2] B3
with 1280 instances and the test set for TSP-500/100 1000 is from 34 with 128 instances for the fair comparison. This section also incorporates results real-world TSPL.E dataset.
Metrics. Following 12 33 35 19, we adopt three evaluation metrics: 1) Length: the average total
distance cost of the solved tours w.r.t. the corresponding instances, as directly corresponds to the objective. 2) Drop: the relative performance drop w.r.t. length compared to the global optimality or the reference solution; 3) Time: the average computational time solve the problems.
Results for TSP-50/100. Table Table@presse presents the results. Since DIFUSCO 19 has been shown able to attain global optimality for instances with these scales, at the cost of a sampling decoding scheme, we degrade to the greedy decoding setting a more meaningful evaluation. The baselines include state-of-the state-of-the-art learning-based methods with greedy decoding, as well as traditional exact and heuristic solvers. Hyperparameter a set as 0.25. Both DIFUSCO and T2T adopt 50 inference steps. As evident from the results, in the setting of pure greedy decoding without 20PT refinement, the proposed search-bar based paradigm achieves a substantial reduction in performance drops from 0.48% to 0.04% for TSP-50 and from 1.01% to 0.18% for TSP-100.
Results for TSP-500/1000. Table presents the results. The baselines include recent learning methods with greedy decoding and sampling decoding (x4), i.e. producing multiple solutions in parallel and selecting the best one, as well as traditional exact and heuristic solvers. DIFUSCO and T2T are compared in the same conditions. DIFUSCO and T2T adopt 120 and 20 inference steps, respectively. The results of other baselines are quoted from 34 and (35] with the runtimes provided for reference. In the sampling decoding setting, compared to previous neural solvers, T2T improves the performance drop from 0.83% to 0.37% for TSP-500 and 1.30% to 0.78% for TSP-
Effect of Disruption Ratio a. As discussed in Sec. 3.3.2 the hyperparameter a is utilized to regulate the extent of perturbation, striking a balance between guidance accuracy and local rewriting degree. Fig. (a) illustrates the impact of a on the solving performance. The experiments are performed on TSP-500 with both greedy and sampling decoding settings. The results demonstrate the tradeoff existence and indicate that 0.3 < S 0.4 can attain relatively better performance.
http://comopt.. ifi f.i..m uni- hww.-heidebbbbggg wtw.eloorrrgdddoooottaarrrsSSss

---

Table 2: Results TSP-500 and TSP-1000. AS: Active Search, S: Sampling Decoding, BS: Beam Search. denotes the baseline for computing the performance drop. DIFUSCO and T2T are compared in the same running settings, while other numbers quoted from 34
35
TSP-500
TSP-1000
ALGORITM
TYPE
LENGTHL
DROP]
LENGTAL
DRUP
TIME
Concorde
62
Exact
16.55*
37.56m
23.12
6.65h
Gurohi
66
Fxact
16.35
0.00%
45.63h
LKH-3 (default)
Hcuristies
0.002%
23.12
2.57
Farthest Insertion
Heuristics
18.30
10.57%
25.72
11.25%
0s
AM
12
RI RLaGidy
20.02
20.99%
1.51m
31.15
34.75 34.75%
3. 1118
SL+Grdy
48.62
110.29%
28.52m
POMO+EAS. Emb
RL+AS+GCrly
19.24
16.25%
12.80h
POMO-EAS Tab
17
RL+AS+Grdy
24.54
48.22%
11.61h
49.56
114.36%
63.45b
DIMES
33
RLi
18.93
14.38%
0,97m
26.58
14.97%
2.08m
DIMES
RL+AS+Gidy
17.81
7.61%
2.106
24.91
7.74%
4,49h
DIFUSCO [19
SL+Grdd
18.11
9.41%
5.70m
25.72
11.24%
17.33m
T2T (Ours)
SLiGidy
17.39
5.09%
4,90m
25.17
8.87%
15.66m
DIMES 35
RL+GRdy+2PPT
17.65
6.62%
1.01m
24.83
7.38%
2. 2.29m
DIMES 33
RL-AS+Gnds+2OPT
17.31
4.57%
2.100a
24.33
5.22%
4.4%
DIPLSCO P
SL:Gr20PT
16.81
1.58%
5.75m
23.55
1.86%
17.52m
121 (Ours)
SL+6+20PT
16.68
0.78%
4.98m
23.41
1.25%
15 91.m
EAN 67
RL+S+20PT
23.75
43,57%
57.76m
47.73
106 46%
5.3%
AM 12
RLABS
18.034%
21.99m
29.90
29.235
1.64h
SL+BS
30.37
51.26
121.73%
51 1.66m
DIMES
RL488
18.84
13.84%
1.66m
26.36
14.01%
2. 5.m8
DIMES 35
RL+AS+S
17.80
7.55%
2.1
21.89
7.70%
4,53h
DIFUSCO
25.11
59. 18m
T2T (Ours)
SEAS
17.02
2.84%
15.98m
24.72
6.92%
53.92m
DIMES 35
RL+S+20PT
17.64
6.56%
1.10m
24.81
7.29%
2 2.86m
RLAAS
17.29
2.1
24.32
5.17%
4.53h
DIPLSCO
1
SLA8-20PT
16.69
0.83%
19.05 19.05m
23.42
1.30%
59.53m
T2T (Ours)
SL4S-20PT
16.61
0.37%
16.03m
23.30
0.78%
54.67m
10
175
Dreg 89)
1.90
90
Inital
1.30
Solukmn
Drep
Dreg
125
Inttal Soludion
Iviial Soldtion
Durs
Outa
be
1.00
04
075
0.4
21
02
0.5
04
06
0.1
02
3.3 alpha
0.4
0.5
-30
83
10
100
Steps
Steps
(b) InitStep-Drop Curve (Greedy and Sampling) Figure 4: Effect of a and initialization steps to the performance drop. For each subgraph, the left represents the greedy decoding, while the right represents the sampling decoding.
(a) a-Drop Curve (Greedy and Sampling)
Effeet of Initial Solution Quality. Fig. (b) illustrates the performance variation when altering the initial solution quality. The quality is controlled by the number of denoising steps for producing the initial solution. The experiments are performed on TSP-500 with both greedy and sampling decoding settings. As shown, T2T exhibits relatively stable performance across varying initial solution qualities, based on which we generally utilize 20 steps for constructing the initial solutions.
Generalization Results on Synthetic Data and TSPLIB. Based on the problem set (TSP-50, 100-100, TSP-500, TSP- 1000), we train the model on a specific problem scale and then evaluate it on all problem scales. Table presents the generalization results of T2T and DIFUSCO with greedy decoding. The results show the satisfying cross-domain generalization ability of T2T, e.g., the model trained on TSP-1000 achieves less than 2% optimality gap on all other problem scales. Moreover, we evaluate our model trained with random 100-node problems on real-world TSPLIB instances with 50-200 nodes. The compared basclines include DIFUSCO and baselines listed in (68)s Table 3. Table 3 shows T2T's superiority achieving merely O. 13333 optimality gap. 58.3% better than the best previous method. Detailed results of Table and the results on large-scale scale TSPLIB instances with 200- 1000 nodes in Appendix A For each instance, we normalize the coordinates to [0.1] and solve with the solving algorithms.
Table 3: Evaluation on TSPLIB dataset.
Method
Drop
AM 16.767%
GCN
40.035%
Leam2OPT
1.725%
GNNGLS
1.529%
DIFUSCO
0.319%
T2T
0.133%
Validation of Gradient Search with Worse Distribution Learning in Training. We investigate the performance over 1o amount of training data and the model trained with lower-quality feasible solutions produced by farthest insertion heuristic (with 7. 7.50% gap to optimality). Results in Fig. 5 val- idate the effectiveness of gradient search even if the distribution is poorly learned, suggesting that T2T

---

Table 4: Generalization results. Tour length and drop with Greedy Decoding are reported.
30
Toneforear
DIFUSCO (1004mp)raa)
POMO
12710 (100k
Toxins
Traning
TSP-50
1SP: 100
TSP 500
TSP 1000
12Y000 It breoptment
DIFUSDO
EIFUSDO (100eesottoN).
TSP-50
DIFUSCO
5.70,..11%
5.200.25%
578 1.00%
58% 2,55%
TSP-100
DIFUSCO
121
7.57. 1.44%
7.50 0.55%
7.78,0.33% 0.23%
1.77, 0.88%
9.33 3,44%
7.55 2.47%
3.02,3311
79., 1:9rs
TSP-500
DIFUSCO)
12T
12:51. 461%
3.79%
26,92,22255
0048
16.68,
16.7% 1.41%
16.6
16.72 1.00%
Figure 5: Results TSP-50 for fewer-shot training with lower-quality supervision.
Ful Truwnng Set
Optiral Superviin
Fower Shot
Fousbbe Supariiie
Fower
1000
DIFUSCO
34.17, 4.50%
24.20 4.603
23,85, 3.166
3.06%
13,65,
17.47,
23,41, 1.23%
2.11%
Table 5: Results MIS. TS: Tree Search, UL: Unsupervised Learning. DIFUSCO and T2T
compared in the same running settings, while other numbers are quoted from 35 43
SATLIB
ER- CRR-(700-00)
ALGORITUM
TYPE
SIZEI
DROP
TIME
SIZE:
DROP
TIME
KaMIS
69
Heuristics
425, $25.96"
37.58m
44.87"
52.13m
Gurobi
66
Exact
425.95
0.00%
26.00m
41.28
7.78%
50.00m
Intel
70
SL+Gıdy
420.66
1.48%
23.05m
34.86
22.31%
6.06m
DIMES
35
RL+Grdy
421.24
1.11%
24.17m
38.24
14.78%
6.12m
DIFUSCO
19
SL+Grdy
424.56
0.33%
8.25m
36.55
18.53%
8.82m
T2T (Ours)
SL4Grdy
425.02
0.22%
8.12m
39.56
11.8%%
8.53m
Intel
70
SL+TS
38.80
13.43%
20.00m
DGL
7
SL+TS
37.26
16.96%
22.71m
LwD 72
RL++
422.22
0.88%
18.83m
41.17
8.25%
6.33m
Gelow/Nets
UL4S
423.54
0.57%
23.22m
41.14
8.53%
2.92m
DIFUSCO
19
SL+S
425.13
0.19%
26.32m
40.35
10.07%
32.98m
T2T (Ours)
SL4S
425.22
0.17%
23.80m
41.37
7.81%
29.73m
stands less sensitive to the quality of labels in training than other peer methods. It further demonstrates the generality of T2T especially when high-quality solution labels are not easily available.
4.3 Experiments for MIS
Datasets. Two datasets tested for the MIS problem following 770 72
19]. include SATLIB [73] and Erdös-Rényi (ER) graphs 77]. SATLIB contains SAT instances encoded in DIMACS CNF format, which are then reduced to MIS instances. ER graphs randomly generated with each edge maintaining a fixed probability of being present or absent, independently of the other edges. We adopt ER graphs of 700 800 nodes with the pairwise connection probability
35
0.15 15.
Following previous works 12 33 35 [9], we adopt three evaluation metrics to measure model performance: 1) Size: the average size of the solutions w.r.t. the corresponding instances, i.c. the objective. 2) Drop: the relative performance drop w.r.t. length compared to the optimal solution or the reference solution; 3) Time: the average computational time required to solve the problems.
Metrics.
Main Results. Table presents results. The baselines include state-of-the-an neural methods with greedy decoding and sampling decoding (x,), as well as exact solver Gurobi [66] and heuristic solver KaMIS (69] The solving time of Gurobi is set as comparable neural solvers, thus does not reach optimality. DIFUSCO and T2T are compared in the same conditions. The results of other baselines are quoted from 35 DIFUSCO and T2T adopt 50 and 20 inference steps, respectively. In the greedy decoding setting, compared to previous neural solvers, T2T improves the performance drop from 0.33% to 0.22% for SATLIB dataset and from 18.53% to 11.83% for ER-[700-800 dataset.
5 Conclusion and Future work
We have presented a principled learning paradigm for solving hard-constrained optimization problems specifically combinatorial optimization, which bridges the offline training with reference solution as supervision to the instance wise solving in testing which calls for more direct gradient feedback from the objective score. Experiments on TSP and MIS show the strong performance of our approach. With the potential generality, further validation across wider range of CO problems is the immediate further work, including those with general representing capabilities such as Mixed Integer Programming (MIP) and ML-dominant special problems like Quadratic Assignment Problem (QAP). Another promising future direction is to explore the potential of recent (scalable) graph as expressive encoder backhones for solving complex CO problems.
Transformers 75 76 77
10

---

References
[1] Y. Bengio, A. Lodi, and A. Prouvost, "Machine learning for combinatorial optimization: a methodological tour d' d'horizon." European Journal of Operational Research, 2021.
[2] Q. Cappart, D. Chételat, E. Khalil, A. Lodi, C. Morris, and P. Veličković, "Combinatorial optimization and reasoning with graph neural networks," arXiv preprint arXiv:2/02.09544, 2021.
[3] Zhang, C. Liu, X. Li, H.-L. Zhen, M. Yuan, Y. Li, and J. Yan, "A survey for solving mixed integer programming via machine learning," Neurocomputing, vol. 519, pp. 205-217, 2023.
[4] W. Guo, H.-L. Zhen, X. Li, W. Luo, M. Yuan, Y. Jin, and J. Yan. "Machine learning methods in solving the boolean satisfiability problem," Machine Intelligence Research, 2023.
[5] X. Chen and Tian, "Learning to perform local rewriting for combinatorial optimization." Advances in Neural Information Processing Systems, vol. 32, 2019.
[6] Y.D.. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, and S. Min, "Pomo: Policy optimization with multiple optima for reinforcement learning," Advances in Neural Information Processing Systems, vol. 33, pp. 21 18 188-21 198, 2020.
[7] S. Li. Z. Yan, and C. Wu, "Learning to delegate for large-scale vehicle routing," Advances in Neural Information Processing Systems, vol. 34, pp. 26 198-16822222 261,1, 2021.
[8] M. Kim, J. Park, and J. Park, "Sym-nco: Leveraging symmetricity for neural combinatorial optimization." arXiv preprint arXiv:2205. 13209, 2022.
[9] Y. Li, Y. Jia, W. Luo, H.-L. Zhen, X. Li, M. Yuan, and J. Yan, "Kissat adaptive restart, kissat cfexp: Adaptive restart policy and variable scoring improvement," Proceedings of SAT Competition, 2022.
[10] O. Vinyals, M. Fortunato, and N. Jaitly, "Pointer networks," Advances in neural information processing systems, vol. 28, 2015.
[11] R. Wang, J. Yan, and X. Yang, "Neural graph matching network: Learning lawler's ' quadratic assignment problem with extension to hypergraph and caltiple-graph) matching," IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 2022.
[12] W. Kool, H. Van Hoof, and M. Welling, "Attention, learn to solve routing problems!" arXiv preprint arXiv: 1803. 08475, 2018
[13] N. Karalias and A. Loukas, "Erdos goes neural: an unsupervised learning framework for combinatorial optimization graphs," Advances in Neural Information Processing Systems, vol. 33, pp. 6659-6672, 2020.
[14] S. Geisler, Sommer, J. Schuchardt, A. Bojchevski, and S. Günnemann, "Generalization of neural combinatorial solvers through the lens of adversarial robustness," in International Conference on Learning Representations, 2022.
[15) H. Lu, 7. Li, R. Wang, Q. Ren, X. Li, M. Yuan, J. Zeng, X. Yang, and J. Yan, "Roco: A general framework for evaluating robustness of combinatorial optimization solvers graphs," in The Eleventh International Conference on Learning Representations, 2023.
[16] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio, "Neural combinatorial optimization with reinforcement learning," arXiv preprint 1rXiv:1611.099// 2016.
[17] A. Hottung, Y.-D. Kwon, and K. Tiemnyy "Efficient active search for combinatorial optimization problems," arXiv preprint 2rXiv:2106.05126, 2021.
[18] H. Wang and P. Li, "Unsupervised learning for combinatorial optimization needs meta-learning." arXiv preprint M0Xi:2301.03111 2023.
[19] 7. Sun and Y. Yang, "Difusco: Graph-based diffusion solvers for combinatorial optimization," arXiv preprint arXi::2302.08224, 2023,

---

[20] G. Harshvardhan, M. K. Gourisaria, M. Pandey, and S. S. RRautaray, "A comprehensive survey and analysis of generative models in machine learning," Computer Science Review, vol. 38, p. 100285, 2020.
[21] T. Iqbal and S. Qureshi, "The survey: Text generation models in deep learning," Journal of King Saud University- Computter and Information Sciences, vol. 34, no. 6, pp. 15152228,, 2022.
[22] X. Guo and L. Zhao, "A systematic survey on deep generative models for graph generation," IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[23] A. Hottung, B. Bhandari, and K. Tierney "Learning latent search space for routing problems using variational autoencoders," " in International Conference on Learning Representations, 2021.
[24] Y. Li, X. Chen, W. Guo, X. Li, W. Luo, J. Huang, H.-I.. Zhen, M. Yuan, and J. Yan, "Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong grructue-hardneee aware baseline," in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2023.
[25] J. You, H. Wu, C. Barrett, R. Ramanujan, and J. Leskovec, "G2sat:
Learning generate sat
formulas," " in Advances in neural information processing systems, vol. 32, 2019.
[26] Z. Geng, X. Li, J. Wang, X. Li, Y. Zhang, and F. Wu, "A deep instance generative framework for milp solvers under limited data availability," arXiv preprint arXiv:2310.02807, 2023.
[27] X. Du, C. Wang, R. Zhong, and J. Yan, "Hubrouter: Learning global routing via hub generation and pin-hub connection," in Advances in Neural Information Processing Systems, 2023,
[28] R. Cheng, X. Lyu, Y. J. J. Ye, J. Hao, J. Yan, "The policy-gradient placement and generative routing neural networks for chip design," Advances in Neural Information Processing Systems, vol. 35, pp. 26 350-26 362, 2022.
[29] J. Sohl-Dickstii,, E. Weiss, N. Maheswaranathan, and S. Ganguli, "Deep unsupervised learning using nonequilibrium thermodynamics," in International Conference on Machine Learning, 2015, pp. 2256-2265.
[30] Austin, Johnson, Ho, D. Tarlow, and van den Berg. "Structured denoising diffusion models in discrete state-spaces," Advances in Neural Information Processing Systems, vol. 34, pp. 17 979 187-1799 993, 2021.
[31] E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, and M. Welling, "Argmax flows and multinomial diffusion: Learning categorical distributions," Advances in Neural Information Processing Systems, vol. 34, pp. 12 12454-12 465, 2021.
[32] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song, "Learning combinatorial optimization algorithms over graphs," Advances in neural information processing systems, vol. 30, 2017.
[33] C. K. Joshi, T. Laurent, and X. Bresson, "An efficient graph convolutional network technique for the travelling salesman problem," arXiv preprint arXiv:1906.0122 2019.
[34] Z.-H. Fu, K.-B. Qiu, and H. Zha, "Generalize a small pre-trained model to arbitrarily large tsp instances," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 8, 2021, pp. 7474-7482.
[35] R. Qiu, Sun, and Y. Yang. "Dimes: A differentiable meta solver for combinatorial optimization problems," arXiv preprint 10.04/2 2022.
[36] P. R. d O Costa, J. Rhuggenaath, Y. Zhang, and A. Akcay, "Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning," " in Asian Conference on Machine Learning, 2020, pp. 465-480.
[37] Y. Wu, W. Song, Z. Cao, J. Zhang, and A. Lim, "Learning improvement heuristics for solving routing problems," IEEE transactions on neural networks and learning systems, vol. 33, no. pp. 5057-5069, 2021.
12

---

[38] Q. Hou, J. Yang, Y. Su, X. Wang, and Y. Deng, "Generalize learned heuristics to solve large- scale vehicle routing problems in real-time," The Eleventh International Conference on Learning Representations, 2023.
[39] D. P. Kingma and M. Welling, "Auto-encoding variational bayes," in ICLR, 2014.
[40] Y. Li, Y. Mo, L. Shi, and J. Yan, "Improving generative adversarial networks via adversarial learning in latent space," in Advances in Neural Information Processing Systems, 2022.
[41] Y. Li, L. Shi, and J. Yan, "fid-gan: an iid sampling perspective for regularizing mode collapse." in International Joint Conference on Artificial Intelligence, 2023.
[42] J. Ho, A. Jain, and P. Abbeel, "Denoising diffusion probabilistic models," Advances in Neural Information Processing Systems, vol. 33, pp. 6840-6851, 2020.
[43] D. Zhang, H. Dai, N. Malkin, A. Courville, Y. Bengio, and L. Pan, "Let the flows tell: Solving graph combinatorial optimization problems with gflownets." arXiv preprint arXiv:2305.17010, 2023.
[44] Y. Bengio. S. Lahlou, T. Deleu, E. J. Hu, M. Tiwari, and E. Bengio, "Gflownet foundations," arXiv preprint arXiv:2111.09266 2021.
[45] D. Belanger, B. Yang. and A. McCallum, "End-to-end learning for structured prediction energy networks," in International Conference Machine Learning. PMLR, 2017, pp. 439-
[46] Y. Chen, Y. Shi, and B. Zhang, "Optimal control via neural networks: convex approach," arXiv preprint arXiv: 1805 1835, 2018.
[47] B. Amos, L. Xu, and J. Z. Kolter, "Input convex neural networks," in International Conference on Machine Learning. PMLR, 2017, pp. 146-155.
[48] Y. Song and S. Ermon, "Generative modeling by estimating gradients of the data distribution," " Advances in neural information processing systems, vol. 32, 2019.
[49] Song, C. Meng, and Ermon, "Denoising diffusion implicit models," arXiv preprint 2rX1v:2010.02502,, 2020.
[50] Y. Song and S. Ermon, "Improved techniques for training score-based generative models," Advances in neural information processing systems, vol. 33, pp. 12438-12444 448, 2020.
[51] A. Q. Nichol and P. Dhariwal, "Improved denoising diffusson probabilistic models," in Interna- tional Conference on Machine Learning, 2021, pp. 8162-8171.
[52] Dhariwal and A. Nichol, "Diffusion models beat gans on image synthesis," Advances in Neural Information Processing Systems, vol. 34, pp. 8780-8794, 2021.
[53] Ho and T. Salimans, "Classifier-free diffusion guidance," arXiv preprint arXiv:2207.12598. 2022.
[54] 7. Wang. J. Hunt, and M. Zhou, "Diffusion policies expressive policy class for offline reinforcement learning," in The Eleventh International Conference on Learning Representations, 2022.
[55] H. He, C. Bai, K. Xu, Z. Yang, W. Zhang, D. Wang, Zhao, and Li, "Diffusion model an effective planner and data synthesizer for multi-task reinforcement learning," in Advances in Neural Information Processing Systems, 2023.
[56] H. P. Wang, N. Wu, H. Yang. C. Hao, and P. Li, "Unsupervised learning for combinatorial opti- mization with principled objective relaxation," in Advances in Neural Information Processing Systems, 2022.
[57] M. J. Schuetz, J. K. Brubaker, and H. G. Katzgraber, "Combinatorial optimization with physics- inspired graph neural networks," Nature Machine Intelligence, vol. 4, no. 4, pp. 367-377, 2022.
13

---

[58] Y. LeCun, S. Chopra, R. Hadsell, M. Ranzato, and F. Huang, "A tutorial on smegg-bbsed learning," Predicting structured data, vol. 1, no. 0, 2006.
[59] A. Graikos, N. Malkin, N. Jojic, and D. Samaras, "Diffusion models as plug-and-play priors." arXiv preprint 2xXv:22006.09012, 2022.
[60] S. Lin and B. W. Kernighan, "An effective heuristic algorithm for the traveling-salesman problem," Operations research, vol. 21, no. 2. pp. 498-516, 1973.
[61] P. R. d. O. da Costa, J. Rhuggenaath, Y. Zhang, and A. Akcay, "Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning," arXiv preprint arXiv:2004.01608, 2020.
[62] D. Applegate, R. Bixby, V. Chvatal, and W. Cook, "Concorde tsp solver," 2006.
[63] K. Helsgaun, "An extension of the inn-kemighann-heisaan tsp solver for constrained traveling salesman and vehicle routing problems," Roskilde: Roskilde University, pp. 24-50, 2017.
[64] G. A. Croes, "A method for solving traveling-sabeel salesman problems," Operations research, vol. 6,
no. 6, pp. 791-812, 1958.
[65] X. Bresson and T. Laurent, "The transformer network for the traveling salesman problem," arXiv preprint (tt:::2003.00122 2021.
[66] Gurobi Optimization, "Gurobi optimizer reference manual," http://wwwwguurbb.com 2020.
[67] M. Deudon, P. Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau, "Learning heuristics for the isp by policy gradient," in International conference on the integration of constraint programming, artificial intelligence, and operations research. Springer, 2018. pp. 170-181.
[68] B. Hudson, Q. Li, M. Malencia, and A. Prorok, "Graph neural network guided local search for the traveling salesperson problem," arXiv preprint arXiv: 10.05291, 2021.
[69] S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck, "Finding near near-optimal indepen- dent sets scale," in 2016 Proceedings of the Eighteenth Workshop Algorithum Engineering and Experiments (ALENEX). SIAM, 2016, pp. 138-150.
[70] Z. Li, Q. Chen, and V. Koltun, "Combinatorial optimization with graph convolutional networks and guided tree search," Advances in neural information processing systems, vol. 31, 2018.
[71] M. Böther, O. KiBig, M. Taraz, S. Cohen, K. Seidel, and T. Friedrich, "What's wrong with deep learning in tree search for combinatorial optimization," arXiv preprint arXiv:2201.10494 2022.
[72] S. Ahn, Seo, and J. Shin, "Learning what defer for maximum independent sets," in International Conference on Machine Learning. 2020, pp. 134-144.
[73] H. H. Hoos and T. Stützle, "Satlib: An online resource for research on sat," Sat, vol. 2000, pp. 283-292, 2000.
[74] P. Erdös, A. Rényi al., "On the evolution of random graphs," Publ. Math. Inst. Hung. Acad. Sci, vol. 5, no. 1, pp. 17-60, 1960.
[75] Q. Wu, W. Zhao, Z. Li, D. Wipf, and J. Yan, "Nodeformer: A scalable graph structure learning transformer for node classification." in Advances in Neural Information Processing Systems, 2022.
[76] Q. WU, C. Yang, W. Zhao, Y. He, D. Wipf, and J. Yan, "DIFFormer: Scalable (graph) trans- formers induced by energy constrained diffusion," in International Conference on Learning Representations, 2023.
[77] Q. Wu, W. Zhao, C. Yang, H. Zhang, F. Nie, H. Jiang, Y. Bian, and J. Yan, "Simplifying and empowering transformers for garge-graph representations," in Advances in Neural Information Processing Systems (NeurIPS), 2023.
[78] Zhou, Y. Wu, W. Song, 7. Cao, and J. Zhang, "Towards ooni-generalizable neural methods for vehicle routing problems," arXiv preprint arXiv:2305. 2023.
14

---

Appendix
A Supplementary Experiments
Results on TSPLIB. We evaluate our model trained with random 100-node problems on real-worid TSPLIB instances with 50-200 nodes. The compared baselines include DIFUSCO and baselines listed in (68's Table 3. Table 0.133% optimality gap, 58.3% better than the best previous method. We also supplement the results (optimality drop) of DIFUSCO and T2T on large-scale TSPLIB benchmark instances with 200-1000 nodes, as shown in Table For each instance, we normalize the coordinates to [0,1] and solve with the solving algorithms.
T presents the results and shows T2T's superiority achieving merely
Table 6: Solution quality for methods trained random 100-node problems and evaluated TSPLIB instances with 50-200 nodes. The comparison includes baselines [68]'s Table 3. Results of DIFUSCO and T2T are based on 4x sampling decoding with 2OPT post-processing. Results of other baselines are from 668.
INSTANCES
AM
GCN
Learn2PPT
GNNGLS
DIFUSCO
T2T
eil51
16.767%
40.025%
1.725%
1.529%
0.314%
0.314%
berlin52
4.169%
33.225%
0.449%
0.142%
0.000%
0.000%
st70
1.737%
24.785%
0.040%
0.764%
0.172%
0.000%
ei176
1.992%
27.411%
0.096%
0.163%
0.217%
0.16%%
pr76
0.816%
27.793%
1.228%
0.039%
0.043%
0.039%
rat99
2.645%
17.633%
0.13%%
0.550%
0.016%
0. 0.000%
kroA 100
4.017%
28.828%
18.313%
0.728%
0.050%
0.000%
kraB 100
5.142%
34.686%
1.119%
0.147%
0.000%
0.000%
kroC 100
0.972%
35.506%
0.349
1.571%
0.000%
0.000%
kroD100
2.717%
38.018%
0.866%
0.572%
0.000%
0. 0.000%
kroE100
1,470%
26.589%
1.832%
1.216%
0.000%
O. 0.000%
rd100
3.407%
50.432%
1.725%
0.003%
0.000%
O. 0.000%
eil101
2.994%
26.701%
0.387%
1.529%
0.124%
0. 0.000%
lin
1.739%
34.902%
1.867%
0.606%
0.441 %
0.393%
pr107
3,933%
80.564%
0.898%
0.439%
0.714%
O. 155%
pr124
3.677%
14.14
10.322%
0.755%
0.997%
0.584% %
bier127
5.908%
45.561%
3.044%
1.948%
1.064%%
O. 171NK 8%
ch130
3. 3.182%
39.090%
0.709
3.519%
0.077%
0.077%
pr136
5.064%
58.673%
0.000%
3.387%
0.182%
O. 0.000%
pr144
7.641% %
55.837%
1.526%
3.581%
1.816%
0.000%
ch150
4.584%
49.743%
0,312
2.113%
0.473%
0. 0.324%
kro A50
3.784%
45.411%
0.724%
2.984%
0.193%
0. 0.19%
kroB 150
2.437%
56.745%
0.886%
3.258%
0.366%
0.02/ %
pr152
7.494%
33.925%
0.029%
3.119%
0.687%
0. 0.687%
u159
7.551 %
38.338%
0.054%
1.020%
0.000%
0.000%
1at
6,893%
24.968%
0.743%
1.666%
0.887%
0.018%
373.020%
62.351%
0.522%
4.772%
0.000%
0.000%
k2o0
7.106%
40.885%
1.441%
2.029%
0.259%
0.000%
kroB200
8,541 %
43.643%
2.064%
2.589%
0.171%
0.171%
Mean
16.767%
40.025%
1.725%
1.529%
0.319%
0.133 %
Generalization Results on Distribution Shift. The generalization results of the diffusion-base methods (c.g.. DIFUSCO and T2T) on the distribution (c.g., cluster, gaussian, etc., instead of uniform) are presented in Table, 8 and Table. The TSP data of different distributions are from [78).
Effeet of Number of Iterations. Table. 10 shows the results of T2T with varying #iterations. Each iteration contributes to a single process of solution improvement, and employing more iterations can lead to improved solutions. However, too many iterations could lead to additional computational overhead. As a result, we aim to strike balance in this trade-off and set #iterations to 3.
Effect of Graph Sparsification Hyperparameter k. Table. 10 shows the results of T2T with varying k. larger value of can yield improved results, yet it can also lead to increased computational overhead. Thus, we strike balance in this trade-off and set & to 50.
15

---

Table 7: Solution quality for methods trained on random 500-node problems and evaluated on TSPLIB instances with 200-1000 nodes. Results of DIFUSCO and T2T are based on 4x sampling decoding with 2OPT post-processing.
INSTANCES
DIFUSCO
T2T
INSTANCES
DIFUSCO
T2T
pr439
1.28%
0.26%
d493
0.00%
0.00%
pch442
0.00%
0.00%
p654
0.00%
0.00%
f1417
0.00%
0.00%
d657
0.00%
0.00%
tsp225
0.99%
0.59%
rat783
1.67%
1.22%
u724
0.00%
0.00%
1s225
0.32%
0.32%
pr299
0.57%
0.14%
lin318
0.30%
0.30%
rd400
0.12%
0.00%
u574
0.00%
0.00%
rat575
0.83%
0.26%
pr1002
2.21%
1,42%
a280
1.11%
0.00%
pr226
0.34%
0.22%
pr264
1.12%
0.48%
Mean
0.57 %
0.27 %
Table 8: Generalization results from the model trained with Uniform- 100 data.
Methods
Decoding
Uniform- 100
Gaussian- 100
DIFUSCO
Greedy
7.78, 0.20%
5.72, 0.72%
T2T DIFUSCO T2T
Greedy
7.76, 0.06%
5.69, 0.28%
Sampling
7.76, 0.00%
5.68, 0.09%
Sampling
7.76, 0.00%
5.68, 0.02%
B
Applicability of T2T
We provide summary concerning the types of problems that T2T can effectively manage:
Mandatory Requirements:
The decision variables are limited to a countable and finite set of values. Currently, we focus on binary decision variables and the model predicts heatmap for the solution. But it can be easily extended to prediction through the multinomial diffusion. Note that even binary variables can cover wide range of CO problems especially on graphs. since most problems can be attributed to edge-selecting problems like TSP, CVRP, and node-selecting problems like MIS, MAX Clique.
A problem-speciffe post-processing procedure is required to transform the prediction into feasible solutions. For problems featuring binary decision variables, this prereq- uisite be easily met with the greedy decoding strategy, which sequentially inserts variables (edges or nodes) with the highest confidence if there are no conflicts.
Nice-to-have Requirements:
The constraints can be transformed to some sort of penalty with meaningful gradient. While preferable to include constraint penalty term in Eq. 7, the utilization the optimization objective alone is also effective (as evidenced by the TSP results). This is due the diffusion's 's capacity to implicitly learn constraints.
C Proofs
Proposition 1. The optimizaaionn-efforeed denoising probability estimation Po(Xx-1|xx, G, v²) equals to
G))((" x,-1, G), where Z is a normalizing constant.
Proof. Since po (x Xx, G. y) estimates q(xt-1 1 G, y²) we aim to show q(xt-1 (xx,,,Gy G,y") ))² x q(x--1 (xe, G'p(y" Xt-1, G), such that as g(x{-1 |x,, G) can be readily estimated by ( G), o( x(x-1/xx, G. G.y")s neural estimation po po(x--1|x4 G,y") can be achieved by Zpo X1, (1) X;-1, G), where Z is normalizing constant.
16

---

Table 9: Generalization results from the model trained with Uniform-500 data.
Methods
Decoding
Uniform-500
Rotation-500
Explosion-500 500
Cluster3 20 -300
Cluster -30
DIFUSCO
Greedy
16.82, 1.63%
12.69, 2.44%
12.06, 2.80%
9.72, 2.64%
5,80, 3.09%
T2T DIFUSCO
Greedy
16.68, 0.78%
12.51, 1.00%
11.94, 1.76%
9,61, 1.49%
5.75, 2.17%
Sampling
16.68, 0.81%
12.60, 1.65%
11.94, 1.78%
9.62, 1.57%
5.75, 2.18%
T2T
Sampling
16,62, 0.42%
12.45, 0.48%
11.87, 1.18%
9.55, 0.85%
5.72, 1.67%
Table 10: TSP-500 Greedy results of the hyperparameter #iterations.
#iterations
0
3
5
10
Tour Length
16,813
16.705
16.683
16.678
16.669
Drop 1.59%
0.94%
0.80%
0.77%
0.72%
We first show that p(y" x,-1, G) does not depend on Xy:
ply" 1x, G) q(x: X 1, G) p(y"(xx11,,0 (x, G)
(14)
((xx Xx-1, G)
((x, (x- ply" G)
(15)
= =
(16)
Then the probability distribution ((x;-1 1xx,, G, y²) can be derived by:
9(x1-1 x,, G,y") 9(xx-1,Xx, X,, G,v")
(17)
q(x,, G,y*)
((x1-1, Xx, G, G,y²)
(18)
q(v" Xx, G) G)
q(v" (1'"1x:-1 X1, G) 1 G) G)
(19)
( |x,, ()) G)
g(v xt- () |x: G)
(20)
(0 ((,))x G)
qly q(y')x,, G) is not depend on x,-1, thus it can be regarded as constant. Now can obtain
(xx,118x, G))") x 1|x, () completing the proof.
D Discussion from Another Aspect: Constructive and Improvement Solvers
Existing CO solvers including both traditional and emerging ML-based methods, generally can be categorized into two groups as summarized in detail in Table [2] Constructive solvers solve the problem from scratch in one shot or multiple steps, and the algorithm ends once a complete solution is obtained. However, effectively enhancing the final solution quality (e.g. the objective score) while ensuring the constraints can be challenging for constructive solvers due to the absence of explicit reference to complete solutions (as the constraints are often obeyed globally across the dimensions of the solution). While in contrast, improvement solvers yield and maintain series of complete solutions during the improvement procedure to optimize (namely minimize) the objective in a score decreasing trend (with fluctuation). Compared with constructive solvers, improvement saurch-based) 37: 7 38) seek enhanced solution by iteratively performing local search within its neighborhood. The algorithm pipelines generally involve selecting specific regions and locally optimizing sub-solutions. This paradigm often offers better tractability and more direct correlation to objective score thanks to the explicit involvement of the objective and accessibility of complete solutions. While improvement-brst based solvers dominate in traditional heuristics (e.g., LKH [60] 63)), for learning class methods, the constructive solvers remain relatively major in number, given their more direct compatibility with network prediction tasks.
solvers [36] 37 5
For constructive ML-solvers, the training procedures can be classified into reinforcement learning (RL) and supervised learning (SL). RL methods [12] 6. g try directly optimize the objective
17

---

Table 11: TSP-500 Greedy results of the graph sparsification hyperparameter
k
10
50
100
200
Tour Length
16,687
16.681
16.678
16.674
Dropt
0.83%
0.79%
0.77%
0.74%
Table 12:
Constructive and improvement solvers. Sol. Dist.: solution distribution learning capability;
LS: using local search scheme. A constructive solver can be combined with a search- based solver, where the latter is responsible for the search component being not part of the constructive approach.
Neural solver
Paradigm
Training
Sol. Dist.?
LS?
AM
12
Constructive Constructive
Reinforce
No
No
POMO 6
Reinforce
No
No
Sym-NCO
88
Constructive
Reinforce
No
No
GCN
33
Constructive
Supervised
No
No
DIMES
355
Constructive
Reinforce
No
No
NeuRewriter [5
Improvement Improvement Improvement Improvement
Reinforce
No
Yes
Learning 2OPT
[36
Reinforce
No
Yes
Learnddelegate 7
Reinforce
No
Yes
TAM 38
Reinforce
No
Yes
CVAE-Opt
Constructive
Supervised Supervised
Yes
No
NeuRouter
2
Constructive
Yes
No
DIFUSCO
19
Constructive Improvement
Supervised
Yes
No
T2T (ours)
Supervised
Yes
Yes
function, but since a complete solution not obtained until the end, the intermediate process lacks valid reference. SL methods [33] solutions. The lack of objective awareness and local search procedures limits their ability to surpass the supervised solvers. The training procedures of current improvement ML-solvers based on RL.
35 19 typically fit the network prediction the reference
currently falls into subelass of constructive solvers. Gener- ative modeling for CO currently falls into subelass of constructive solvers, which leverages the powerful expressive and modeling capabilities of generative models, e.g.. VAE [23 and the diffusion model 19 However, as mentioned above the model lacks awareness of the optimization objective and does not introduce a search procedure to fully utilize the estimated solution distribution. In contrast the constructive way for CO problem solving, T2T serves as improvement solver the strong compatibility between the diffusion model and the diffuse-and -nd--noo--dee local search paradigm with objective feedback the loop. In our approach, generative diffusion model and local search both used (which is the first time to our best knowledge), in a complementary and synergistic way to achieve state-of-the-att performance in both objective score and solving time. Compared existing improvement solvers, such design facilitates parallel optimization across multiple sub-regions of the entire solution, greatly improving efficiency while also eliminating the need for the iterative selection of optimization regions.
Generative modeling for CO 23
E Network Architecture Details
E.1 Input Embedding Layer
Given node vector E Nx2 weighted edge vector E R denoising timestep / { TM }. where N denotes the number nodes in the graph, and E. denotes the number of edges, we compute the sinusoidal features of each input element respectively:
18

---

3; concat Ti,1)
(21)
Vig
Ji.j
Ji.j
Ji.j
Fi.
Fi.j
Ji.j concat
sin
cos
sin
cos
Sin
cos
(22)
T
T
T
T
T
T
6
E
Ei
é concat
sin
T
U
COS
T
sin
T
COS
T
Sin
T
COS
T
(23)
t
1
t
concat
sin
CO8
sin
C0S
sin
COS
(24)
T
T
T
T
T
T
where d is the embedding dimension, T is large number (usually selected as 10000), concat denotes concatenation.
Next, we compute the input features of the graph convolution layer:
5. WP4;
(25)
6
0 W
(26)
8 = (R(LL((()3)))
(27)
where e Rd, de is the time feature embedding dimension. Specifically, for TSP, the embedding input edge vector is weighted adjacency matrix, which represents the distance between different nodes, and is computed as above. For MIS, we initialize e to a zero matrix Bxd
E.2
Graph Convolution Layer
Following
33
the cross-layer convolution operation is formulated as:
2
I+1 = a! ReLL(BN(W/a) + Σ Enl o W) j
(28)
J+1 = -CL- + Win W
(29)
a(et)) th Epmn +e
(30)
where 2/ and ely denote the node feature vector and edge feature vector layer 1, W1, Ws hhxh denote the model weights, n/y denotes the dense attention map. The convolution operation integrates the edge feature to accommodate the significance of edges in routing problems.
For TSP. aggregate the timestep feature with the edge convolutional feature and reformulate the update for edge features as follows:
+ ctty ReLU(BN(WWee, Wla! Wia()) + ((
(31)
For MIS, we aggregate the timestep feature with the node convolutional feature and reformulate the update for node features as follows:
[+1 (e
Σnh, jNs
nly o w(rd) (C(R)LU(())
(32)
E.3
Output Layer
The prediction the edge heatmap in TSP and node heatmap in MIS as follows:
eijj = (ofmmx(oorm(elllWWW...
(33)
2; Softmax(nomm(eLl
(34)
where L is the number of GCN layers and norm is layer normalization.
19

---

E.4 Hyper-parameters
For both TSP and MIS tasks, we construct 12-layer GCN derived above. We set the node, edge, and timestep embedding dimension d = 256, 128 for TSP and MIS tasks, respectively.
F Fast Inference for Discrete Diffusion Models
The technique of denoising diffusion implicit models (DDIMs) 49 is introduced for accelerating inference and solution reconstruction. Let F1.r denotes the latent variables and {TI,..., -as } is one increasing subset of time sequences (1....,,7) 7. TM T for the inference processes and o? for the reconstruction processes. The diffusion processes can be generated to a class non-Markovian processes with the training objective, where the inference processes traverse only subset of latent variables. The inference processes are reformulated as:
(1x--1X-,30) = ((x7|x+-11 1,00 (x7 q(x,
(35)
x-Q7 S X Xr-111
Cat X
Xy Q
For both TSP and MIS tasks, adopt the cosine denosing scheduler such that 7; |cos for some constant c.
[1- viet .T)
G Experimental Details
G.1 Training Resource Requirement
Table 13:
Details about the training resource requirement T2T framework. The results are calculated on A100 GPUs.
provide the details about the offline training resource requirement of T2T framework in Table 13 The results are calculated on A100 GPUs. For comparison reference: AM [12) requires 1 128M
instances generated on the fly for training TSP-100, and requires 45. 8h on 1080Ti GPUs;
POMO [6] requires 200M instances generated the fly for training TSP-100, and it requires 1 week on a single Titan RTX; Sym-NCO [8] based on POMO requires weeks on single A100,
Sym-NCO 8 based AM requires days 4 A100 GPUs.
Problem Scale
Dataset Size
GPU
GPUs
4 GPUs
GPU Mem
TSP-50
1,502 k
56h 24m
30h 49m
19h 8m
13.2 GB
TSP-100
1,502
206h 20m
109h 45m
59h 55m
24.0 GB
TSP-500
128 k
64h 26m
34h 37m
22h 46m
19.1 GB
TSP-1000
64 k
123h 31m
65h 46m
38h 35m
35.8 GB
G.2 Hyperparamters
We conduct experiments TSP and MIS benchmarks with methods and compare the performance with SOTA barming-based solvers, heuristics, and exact solvers. We select hyperparameters to balance the inference time and the solution quality. Specifically, the inference time of our method is approximate with other learning-basse frameworks. For each benchmark, we adopt 20 inference steps and 10 objective-guided denoising steps for reconstruction, which involves iterations and selects the optimal solutions. The disruption ratio associated with each benchmark is listed in Table. 14
Table 14: Disruption Ratio for each benchmark.
Benchmark
TSP-50
TSP-100
TSP-500
TSP-1000
ER-[700-800]
20

---

G.3 Baseline Settings
G.3.1 TSP Benchmarks
TSP-50/100. For TSP-50 and TSP-100, we compare our proposed T2T with 10 baselines, including
one exact solver Concorde [62] two heuristic solvers 2OPT 64 and Farthest Insertion, and 7
learning-based solvers, i.e., AM 12, GCN (33, Transformer 665 POMO [6]. Sym-NCO (8)
Image Diffusion [59] and DIFUSCO [19. The post-processing includes greedy sampling and 2OPT
refinement. To ensure a fair comparison with similar runtimes, we set the number of inference steps for DIFUSCO to 120.
TSP-500/1000, For TSP-500 and TSP- corde [62] and Gurobi [66]. 2 heuritics solvers LKH-3 [63 and Farthest Insertion, and learning-
compare our method with exact solvers Con-
based methods including EAN [67]. AM (2). GCN (33, POMO+EAS (17). DIMES [35] and DIFUSCO [9]. The satriing-based methods can further be categorized into supervised learning (SL) and reinforcement learning (RL). The post-processing includes greedy sampling (Grdy, G), multiple sampling (S), 2OPT refinement (2OPT), beam search (BS), active search (AS), and their combinations. To ensure fair comparison with similar runtimes, we set the number of inference steps for DIFUSCO to 120.
G.3.2 MIS Benchmarks
We evaluate our method two benchmarks, namely SATLIB and ER-[700-800). For both bench- marks, we compare T2T with one exact solver Gurobi [66]. one heuristic solver KaMIS [69] and 5 learning-base frameworks Intel [70], DGL [70]. LwD [72]. DIMES [35] and DIFUSCO [19]. The post-pre prsceercnssiig includes greedy sampling (Grdy) and tree search (TS). Specifically, we set the inference steps 50 for DIFUSCO on both benchmarks.
G.4 Graph Sparsification
TSP, the number of edges the graph increases quadratically with the number of nodes, which poses scalability challenges. To address this, we adopt graph sparsification by limiting each node to connect only with its k nearest neighbors (KNN) based on Euclidean distance. Specifically, we set k 50 for TSP-500 and TSP-1000.
G.S Visualization
Fig. 6 visualizes the specific process T2T with 5 rounds of gradient search on TSP-50.
Paseprncssing
Round
Round
Round
Round
Round
Figure 6: The visualization of T2T solving TSP-50, corresponding to the orange part in Fig.
21


Reviews:
[{"review_id": "vMQPzgWHC3", "reviewer": "Reviewer_uUyD", "summary": "The paper presents T2TCO, a new approach for neural combinatorial optimization based on using gradient-based search in the solution  space during test time. The proposed approach leverages generative modeling (specifically diffusion) for graduated solution improvement but employs an additional energy-based model (EBM) to evaluate the compatibility of solutions with the optimal solution. Experiments show improvement over DIFUSCO (similar generative modeling approach but without test-time gradient-based search) and a range of baselines in two popular CO benchmarks: TSP and MIS.", "questions": "I would appreciate the authors' response on my main concerns listed above.", "limitations": "While there is no explicit discussion of limitation, I have no concerns regarding the impact of the manuscript.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Interesting work suggesting a new approach for ML4CO. The approach extends DIFUSCO (or similar approaches) with gradient-based search during test time to improve performance.\n- Experiments show the proposed approach outperforms the baselines. In particularly, it outperforms the recent DIFUSCO which it extends with gradient-based test-time search.", "weaknesses": "- Related literature: there are several relevant works that are not being mentioned and discussed. First, gradient-based search in prediction/inference (test-time) for different purposes has been proposed before in a range of settings. e.g., in [1], [2], [3]. While using it in combinatorial optimization is new (to my knowledge), the principles have been proposed before and related previous works should be mentioned and similarities and differences highlighted. Second, using diversity-focused solution generation (test-time) in combinatorial problems has been studied before e.g., in [4] and [5]. Third, introducing constraints to gradient-based search by continuous relaxations has been done before, e.g., in [6] and [7].\n\t* related to the above, it is important to mark what parts of the work is based on previous work. In particular, it sounds like Section 3.2 is primarily based on DIFUSCO, which if indeed is the case, should be clearly stated.\n\n- Experiments: (1) No experiments on generalization: it sounds like each group of instances (e.g., TSP-100) was trained and tested on instances from the same size. Previous work on ML4CO has often looked at the ability of networks trained on smaller sizes to generalize well for larger problems (including in DIFUSCO [8]). It is not clear how the proposed gradient-based search approach works in such settings. (2) While experiments show consistent improvement over previous SOTA (usually DIFUSCO), the improvement is often somewhat modest (except for MIS with ER graphs) and there is no clear analysis to demonstrate where the gain are comping from (e.g., is it consistent but modest gain across all instances vs. a small number of instances that got significant boost).\n\n- The proposed method requires manual relaxation of constraints to penalty terms and therefore is not clearly generic to all CO problems (and it is not clear that it will work well across relaxations). This is not a critical issue but it would be interesting to cover a set of popular types of constraints and their relaxations and make sure they are tested. Potentially, this can be based on previous literature (e.g., [6] where a list of continuous relaxations for popular hard constraints is provided).\n\n- Not a critical issue, but the paper seems to build extensively on DIFUSCO that, as far as I can see, is not yet been published in a peer-reviewed venue.\n\nMinor:\n- line 51: desired to estimate -> \"designed to estimate\"?\n- line 299: I think \"TSP-50\" here should be \"TSP-500\"\n- line 310: \"T2TCO is not that sensitive to the quality of labels in training\" - I think this statement is too strong given that the quality of labels seems to have significant impact on the performance (it may be that it is less sensitive than other approaches but it is still sensitive).\n\n\n[1] Belanger, D., Yang, B., & McCallum, A. (2017, July). End-to-end learning for structured prediction energy networks. In International Conference on Machine Learning (pp. 429-439). PMLR.\n\n[2] Chen, Y., Shi, Y., & Zhang, B. (2019, February). Optimal Control Via Neural Networks: A Convex Approach. In International Conference on Learning Representations.\n\n[3] Amos, B., Xu, L., & Kolter, J. Z. (2017, July). Input convex neural networks. In International Conference on Machine Learning (pp. 146-155). PMLR.\n\n[4] Cohen, E., & Beck, J. C. (2021). Heavy-Tails and Randomized Restarting Beam Search in Goal-Oriented Neural Sequence Decoding. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings 18 (pp. 115-132). Springer International Publishing.\n\n[5] Bai, Y., Zhao, W., & Gomes, C. P. (2021). Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems. arXiv preprint arXiv:2102.03002.\n\n[6] Chen, Di, et al. \"Deep reasoning networks for unsupervised pattern de-mixing with constraint reasoning.\" International Conference on Machine Learning. PMLR, 2020.\n\n[7] Chen, Di, et al. \"Automating crystal-structure phase mapping by combining deep learning with constraint reasoning.\" Nature Machine Intelligence 3.9 (2021): 812-822.\n\n[8] Sun, Z., & Yang, Y. (2023). Difusco: Graph-based diffusion solvers for combinatorial optimization. arXiv preprint arXiv:2302.08224.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thorough review and valuable comments. We are encouraged with your acknowledgement to our idea, experiments and contribution to the ML4CO community. Below we respond to your specific comments.\n\n**Q1: Some related works are missed.**\n\nThanks for sharing these related works. We will disscuss these works in our new version.\n\nWe would like to note that the mentioned principles can be somehow general under various settings. For instance, a broad spectrum of diffusion models and energy-based models fall within the overarching principle of employing gradient-based sampling during the inference phase. While these approaches share a common design feature, they can technically exhibit significant variations from one another, and the uniqueness and novelty inherent in each of these methods could still be appreciated.\n\nWhen compared to the mentioned related works, including SPENs [1], ICNNs [2], or even general score-based (diffusion) models, concerning the gradient utilization in the test phase, T2TCO similarly train a network to estimate the score funtion $\\nabla_x \\log(q(x_t))$, which can be seen as the gradient of some sort of energy function. Subsequently, the sampling in the test phase utilizes the estimated scores to sample a valid generation. However, T2TCO goes a step further by incorporating an explicit objective optimization term during the test phase. The guidance of the trained network and the guidance from the objective gradient are organically integrated to enable optimization in the solution space. When it comes to specific framework designs, T2TCO is obviously different from the above methods with the sequential local improvement machanism.\n\n**Q2: It sounds like Section 3.2 is primarily based on DIFUSCO, which if indeed is the case, should be clearly stated.**\n\nActually, we have already marked in the corresponding section when we adopt conclusions or modeling paradigms from previous works. The diffusion modeling paradigm in Sec. 3.2 follows DIFUSCO [3] as marked in Line 149, while we differ DIFUSCO by explicitly modeling the solving task as a conditional generation task. Thus the derivation in Sec. 3.2 is based on the conditional context of diffusion models. We will enhance the clarity of our references in the new version of our work.\n\n\n**Q3: No experiments on generalization.**\n\nThanks for the comment. We have supplemented the generalization results in the general response.\n\n**Q4: While experiments show consistent improvement over previous SOTA, the improvement is often somewhat modest. Where the gains are coming from?**\n\nFirstly, we would like to emphasize that the performance gain achieved by T2TCO over the previous methods is actually significant among the SOTAs, rather than minor. In the TSP experiments, we observed an average performance gain of 49.3% across various settings compared to the previous state-of-the-art. Although the absolute numerical improvement might not appear exceedingly large, it is important to consider that the previous SOTA methods had already achieved high quality results (with less than 1% optimality drop). Please kindly note that reviewers p83a, uaDN, and gU16 all acknowledge the empirical results of T2TCO.\n\nFor the performance gains on individual instances, please see Table 5 in the supplemented pdf for a direct perception, where we list the model performance on each instance of TSPLIB dataset. Since DIFUSCO have reached or approached optimality in partial instances, the performance gains are distributed among other instances with certain variation.\n\n\n**Q5: Manual relaxation of constraints to penalty terms is not clearly generic to all CO problems. This is not a critical issue but it would be interesting to cover a set of popular types of constraints and their relaxations and make sure they are tested.**\n\nThanks for providing the related work and offering the advice. Actually, T2TCO is designed to learn the constraints via latent space learning (i.e. generative modeling) which allows the loss for gradient computing in test time. It only involves the raw objective function as we did for the TSP case (see Line 202-203). We optionally add the constraint penalty term for the MIS case, which is designed mainly as an auxiliary support to latent space learning for constraints.\n\n**Q6: Minor issues and suggestions.**\n\nWe sincerely appreciate your thorough review. We will revise the manuscript accordingly to elevate it into a more refined paper.\n\n---\nWe hope this response could help address your concerns, and wish to receive your further feedback soon.\n\n---\n\n**Reference:**\n\n[1] End-to-end learning for structured prediction energy networks. ICML 2017.\n\n[2] Input convex neural networks. ICML 2017.\n\n[3] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. arXiv 2023."}, {"review_id": "WwOethemRa", "reviewer": "Reviewer_p83a", "summary": "The paper proposes a training to testing (T2TCO) framework to better align with the goal of combinatorial optimization (CO) problems, instead of pursuing the average expected performance, Real-world CO problems care more about instance-wise optimal solution. And thus, the paper first models the solution distribution with generative diffusion model and further conducts gradient search during testing to fine-tune the results. The framework design is novel, interesting, and sound. Experiments show the significant superiority of the framework.", "questions": "1.\tIs there any comparison on the training resource requirement / training time between T2TCO and other state-of-the-art methods listed in the paper? Could the authors provide some experiment data on that to give the readers a feeling about the training difficulty of the framework? (e.g. How many GPU/CPU hours, how much space, how many data does T2TCO require to converge, how about the other methods listed in the paper?)", "limitations": "The motivation is practical, the framework is novel, interesting and the methodology is sound. Therefore, I omit the limitation of this paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written. The motivation of the paper aims towards the goal of per-instance optimality for CO problems and introduces a novel T2TCO framework to resolve the problems. The gradient-search on each testing instance requires no longer fine-tuning the parameters of the model, which is also an interesting improvement.\nThe paper conducts experiments on two representative CO problems and both achieves better results than the state-of-the-art methods.\n", "weaknesses": "The only concern I could think about is the cross-domain generalization ability or even the in-distribution generalization ability of the supervised learning framework for CO problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable comments and for acknowledging the motivation practicality, framework novelty, and methodology soundness of our paper. Below we respond to your specific comments. Since your concerns are representative and common, we have discussed them mainly in the general response.\n\n**Q1: Cross-domain generalization ability evaluation.**\n\nThanks for the comment. We have supplemented the generalization results in the general response.\n\n**Q2: More details about the training difficulty of the framework, e.g., the training resource requirement, training time, and data requirement.**\n\nWe have provided the details about the offline training resource requirement of T2TCO framework in the general response. \n\n\n---\nWe hope this response could help ease your concern and wish to receive your further feedback soon."}, {"review_id": "0zJ0d0UfaF", "reviewer": "Reviewer_uaDN", "summary": "This paper proposed a diffusion model based solution distribution learning method for combinatorial optimization. The main novelty is that a search mechanism is proposed, which uses the learned distribution to conduct a gradient based search for each instance where the gradient is computed w.r.t the optimiztion objective function. Comparing with existing testing-time gradient update methods such as active search and meta-learning, this method does not need to update model parameters, hence could be more efficient. Experiments on two graph problems TSP (up to 1000 nodes) and MIS show that the proposed method outperforms recent neural CO methods. ", "questions": "1. What kind of problems can the proposed approach solve? Specifically, what kind of variables and constraints, and is it easy to design a problem-specific post-processing procedure?\n\n2. How is the diffusion model in Section 3.2 different from the one in Difusco [19]?\n\n3. Some questions about design and implementation:\n\na. For TSP, why and how is 2OPT applied? It looks like 2OPT is independent from the proposed gradient search mechanism. In this case, it is a general solution improvement technique and should be applied to other baselines for fair comparison. Moreover, better solution quality with 2OPT is not suprising and does not help in justifying the contribution of the proposed method.\n\nb. The authors state that \"For gradient search, T2TCO generally involves 3 iterations with 10 guided denoising steps for each\". Why you need 3 iterations and how about the performance of only 1 iteration? How do you perform the 3 iterations, independntly and then picking the best solution?\n\nc. The authors used k=50 for graph sparsification. How sensitive does the proposed method w.r.t. to k?", "limitations": "As mentiond above, this paper lacks a discussion on the applicability of the proposed approach, i.e. it is suitable for what kind of problems. The authors also did not explicitly describe the limitations of the proposed method.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of using learned distribution to perform search is interesting and novel as far as I know.\n\n2. Empirical performance on two important problems TSP and MIS is impressive.", "weaknesses": "1. While the paper is interesting, a weakness is that the authors did not clearly state what assumptions they made, or the proposed approach is suitable in solving which kinds of problems. For example:\n\na. The decision variables are binary. Though it is possible to transform non-binary problems into binary ones, a large number of variables could be involved, making the proposed approach impractical. \n\nb. The constraints can be transformed to some sort of penalty with meaningful gradient.\n\nc. A problem-specific post-processing procedure is needed to transform the prediction into feasible solutions.\n\nThe authors only evaluate the proposed method on two simple problems TSP and MIS, which satisfies the above conditions. But it is important to demonstrate its effectiveness on more challenging and practical problems. \n\n2. The distribution learning method in Section 3.2 heavily relies on [19]. The proof of Proposition 1 is adapted from [39]. The authors should be precise about what are the novel techniques and which parts are borrowed from existing works. \n\n3. Some design and implementation details lacks explanation. Please see the below questions.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable comments, constructive advice, and recognition of our idea and empirical results. Below we respond to your specific comments.\n\n**Q1: What kind of problems can the proposed approach solve? Specifically, what kind of variables and constraints, and is it easy to design a problem-specific post-processing procedure?**\n\nWe sincerely appreciate your valuable summary concerning the types of problems that T2TCO can effectively manage. We would like to reorganize it and provide explanations as follows:\n\nMandatory Requirements:\n1. The decision variables are limited to a countable and finite set of values. Currently, we focus on binary decision variables and the model predicts a $N\\times 2$ heatmap for the solution. But it can be easily extended to $N\\times k$ prediction through the multinomial diffusion. Note that even binary variables can cover a wide range of CO problems especially on graphs, since most problems can be attributed to edge-selecting problems like TSP, CVRP, and node-selecting problems like MIS, MAX Clique.\n2. A problem-specific post-processing procedure is required to transform the prediction into feasible solutions. For problems featuring binary decision variables, this prerequisite can be easily met with the greedy decoding strategy, which sequentially inserts variables (edges or nodes) with the highest confidence if there are no conflicts.\n\nNice-to-have Requirements:\n1. The constraints can be transformed to some sort of penalty with meaningful gradient. While it is preferable to include a constraint penalty term in Eq. 7, the utilization of the optimization objective alone is also effective (as evidenced by the TSP results). This is due to the diffusion's capacity to implicitly learn constraints.\n\n\n**Q2: The authors should be precise about what are the novel techniques and which parts are borrowed from existing works.**\n\nOur method is technically based on the diffusion model as the implementation foundation inspired by DIFUSCO [1]. Thus it is unavoidable to follow the diffusion modeling design in the methodology with DIFUSCO [1], whose main idea is to learn the solution distribution given an input instance using diffusion. However, the proposed framework including the test-stage gradient-based search with instance-wise objective feedback and the sequential local improvement mechanism obviously extends beyond DIFUSCO, as also evidenced by the empirical results.\n\nIndeed, we have already marked in the corresponding section when we adopt conclusions or modeling paradigms from previous works. The diffusion modeling paradigm in Sec. 3.2 follows DIFUSCO [1] as marked in Line 149, while we differ DIFUSCO by explicitly modeling the solving task as a conditional generation task. Thus the derivation in Sec. 3.2 is based on the conditional context of diffusion models. Prop. 1 is adapted from [39] as marked in Line 205, which we utilize as an existing conclusion to incorporate explicit objective optimization in generation.\n\nWe will enhance the clarity of our references in the new version of our work.\n\n\n**Q3: For TSP, why and how is 2OPT applied? 2OPT should be applied to other baselines for a fair comparison.**\n\n2OPT is indeed independent from the proposed gradient search mechanism as a general solution improvement technique. We have supplemented the experiments that apply the 2OPT solution improvement technique to other main baselines in original Table 1 and 2 for fairer comparison. Please refer to the general response.\n\n**Q4: Why do you need 3 iterations and how about the performance of only 1 iteration? How do you perform the 3 iterations?**\n\nOn one hand, each iteration contributes to a single process of solution improvement, and employing more iterations can lead to improved solutions. On the other hand, too many iterations could lead to additional computational overhead. As a result, we aim to strike a balance in this trade-off and have opted to set the iteration number to 3.\n\nWe supplement TSP-500 Greedy results of the hyperparameter #iterations below.\n\n| #iterations | Tour Length $\\downarrow$ | Drop $\\downarrow$ |\n| ------ | ------- | ---- |\n| 0  | 16.813      | 1.59% |\n| 1  | 16.705      | 0.94% |\n| 3  | 16.683      | 0.80% |\n| 5  | 16.678      | 0.77% |\n| 10 | 16.669      |  0.72% |\n\n\nThe iterations are performed sequentially, where each iteration is based on the previous iteration's result to improve. As claimed in Line 230-232, each iteration involves adding a certain degree of noise to disrupt the structure, denoising with objective gradient guidance to obtain a lower-cost soft-constrained solution, and subsequently post-processing to decode a feasible solution.\n\n\n**Q5: How sensitive does the proposed method w.r.t. to graph sparsification hyperparameter $k$?**\n\nWe supplement TSP-500 Greedy inference results of graph sparsification hyperparameter $k$ below.\n\n| $k$ | Tour Length $\\downarrow$ | Drop $\\downarrow$ |\n| -- | --- | --|\n| 10  | 16.687      | 0.83% |\n| 50  | 16.681      | 0.79% |\n| 100  | 16.678      | 0.77% |\n| 200  | 16.674      | 0.74% |\n\nA larger value of $k$ can yield improved results, yet it can also lead to increased computational overhead. Thus, we strike a balance in this trade-off and set $k$ to 50.\n\n---\nWe hope this response could help address your concern, and wish to receive your further feedback soon.\n\n---\n\n**Reference:**\n\n[1] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. arXiv 2023."}, {"review_id": "XKkamuzYBW", "reviewer": "Reviewer_gU16", "summary": "This paper proposes a novel framework, T2TCO, for solving combinatorial optimization problems. Specifically, it trains a generative model (i.e., discrete diffusion solver from [1]) to estimate the distribution of high-quality solutions for each instance, and, during testing, conducts an effective local search (i.e., iterative objective-aware denoising) guided by the gradient feedback within the estimated solution space. The experiments are conducted on TSP and MIS to demonstrate the superiority over previous SOTA methods. ", "questions": "* Do you plan to release the source code during the rebuttal period?\n* Has a similar idea (to the one in Section 3.3.1) been proposed in other domains (e.g., computer vision)?\n* Could you discuss further the objective function in Eqs. (6)-(7)? For example, why not use Eq. (1) in [1]?\n* Why the energy function is designed as Eq. (10)?\n* In Eq. (12), why $-\\log\\nabla_{x_t}Z$ is removed? It seems that $Z$ is also a function of $x_t$.\n* In line 224, is the negative sign missing in the exponentiation, i.e., $\\exp(-\\cdots)$?\n* The authors mention that $x_{t-1}$ is not accessible at step $t$. However, the approximation of $p(y^*|x_{t-1},G)$ still depends on $x_{t-1}$ (in line 224). I'm confused about it. Could you explain it further?", "limitations": "Limited scope and training efficiency.\n\nNo negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The writing of this paper is good. The motivation of the proposed method is clear. The drawbacks of previous tailored search methods in the test phase (i.e., active search or meta-learning needs to update model parameters), and that of the constructive diffusion solver [1] (i.e., without explicitly considering the optimization of CO objective during denoising) are discussed clearly.\n\n* The proposed method seems to be sound and novel. This paper uses the discrete diffusion model from [1] to model the high-quality solution distribution for each instance. The novelty of the proposed T2TCO could be mainly attributed to the objective-aware denoising process $p_{\\theta}(x_{t-1}|x_t,G,y^*)$ with gradient feedback (see Section 3.3.1), along with its theoretical analyses.\n\n* The empirical results are good, achieving SOTA on TSP and MIS.", "weaknesses": "* The proposed method is only applicable to diffusion-based methods [1], which may limit the scope of this paper. Moreover, it is an incremental work upon DIFUSCO [1].\n* Computational Complexity:\n  * The training cost of the diffusion model is extremely high, requiring **four A100 GPUs**.  It would be an interesting direction on improving the efficiency of the diffusion-based models for COPs.\n  * Could you provide further details about the needed training time (if training on a single GPU) and GPU memory?\n  * How about the training and inference complexity compared to DIFUSCO [1] (e.g., given the same number of sampling steps)?\n* Empirical Evaluation:\n  * How about the performance if using Monte-Carlo Tree Search (MCTS) [2] as the post-inference decoding?\n  * Any training setups for baselines? POMO [3] could achieve 0.03\\% and 0.14\\% on TSP50 and TSP100, respectively, while you report 0.64\\% and 1.07\\% in Table 1. These differences are not negligible. \n  * How about the generalization performance? DIFUSCO [1] has conducted the generalization study in their empirical analyses. Moreover, recent works [4, 5] consider the generalization study of neural (TSP) solvers across both size and distribution. It is interesting to see how your method performs in this setting.\n  * The detailed results on the classical benchmark dataset (e.g., TSPLIB [6]) are needed for both T2TCO and DIFUSCO.\n* Minor:\n  * In line 96, \"autoregressive\" -> \"construction\".\n  * In line 113, \",T2TCO\" -> \", T2TCO\".\n  * In line 170, \"$Cat$\" -> \"Cat\".\n  * In line 220, \" Note\" -> \"Note\"; \"to\" -> \"the\".\n\n[1] DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. In arXiv:2302.08224.\n\n[2] Generalize a small pre-trained model to arbitrarily large tsp instances. In AAAI 2021.\n\n[3] POMO: Policy optimization with multiple optima for reinforcement learning. In NeurIPS 2020.\n\n[4] On the generalization of neural combinatorial optimization heuristics. In ECMLPKDD 2022.\n\n[5] Towards Omni-generalizable Neural Methods for Vehicle Routing Problems. In ICML 2023.\n\n[6] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95\n\n*Note to AC: I am not an expert in diffusion and hence cannot completely ensure the correctness of the equations in Section 3.3.1 and the proof in the Appendix.*\n\n----\n\n**Overall**, despite the limited scope and expensive training cost, the proposed method is sound and novel, which may bring new insights to the ML4CO or NCO community. The empirical results are good as well. Therefore, I lean towards borderline acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thorough review and valuable comments. We are encouraged with your acknowledgment of our writing, motivation, methodology, empirical results, and contribution to the ML4CO community. Below we respond to your specific comments.\n\n**Q1: The proposed method is only applicable to diffusion-based methods, which may limit the scope of this paper.**\n\nIndeed the proposed method is technically developed on top of the diffusion models. However, it is important to note that this technical foundation does not confine its range of applications. For instance, the proposed framework exhibits the capacity to address CO problems whose decision variables are limited to a countable and finite set of values. This versatility encompasses a variety of graph CO problems, spanning both edge-selection problems like TSP and CVRP, as well as node-selecting problems like MIS and MAX Clique.\n\n\n**Q2: More details about the needed training time. The inference complexity compared to DIFUSCO.**\n\nWe have provided the details about the offline training resource requirement of T2TCO framework in the general response. \n\nFor the comparison to DIFUSCO, the proposed objective-guided denoising step requires ~ 3 times the calculation of the original denoising step. This increase is due to the additional gradient calculations needed to incorporate objective optimization information. However, T2TCO can achieve satisfactory results with fewer steps. The experimental comparisons are based on results with approximately equal computational overhead.\n\n\n**Q3: How about the generalization performance?**\n\nThanks for the comment. We have supplemented the generalization results in the general response.\n\n**Q4: POMO could achieve 0.03% and 0.14% on TSP50 and TSP100, respectively, while you report 0.64% and 1.07% in Table 1.**\n\nPlease note that the results in Table 1 (original) are based on greedy decoding. In this setting, the results are consistent with POMO's Table 2.\n\n**Q5: Experiments on real-world TSPLIB benchmark.**\n\nThanks for the advice. We have supplemented the experimental results on TSPLIB in the general response.\n\n**Q6: Has a similar idea (to the one in Section 3.3.1) been proposed in other domains (e.g., computer vision)?**\n\nAs mentioned in Line 124-126, classifier guidance and classifier-free guidance similarly attempt to introduce additional shifts to the original denoising steps to achieve conditional generation. However, these shifts originate either from an additional predictive classifier or from the difference between the conditional model and the non-conditional model, without a explicit optimization objective.\n\n**Q7: For Eqs. 6-7, why not use Eq. 1 in DIFUSCO as the objective?**\n\nEq. 1 in DIFUSCO using our notations: $l(x;G)=f(x;G)+valid(x,G)$, where $f(\\cdot)$ is the objective function defined on the feasible space and $valid(\\cdot)$ is the validation function that returns 0 for feasible solutions and $+\\infty$ for invalid solutions.\n\nThis objective formulation is general and classical in CO, but we cannot directly utilize it because:\n1. The need for the approximate objective estimation for the relaxed (infeasible) $x_t$ at time step $t$ requires a relaxed version of $f(\\cdot)$ like $f_r(\\cdot)$ in Eq. 7.\n2. The acquisition of gradient feedback from the objective is a requisite, yet the function $valid(\\cdot)$ lacks differentiability. Thus we define the differentiable constraint penalty $g_r(\\cdot)$ to reflect the extent of constraint violation and transmit reliable gradient signals.\n\n\n**Q8: Why the energy function is designed as Eq. 10?**\n\nRecall that an energy function measures how well the outputs fit the inputs. Eq. 10 aims to quantify the consistency between the inputs $(x_t, G)$ and the output $y$. Such that in the derived distribution (Eq. 7), the best $y$ matching the inputs can maintain the highest probability density, and the probability density is positively correlated with the matching degree.\n\n**Q9: In Eq. 12, why is $-\\log\\nabla_{x_t}Z$ removed?**\n\nIn the distribution defined by Eq. 11, different values of $x_t$ only affect the center position (i.e., $l(x_t;G)$) of this unimodal distribution. Changing $x_t$ only results in shifting this distribution, and therefore, $Z$ as the integral over the entire distribution is not affected by $x_t$ and can be removed in Eq. 12.\n\n**Q10: In line 224, is the negative sign missing in the exponentiation?**\n\nYes, the negative sign is missing. Sorry for our typo.\n\n**Q11: The authors mention that $x_{t-1}$ is not accessible at step $t$. However, the approximation of $p(y^\\*|x_{t-1}, G)$ still depends on $x_{t-1}$ (in line 224).**\n\nIn line 224, the expression $[-\\nabla l(x_t;G)]^\\top x_{t-1}$ indicates how to associate the calculated $[-\\nabla l(x_t;G)]^\\top$ with $x_{t-1}$. For $p_\\theta(x_{t-1}|x_t,G,y^*)=Zp_\\theta(x_{t-1}|x_t,G)p(y^*|x_{t-1},G)$, the former term produce the probability of $x_{t-1}$ and the latter term calculates $[-\\nabla l(x_t;G)]^\\top$. Their combination yields the ultimate output prediction.\n\n**Q12: How about the performance if using Monte-Carlo Tree Search (MCTS) as the post-inference decoding?**\n\nWe have made efforts with MCTS, but the diffusion-based models consistently fall short in yielding satisfactory results when coupled with MCTS. This may be due to that the solutions produced by the models are close to feasible rather than soft heatmaps, which might hinder its effectiveness when combined with MCTS. We will continue to make efforts and try our best to incorporate reliable outcomes with MCTS in the new version. Besides this, we believe that the current results with greedy decoding and sampling decoding already convincingly underscore the superiority of T2TCO.\n\n**Q13: Do you plan to release the source code during the rebuttal period?**\n\nThanks. We will release the source code upon the acceptance of the paper.\n\n---\nWe hope this response could help address your concern, and wish to receive your further feedback soon."}]

Author rebuttal:
Dear Area Chairs and Reviewers,

We greatly appreciate the reviewers' time, valuable comments, and constructive suggestions. We are delighted that all the reviews have expressed a positive inclination towards accepting our submission. Overall, the reviewers deem our paper as "well written" (p83a, gU16) and "constructive for ML4CO community" (uUyD, gU16), acknowledging our methodology as "interesting" (uUyD, p83a, uaDN), "novel" (p83a, uaDN, gU16), and "sound" (p83a, gU16), with "clear" and "practical" motivation (p83a, gU16) and "significant" or "impressive" empirical results (p83a, uaDN, gU16).

In the author response period, we make every effort to address reviewers’ concerns and provide additional experimental results in the **Supplemented PDF** to further verify our contributions. The summary of our main experimental efforts corresponding to the supplemented pdf is presented as follows:

(1) We provide experimental results on generalization. Specifically, based on the problem set {TSP-50, TSP-100, TSP-500, TSP-1000}, we train the model on a specific problem scale and then evaluate it on all problem scales. Table 1 and 2 present the generalization results of T2TCO and DIFUSCO [1] with greedy decoding and sampling decoding, respectively. The results show the satisfying cross-domain generalization ability of T2TCO, e.g., the model trained on TSP-1000 achieves less than 0.8% optimal gap on all other problem scales.

(2) We apply the 2OPT solution improvement technique to other main baselines in the original Table 1 and Table 2 for a fairer comparison. Table 3 presents the results on TSP 500 and 1000, and Table 4 presents the results on TSP 50 and 100. In Table 3, we mainly include DIMES and DIFUSCO for comparison, as they are the only two competitive methods in the non-2OPT setting. The results reaffirm T2TCO's superiority, just as in previous findings. 

Remark: T2TCO and DIFUSCO's results on TSP-50 have been updated in Table 4, since we observe that the previous TSP-50 results were obtained from the models trained on TSP-100. We sincerely apologize for this oversight, and we have verified other results to ensure their accuracy.

(3) We evaluate our model trained with random 100-node problems on real-world TSPLIB instances with 50-200 nodes. The compared baselines include DIFUSCO and baselines listed in [2]'s Table 3. Table 5 presents the results and shows T2TCO's superiority achieving merely 0.133% optimality gap, 58.3% better than the best previous method.

(4) We provide the details about the offline training resource requirement of T2TCO framework in Table 6. The results are calculated on A100 GPUs. For comparison reference: AM [3] requires 128M instances generated on the fly for training TSP-100, and it requires 45.8h on 2 1080Ti GPUs; POMO [4] requires 200M instances generated on the fly for training TSP-100, and it requires ~ 1 week on a single Titan RTX; Sym-NCO [5] based on POMO requires ~ 2 weeks on a single A100, Sym-NCO [5] based on AM requires ~ 3 days on 4 A100 GPUs.


In our individual responses, we provide detailed answers to all the specific questions raised by the reviewers. We hope these responses could help address the reviewers' concerns, and further discussions are welcomed towards a comprehensive evaluation of our work.

---

**Reference:**

[1] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. arXiv 2023.

[2] Graph Neural Network Guided Local Search for the Traveling Salesperson Problem. ICLR 2022.

[3] Attention, learn to solve routing problems. ICLR 2019.

[4] POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS 2020.

[5] Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. NeurIPS 2022.

Meta-review: The paper proposes a training to testing framework, which leverages the generative model to learn solution distribution and then conducts a gradient-based search within the solution space during testing. All the reviewers agreed that the problem is well-motivated, the proposed approach is novel, and the empirical evaluations are thorough. Overall, this paper is well written and easy to follow, and the idea of training to testing is valuable for this community. The authors' rebuttal addressed most of the concerns of reviewers, and all the reviews tend to accept the paper during the reviewer-author discussion phase. Therefore, I recommend this paper to the NeurIPS 2023 conference.
Decision: Accept (poster)