Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization
Authors: Yang Li
Jinpei Guo
Runzhong Wang
Hongyuan Zha
Junchi Yan
Venue: NeurIPS 2024 poster (2024)
Keywords: Neural Combinatorial Optimization
Generative Modeling
Primary area: machine_learning_for_other_sciences_and_fields

Abstract: Diffusion models have recently advanced Combinatorial Optimization (CO) as a powerful backbone for neural solvers. However, their iterative sampling process requiring denoising across multiple noise levels incurs substantial overhead. We propose to learn direct mappings from different noise levels to the optimal solution for a given instance, facilitating high-quality generation with minimal shots. This is achieved through an optimization consistency training protocol, which, for a given instance, minimizes the difference among samples originating from varying generative trajectories and time steps relative to the optimal solution. The proposed model enables fast single-step solution generation while retaining the option of multi-step sampling to trade for sampling quality, which offers a more effective and efficient alternative backbone for neural solvers. In addition, within the training-to-testing (T2T) framework, to bridge the gap between training on historical instances and solving new instances, we introduce a novel consistency-based gradient search scheme during the test stage, enabling more effective exploration of the solution space learned during training. It is achieved by updating the latent solution probabilities under objective gradient guidance during the alternation of noise injection and denoising steps. We refer to this model as Fast T2T. Extensive experiments on two popular tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), demonstrate the superiority of Fast T2T regarding both solution quality and efficiency, even outperforming LKH given limited time budgets. Notably, Fast T2T with merely one-step generation and one-step gradient search can mostly outperform the SOTA diffusion-based counterparts that require hundreds of steps, while achieving tens of times speedup.

Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization
Yang Li Jinpei Guo", Runzhong Wang", Hongyuan Junchi Yan Junchi
2 Dept. CSE School of & MOE Key Lab AI, Shanghai Jiao Tong University
Massachusetts Institute of Technology
'hee Chinese University of Hong Kong, Shenzhen Saanglily,mikee0re haw.aaeeoee...aanccieeeeeeeeeeee yanjunchi)@ssjtuu edu, cn runzhong@mit. edu, zhahy@cuhk. edu. cn
Abstract
Diffusion models have recently advanced Combinatorial Optimization (CO) as a powerful backbone for neural solvers. However, their iterative sampling process requiring denoising across multiple noise levels incurs substantial overhead. We propose to learn direct mappings from different noise levels the optimal solution for given instance, facilitating high-quality generation with minimal shots. This is achieved through an optimization consistency training protocol, which, for a given instance, minimizes the difference among samples originating from varying generative trajectories and time steps relative to the optimal solution. The proposed model enables fast single-step solution generation while retaining the option of multi-step sampling to trade for sampling quality, which offers a more effective and efficient alternative backbone for neural solvers. In addition, within the wraining-to-testing (T2T) framework, to bridge the gap between training on histor- ical instances and solving instances, introduce novel consistency-bant based gradient search scheme during the test stage, enabling more effective exploration of the solution space learned during training. It is achieved by updating the latent solution probabilities under objective gradient guidance during the alternation of noise injection and denoising steps. We refer this model as Fast T2T. Extensive experiments on two popular tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), demonstrate the superiority of Fast T2T regarding both solution quality and efficiency, even outperforming LKH given limited time budgets. Notably, Fast T2T with merely one-step generation and one-step gradient search can mostly outperform the SOTA diffusion-based counterparts that require hundreds of steps, while achieving tens of times speedup. The codes are publicly available at wtthttps:/// thub. wwwp///iinnaab-aSt//aaaaaaaa
1 Introduction
Combinatorial Optimization (CO) problems, which involve optimizing discrete variables under given objectives, essential in computer science and operational research. Due the inherent computational difficulty, e.g. NP-hardness, solving efficiency poses significant challenges and requires exhaustive human efforts design solving heuristics. Recent progress in this domain has shown promise in automatically learning heuristics with Machine Learning (ML) in a data-driven
"Correspondence author. 1 denotes equal contribution. This work was partly supported by NSFC (92370201, 62222607) and Shanghai Municipal Science and Technology Major Project under Grant 2021SH2DZX010..
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(o(
Graph Instance
Random Noise
10(3,
Solution
fo(x,,,'',G)
Xy
X
Xe
Xp
Optimization consistency models for CO solving where the model learns how to map from varying levels of noise to the solution distribution, conditioned on the problem graph instance.
Figure 1:
6 7 8, bringing practical advantages in both quality and speed, especially when the instances are within a certain domain. In addition, learning can help quickly uncover new heuristics for new problems new instance distributions where experts not there.
manner 2 3
Learning-base solvers for CO typically employ neural networks to generate neural predictions for solution construction search guidance, aiming to minimize either the objective score 2 4
5. 6. 9 or the deviation from reference solutions [10, 3] I 12 [3]. The problem-solving task places significant demands on the testing performance of the model, while optimizing the average performance across training data does not ensure optimal performance for every encountered test 8 have been proposed to perform tailored optimization on neural predictions for every testing instance. In particular, generative modeling like diffusion has shown promise in learning instance-conditione quality solution distributions 7 g with robust expressive power to achieve state-of- oftte-of-thh-ar aart performance, which also provides more informative support for further exploitation like gradient search in the solving stage, which was previously proposed as the diffusion-basee training-to-testing (T2T) framework [8). However, a major drawback of the diffusion backbone lies in its costly inference process, which necessitates tens hundreds of denoising steps to solve one problem instance. This limitation in inference speed is crucial since CO seeks to achieve the highest solution quality within the shortest possible time, where both performance and efficiency are pivotal metrics in this pursuit. Although the diffusion solvers 7 g can exhibit superiority in inference speed compared certain traditional methods and prior learning-basse
instance. Thus, methods [14 [5| 6
solvers, there remains substantial potential for speed enhancement, where bolstering this aspect could provide fundamental support and several-fold speedup for neural solvers based on generative modeling.
To resolve this issue, drawing inspiration from the successful practice of consistency models [16] for image generation, we propose the optimization consistency models speed up the diffusion-based T2T framework, dubbed as Fast T2T, specifically for optimization problem-solving. We follow X to approach CO problems as conditional generation tasks, with the goal of modeling the distribution of high-quality solutions specific to given problem instances. As illustrated in Fig. Fast T2T builds upon the methodology foundation of the discrete diffusion models [17 19 where a smooth transition from random uniform noise to the high-quality solution distribution is established. Given a problem instance, Fast T2T trains the conditional prediction consistency directly from varying noise levels to the solution distribution centered on the optimal solution to enable fast one-step solution distribution estimation. Meanwhile, to bridge the disparity between data-driven training and problem-solving. Fast T2T incorporates a novel objective gradient search for every instance in the testing phase based on the trained optimization consistency mappings.
Specifically, for the solving task, the model is expected to deliver the optimal solution output to the best extent possible for given input instance. Thus, we define the optimization consistency property for the optimization scenario by conditional generation: conditoned on a given instance G, points on all trajectories of all noising steps consistently map to the optimal solution of G. Compared to
the diffusion prediction of the data distribution from noising step to step t 1, the consistency modeling enables generating solutions (xy in Fig. I from random noise vectors (xy in Fig. (T) by single step of model inference. This is achieved by an optimization consistency training protocol that minimizes the difference among samples originating from varying trajectories and noising steps relative to the optimal solution. The model retains the capability for multi-step sampling to trade for sampling quality by alternating noise introduction on X, to generate less noisy point x, and solution reconstruction to obtain new xo- Additionally, design novel objective gradient-baat based search

---

on top of the learned consistency mapping to further explore the learned solution distribution for every test instance. We introduce instance-speciffe guidance from the objective the learned solution prior (x G) and obtain the posterior po(xly" G) where y² represents the optimal objective score given instance G, thereby directing the sampling process to the optimal x*. It specifically entails minimizing the free energy corresponding to the posterior by updating the probability parameters of intermediate noisy points through exponential gradient updates guided by the objective function during the alternation of noise injection and denoising steps.
We show the efficacy of Fast T2T on two typical CO problems for edge dige-decision and node-decision types respectively, i.e., Traveling Salesman Problem (TSP) and Maximum Independent Set (MIS), We show that Fast T2T, even with single-step initial solution generation and a single-step gradient search, can mostly outperform the SOTA efffusion-basee counterparts with hundreds of inference steps. Meanwhile, due to its reduced step requirement Fast T2T naturally demands significantly less inference time to achieve comparable quality, with more steps for further enhancement.
The highlights of this paper include: 1) We introduce the optimization consistency condition and establish Fast T2T based on the proposed optimization consistency models to facilitate fast high-quality CO solving, which offers highly effective and efficient backbone for learning- -aased solvers. 2) To complement the learned prior and bridge the disparity between data-driven training and the requirement of -olvvigg we introduce a novel gradient search with objective guidance based on consistency mappings to conduct tailored search for every test instance. 3) Extensive experiments show that Fast T2T exhibits strong performance superiority over existing SOTA neural solvers on benchmark datasets across various scales.
2 Related Work
Machine Learning for Combinatorial Optimization. Current learning- bearning-based CO solvers can be cat- egorized into constructive approaches and improvement-basee approaches. Constructive approaches refer to autoregressive methods (20 2
21 5 that directly construct solutions by sequentially determining decision variables until complete solution is constructed, and non-autoregressive 7 23 that predict soft-constrained solutions in one shot and then perform post-
4
methods 3 12 22
processing to achieve feasibility. Improvement based solvers [24 25 26 27 28 learn iteratively refin solution through local search operators toward minimizing the optimization objective.
Generative modeling for CO has recently shown promise with its potent representational capabilities and informative distribution estimation. It models the problem-solving task as a conditional generation
Drawing from diffusion models, DIFUSCO 7 has attained SOTA performance in solving TSP and MIS. Nonetheless. does not incorporate any instance-specinng search paradigms fully capitalize on the
task for learning solution distributions conditioned on given instances [2] 29 7 30
31 8
estimated solution distribution. Addressing this limitation, the T2T framework (8) further introduces an objective- -uidedd gradient search process during solving to leverage the learned distribution. However, every aspect of this system, including distribution learning and gradient search, hinges on the diffusion model for step-by-step generation. This reliance renders the diffusion- based approaches computationally inefficient and impedes further search computations to trade for solution quality.
Diffusion Models and Consistency Models. Diffusion models entail dual process comprising noise injection and learnable denoising, wherein neural networks predict the data distribution at each step based on the data from the previous step. For Diffusion in continuous space 17
37]. the solution trajectories can be modeled by Probability Flow ODE 38). Similar paradigms have also been adopted for discrete data using binomial or multinomial/categrraa noises 17 18 19]
32 33
34
35
36
On top of the foundation of diffusion models, consistency models [6] define the self-consistens for every generation trajectory and introduce a consistency training paradigm for continuous data to directly learn the mappings from noise to the data. Inspired by this paradigm, we define the optimization consistency condition tailored for the optimization scenario, which requires consistency across multiple trajectories and time steps with the optimal solution as the target in a conditional context, thereby proposing the optimization consistency models as the solver embodiment. The models employed on the discrete multinomial data for the benefit of CO.
3

---

3 Preliminaries and Problem Definition
Adopting the conventions established in
39 40 we define G as the collection of CO problem instances represented by graphs G(V. E) E G, where V and E denote the nodes and edges respectively. CO problems can be broadly classified into two types based on the solution composition: edge-decision problems that involve determining the selection of edges and node-decision problems that determine nodes. Let x E {0, 1] N x2 denote the optimization variable, where each entry is represented by a one-hot vector, i.e., each entry with (0. 1) indicates that it is included in x and (1, 0) indicates the opposite. For edge-decision problems, N = n² and x,, indicates whether E,, is included in x. For node-decision problems, NN = and x; indicates whether V, is included in The feasible set P consists of x 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)Nx2 Rzo:
min (E
1(x; G) s.t. x x $2
TSP is defined on undirected complete graph G (V, E), where V represents cities and each edge E,,5 is assigned non-neegee non-negative weight Wa, representing the distance between cities and j. The problem revolves around identifying a Hamiltonian cycle of minimum weight in G. For MIS, given an undirected graph G = (V. E), an independent set is a subset of vertices S S V such that no two vertices in S are adjacent in G. MIS entails finding independent set of maximum cardinality in G.
4
Training-Stage Optimization Consistency Modeling
4.1 Solution Encoding and Noising Process
Using the notations in Sec. 3 we represent the solutions of CO problems as x E {0, 1) with x E Ω. The distribution of x is represented by N Bernouli distributions indicating whether each entry should be selected, i.e., p(x) E [0, 1] The objective of utilizing generative modeling for problem- solving is to capture the distribution of high-quality solutions conditioned on a given instance G, denoted as ()) The neural models try to establish transition trajectories from random uniform noise to high-quality soft-constrained solutions, i.e., E {0, 1J These soft-constrained solutions are directly sampled from the estimated Bernoulli distributions where feasibility constraints can be broadly captured through learning and eventually hard- sard-guaranteed by poss-processing.
To establish the transition trajectories of data, we follow the discrete diffusion modeling 7 g to
define the noising process, which takes the initial solution X, sampled from the distribution g G) and progressively introduces noise to generate sequence of latent variables X1:7 = X1, X2, .... Xy-
Specifically, the noising process is formulated as q(x1:r|xx) = II= ((2 (x) which is achieved
by multiplying x, e {0. 1]. Nx2 x2 at step with a forward transition probability matrix Q₂ E [0, 1]2x2
Be 1- 1-3: 3:
which indicates the transforming probability of decision state. We set Q:
18
11--, 3,
B.
where 3r [0, 1] 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 1-step marginal are formulated
qxx x1- = Cat(x;; p xx-1Qu) Qr) and qxx; xo) Cat(x:: = X XxQ,)
(2)
where Cat(x: p) is categorical distribution over N one-hot variables and Q = Qi Q2 .....Q.. ....Q.
Q
4.2 Optimization Consistency Training Scheme
Unlike the diffusion models modeling po (x x G),, we aim to directly map random noise data by (xolxx G) in an optimization context. In continuous-time diffusion models defined on (c, [38] consistency models [16] defines the self coff-consistency property as points on the same trajectory map to the same initial point, and optimize the learned consistency function fo(-.-) to satisfy the
requirement by: 1) boundary condition: fo(x,, 6) = x,: 2) self-consistency property: Jo outputs consistent estimation for arbitrary pairs of (x,, L) that belong to the same trajectory, i.e., fo(xe,
fo(x,,t'), Y 1, E [e, T). The joint effect of these two constraints serves as the necessary and sufficient condition to achieve reliable data prediction from noise step T to data, i.c., fo(xT, +

---

p(x,)
Trajectories
p(x.)
p(x+)
Trajectores
((k)) -x)
606.7.0
1000
13.33
[2
(..
(4.0
Conditioned Instance
(A) Vanilla Consistency Models
(b) Optimization Consistency Models
Figure 2: Vannila consistency models are trained to map points on any trajectory to its origin. Optimization consistency enforces that all trajectories conditioned on G consistently map the same initial point, i.e,, the optimal solution of G.
x, In the optimization scenario of mapping instance G approximate its optimal solution x", the generation process is conditioned on the problem instance G with a reference optimal solution x" serving as the commonly targeted initial point for all the conditional trajectories. Based on the discrete diffusion process with an explicit sampling process [ 7 8) we use the consistency function to estimate the optimal solution distribution as a point estimate d(x x*) where 8(.) represents Dirac delta. Below defines optimization consistency for the conditional context of problem-solving.
Definition 4.1 (Optimization Consistency). Given a solution trajectory {xt (xe)o00..7 we define the consistency function as f : (x,, t, G) + 6(x - x*), which maintains the optimization consistency property: conditioned on instance G, all points along any trajectory map its optimal solution, i.e., fa(x), t, G) fo(x),, t', G) 8(x x") for distinct trajectories i and at distinct steps and t'.
As illustrated in Fig. the goal of the consistency model fe in the optimization context, is to estimate the consistency function from data by learning to enforce optimization consistency. To achieve such consistency in the context of optimization to learn ʃ G + x given its nature as conditional gener- ation and the aim for an explicit optimal solution x", we can seamlessly integrate x" into the objective function for smooth training. Instead of optimizing the expectation of the variation of the consistency mappings over two noise points x and x', i.c., (0) E (ffe (x, G). fe (x', t G) ]. we introduce x" to optimize the upper bound of LCM through triangle inequality of distance measures as
LOpcM (0) = E[d(fo(x, 1, G), -(x-x(())) + d(fo(x', 1', G), 8(x - xx])] 2 LcM(O).
(3)
Here -(.,-) is a distance metric function. In this case, the boundary conditions become less significant, since we have already dispersed the information of x" across all noise time steps. Therefore, can directly utilize the neural network to estimate the consistency function fo(:...). :). In addition, all learned trajectories are expected to map to the optimal solution x" given the instance G, and the estimated solution distribution is expected to center on x". This calls for the requirement of consistency extending across all trajectories, rather than being confined within single trajectory.
Definition 4.2. The optimization consistency loss for conditional problem-sol is defined as:
Copicm (0) = [A(t.) (d (fo(xi, G), 0), d (fo(x) 1n G), 8(x - xx)) (4)
where the expectation is taken with respect to G ~ PC, n U[, N₂ 11. x Cat(xi,, x" &²Q.,) and x Cat(X x' x²Q...)). He NN denotes the uniform distribution over {1, 2....... ... N - 1}. X() E B is a positive weighting function.
Since the model outputs N Bernoulli distributions the distribution of xg. we adopt the binary cross entropy to measure the distance between the estimation po(x) and 5(x - x"). We set X(t,.) = 1 and discover a decent empirical performance. xi,, and x are identically and independently sampled from different noising trajectories, in comparison to x : = x', x x Cat(X P = x,, Qt++1 Q....) where xf,, and x are from the same trajectory. Since very close fn and fn+1 would make Eq. 4.2 very easy to learn, we reschedule the time horizon into N₂ 1 sub-intervals
< to < tN. T through the cosine denoising schedular such that [cos (1-g-e() T' following DDIM 34 This training procedure enforces the model to learn
5

---

conditional consistency across different noise steps to consistently map to the optimal solution x" of the given condition G. Note that although we enforce the noise to map the Dirac delta on x", the generative modeling process with single sample per instance condition during training still enables the model to estimate a solution distribution (centering around the optimal solution) to enjoy diversity to enhance performance via parallel sampling, as evidenced by the experiments in Table. 2
Specifically for implementation, the network 0 is embodied an anisotropic graph neural network with edge gating mechanisms [3] and instance G serves as part of the conditional input as the node or edge features. For TSP, the 2D coordinates of the vertices serve as the instance condition, and the input edge features are from the embeddings of entries in X; integrated with the embedding of the input time step t. For MIS. the edges E serve as the instance condition and the node embeddings are from x, to collectively form the input. After the GNN iterations, the features of the decision variables
(edges for TSP and nodes for MIS) are projected to 2-D outputs po Po(Xo) (Xolx,, G) E (0, 1] featuring N Bernoulli distributions for N entries in Xo via linear layer followed by Softmax layer.
5 Testing-Stage Problem Solving via Consistency-Based Gradient Search
The solving involves obtaining the initial solution from the raw consistency sampling process and consistency-basel gradient search process with objective feedback for iterative solution improvement.
5.1 Consistency Sampling for Initial Solutions
With well- well-trained fo(:..;), we generate solutions for given instance G by sampling Xy from the uniform distribution and then evaluate for Xa po(xo) = fo(xr, T, G). This process requires only one forward pass through the consistency model, re- sulting in sampling in single step. Solution sam- pling with multiple steps of inferences can also be accomplished via alternating denoising and noise injection, allowing trading runtime for improved solving quality. Given sequence of time points T1 > T2 > > TN,-I in time step Tue the multi- step sampling process adds noise to the xy obtained from the last step Tn-1 by X,, ~ Cat(x,,; i =
Algorithm 1 Multistep Consistency Sampling
Input: Consistency model fo(::".), graph problem instance G, sequence of time
points T1 > T2 >> ... > -N
Sample XT from uniform distribution 4 po G)) +- fe(XT, T, T)G) Xo ~ po po G)) for n 1 to N, - 1 do
Sample XT. ~ Cat(X : p0= = X Q..)) (o (G) t fo (xcx..: Tni G)
X ~ pe px(xxl (xo G)
end for
x xQ..). ), then denoise to find the new solution by Xy ~ fx( Ta, G), as shown in Algorithm.
Output: Solution Xo
5.2 Consistency- Gradient Search with Objective Feedback
For CO. the integration of objective optimization facilitates direct engagement with the objective and enables efficient exploration of the solution space to minimize the score. [8] has established such a procedure for the step-by-ste bt- denoising function, yet it is not transferable to the consistency function, and incorporating objective optimization may prove more challenging as the consistency function maps across longer distance time steps. With the learned conditional solution prior (x()) this sec- tion aims to introduce constraint c(x, y GG) on x to this prior for inference, where y represents the optimal objective score given the instance G. That is, we want to find approximation to the posterior distribution po (x y"" G) x (x)) (G) to guide the sampling process to the optimal x*.
g to determine c(x, y (G) by utilizing energy-based modeling 41 with the energy function Ely. x, = ly 1(x: G)J. which quantifies the compatibility between y and (x, G), and
Here we follow
reaches zero when y is exactly the objective score of x with respect to G. Such a design enables the best y matching the inputs 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 a collection of arbitrary energies:
exp(- ([-F(,,, x, G)) (() fy expl E(y' x. G))
Z exxp(-11 -ly -((( G))
(5)
6

---

Following 42). we introduce an approximate variational posterior g(x[G) and the free energy
F = - ()g(hlx) (x h[G) - log (()) G)] - [((()) [log c(x, y G)]
(6)
is minimized when (x (x)l" G)) is minimized. Here h = X1 XT represent the
latent variables. Through the diffusion process, an approximation to the posterior over x = Xy as a point estimate g(x () = 6(x 7). Fi aligns
obtain (h]xx) II_ (xx, x We apply
with the objective of the consistency and diffusion models and F2 can be transformed using Eq. 5
log 2(h)m, G) po (m, b[G)
(h)
and F2 log c(n) y [G) ((m G) log y²
(7)
Initializing 17 from Sec. 5.1 we aim to update to reach conditional solution distribution po ( v G)
through exponential gradient decent on the latent continuous probability Px p(xxr) = n,TT E [0, 1| at each iteration minimizing F1 and F2. Here Px parameterizes N Bernoulli distributions and a serves as hyperparameter to control the noise degree. We view px as the expectation of X.T over Px, i.e., Ep, (X.7) Px, since Px is a multivariate Bernoulli. To obtain reliable gradients on Px. we estimate the expected distribution of Xn by [o(Px, aT, G). Note Fi is exactly the (implicit) objective of the diffusion and consistency models, i.e., the variational upper bound of the negative log- log-likelihood with the targeted data which we optimize by minimizing the consistency over the re-predicted solutions (fx( aTI', G), 8(x n)). While F/2 can be optimized by minimizing ((JoPxx oT, G); G) + Const(px), where the objectives are defined following [8] as IMIs (x; G) A EiSien + ((j)E x; and lTSP = x ④ D where D E R4 denotes the distance matrix.
In each iteration, with current v). we obtain Px = noaT. (o(n)) = fo (Px, G) and update px by (8)
Px f Px C exp Vpx A (Epp())) n. 8 (x 7)) + A2 (7 G)]}
where d₁, A2 are weighting hyperparameters Then we sample XxT ~ Px and reconstruct new distribution estimate of 17 by (n) fx(X.7, aT' G). To guarantee the feasibility, we utilize the logits of (T( and p/g (n) to produce the heatmaps where each element denotes each edge/node's s confidence to be selected, and then adopt post-processing") to obtain two feasible solutions. This iteration concludes by outputting the lower-cost solution 77.
6 Experiments
We test on two CO problems, TSP and MIS. The comparison includes SOTA learning-based solvers, heuristics, and exact solvers for each problem. To configure the generative-baset models, we adopt T, and Tg to represent the number of inference steps in initial solution sampling and the number of gradi- ent search steps, respectively. For diffusion- based baselines including DIFUSCO (7) and T2T [8) we adopt 5,=50 and involve 3 iterations with 5 guided denoising steps per iteration for T2T's gradient search, i.e., 11= Fast T2T can achieve promising results with merely one-step initial solution sam- pling and one-step gradient search, i.e., T and =,=1. However, the affordability of model inference facilitates more extensive exploration of the solution distribution through a thorough search.
6.1 Experiments for TSP
Datasets. A TSP instance includes N 2-D coordinates and reference solution obtained by heuristics. Training and testing instances are generated via uniformly sampling nodes from the unit square [0, 1]2, which is standard procedure adopted in [2] 21 48 6 8). We experiment various
problem scales including TSP-50, 100, 500, and 1000.
6 7 8) we adopt three evaluation metries: 1) Length: the average total distance or 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.
Metrics. Following 2
We follow previous works 6 g to perform greedy decoding by sequentially inserting edges or nodes with the highest confidence if there conflicts. For TSP, the 20pt heuristic [43 is optionally applied.
7

---

Table Results with Greedy Decoding on TSP-50 and T0P-100. RL: Reinforcement Learning, SL:
Supervised Learning, G: Greedy Decoding. denotes results that are quoted from previous works.
TSP-50
TSP-100
ALGORITHM
TYPE
LENGTHL
DROPL
TIMEI
LENGTHL
DROP,
TIMEL
Concorte
Exact
5.69
0.00%%
(3m)
7.76
0.00%
(12m)
LK113
55
Heurittics
5.69
0.00%
(3m)
7.76
0.00%
(33m)
20pt
Heuristies
3.86
2.95%
8.03
3.54%
AM
2
RL+G
5.80
1.76%
(2s)
8.12
4.53%
(6s)
GCN
3
SL+G
5.87
3.10%
(55c)
8,41
8.38%
(6m)
Transfrmer
RL+G
0.31%
(14s)
7.88
(5s
POMO
4
RlaG
5.73
0.64%
(16)
7.84
1.17%
(2s)
Sym-NCO
RL4G
7,84
0.94%
(2))
Image Diffusion"
SL-G
1.23%
7.92
2.11%
(IFUSCO((T=I)) 7
SL-G
6.42
12.84%
(16s)
9.32
20,20%
(20s)
DIFUSCO (T,-50) X
SL+G
5.71
0.45%
(9m)
7.85
1.21%
(9m)
DIFUSCO((T,=100
SL+G
5.71
0.41%
(18m)
7,84
1.16%
(18m)
Fast 12T (T,=1)
SL-G
5.71
0,31%
(11s)
7,86
1.31%
(16s)
Fast T2T (T.-3)
SL-G
5.69
0.05%
(25s)
7.77
0.17%
(33s)
Fast 127 (1(=5)
SL+G
5.69
0.02%
(1m)
7.76
0.07%
(1m)
12T
g
SL-G
6.15
8.13%
(554)
9,00
16005%
(Im)
121 (1,-5001,-15)
SL-G
5.69
0.07%
(18m)
7.77
0.20%
(18m)
T2T (T,=50.T,
SL-G
5.69
0.03%
(26m)
7.76
0.11%
(42m)
Fast 12T (T,-1.T--]
SL-G
5.69
0.03%
(54s)
7.76
0.10%
(Im)
T2T (T,=2.T,-2)
0.02%
(2m)
7.76
(2m)
Fast T2T (T.33T
SL-G
5.69
0.01 %
(3m)
7.76
0.03%
(3m)
Results for TSP-50/100. Given the recent success of learning-basse solvers in achieving near-optimal performance on small-scale problems, we follow g to assess methods within the naive greedy decoding setting, aiming for a more discernable evaluation. The comparison includes state-of-the-ane learning-base based methods with greedy decoding and traditional solvers. Hyperparameter a set as 0.2. The sampling steps and gradient search steps are explicitly marked. Table. Table.[]shows shows that Fast T2T with merely one-step sampling steps approximates diffusion-basee based solvers with 100 sampling steps with a slight average performance gain of 5.7% yet with an average speedup of 82.8x. A similar conclusion can be made for methods with gradient search with an average performance gain of 4.5% % and speedup of 35.4x. Fast T2T variants with more sampling and gradient search steps achieve 82.1 % performance gain with 14.7x speedup compared to previous statc-of-the art diffusion basod counterparts.
Results for TSP-500/1000. Learning based solvers are compared using greedy decoding and sampling decoding (x 4), i.e., sampling multiple solutions and reporting the best one. Hyperparameter a is set as 0.2. The sampling steps and gradient search steps are explicitly marked. Table. (/swos that Fast T2T with merely one-step sampling steps averagely outperforms diffusion-based solvers with 100 sampling steps by performance gain of 10.1 % and speedup of 16.8x. A similar conclusion can be made for methods with gradient search with an average performance gain of 14.9% and a speedup of 8.5x. Fast T2T variants with more sampling and gradient search steps achieve 52.1 % performance gain with 7.4x speedup compared to previous SOTA diffusion based counterparts.
Results for Generalization. Based on the problem set (TSP-50, 100, TSP-500, TSP-1000), we train the model on a specific problem scale and then evaluate it on all problem scales. Table 3 presents the gener- alization results of Fast T2T compared with diffusion-based counterparts with greedy de- coding. The results show the satisfying cross-domain generalization ability of Fast T2T, e.g., the model trained on TSP- achieves less than 0.6% optimality gap all other problem scales.
Table 3: Generalization results. Tour length and drop with Greedy Decoding reported.
TSP-30
TSP-100
3SP-500
TSP-1000
585. 2.55%
2:71R
TSP-30
12T (T
5.00 0.175
0300%
55 (1.0%
5T, (1.11)
571.1425
576. 1.605
639. 1.00%
1.02%
30.7,
DIFUSO0 eaar
ZaT, 1.4%%
2:25 0132%)
$10. 3.44%
KG1, 3.31%
(1.2%
2,26, (3022)
2.36 11457
1435
7.7% 0.00%
7.76 0.00%
1.77. 0.25%
7.7% 4L.4%
DIPLSCO (2
15,05 3114%
15.7%
LI9S
1SP-500
T2T (T=30T -30r
8
17.18- 3.79
3.07%
16.90 3.35%
7.775
75.05 0.41%
15.72 LOOS
01115
Fask (1-3307,-00
DIPL500 epaoo 0
24172-4555
34J44 3380%
23,63 23375
25,55 2275
TSP-1000
(Tud
24.8.4
3.66%
0.855
0.195
Pas 222 (12 2010
25.06,2225
24J1L 34677
23.35 14.8%%
21.20 0.795
Soving Time vs. Optimality Drop on TSP-100/1000. Fig. Bland Fig. Dillustrate the solving progress
via the runtime-drop curves of Fast T2T and the prominent mathematical solver LKH3 [45). The comparison is conducted on TSP-100 and TSP-1000 We are excited to discover that Fast T2T surpasses LKH3 the early solving stage while also performing comparably in the later stage. This suggests that Fast T2T can serve an effective rapid solver for approximate solutions outperforming
8

---

Table 2: Results on TSP-500 and TSP-1000 AS: Active Search, S: Sampling Decoding. BS: Beam Search." denotes results that are quoted from previous works 8 6
125
Merhod
Fast 121
1.00
LKHS
0.75
ALGORITIM
Tyre
TSP-500
TSP-1000
0.50
LeNGTnL
Diorr
LENCTIN
Dwor]
TIME
025
Mishonatical Siswwer Hearintic
Concoede 4
Esact
16.55
37 66m
23.12
0.00%
6,059
0.00
Dambi
10
Exact
16.55
0.00%
45.63h
1K1-3
Houtettos
10.59
25m
2312
0.08
2.578
Time
Ber Insction
Hourisiis
18.30
10.57%
11,25%
Figure 3: Effeet of runtime to optimality drop for Fast T2T
Leanwing busee Stylerz
Decoding
AM
Rl
30.07
1.5mm
51.15
$4.795
1.18m
IOMO+EAA-EEE
OCN 8
SLG
29.72
16.35%
79.01%
12.90h
0,67m
48.62
130.29%
28,52m
and LKH3 on TSP-100.
RL
11.6th
63,45h
DIMES
18.93
14.38%
14.77%
DIMES
RLAAASG
17:81
7616
2310
2451
1.70%
4,6h
Method Fast T2T
DIMES
Rl-GG+20pt
17.05
6,626
1.31
24.43
7.38%
7.24
DIMES'
RL--AS-G-20pp
17.31
4.57%
2,106
24.33
5.22%
4,4%%
2.0
UKHD
DIFISCO (7,-100
SL4G
0.2%
17:80
0.13%
Pat
Stues
17.53
5.84
6.29%
M
17.0
300
25.0
Fat T2E [T-..-)))
SL4G
17.25
4.23%
36s
24.00
6.42%
2aa30s
Fai 721 -:
SLUG
16.93
2.35%
2m
23.96
3,64%
9c122
0.5
DIFUSCO (1-4000
20g
16.80
1,306
25.55
1,39%
(T-1))
20p
1.42%
SLaG-200p
2004
16.67
0,731
1.00%
20633
Figure 4: Effect of runtime to optimality drop for Fast T2T and LKH3 on TSP-1000.
Fai T21 (
16.61
0.39%
2m
23.25
0.58%
8r337
Zearning bused Soeierz with Sumpying Decoding
19.53
18.00%
29.23%
OON DIMES DIMES
SLARS
10:37
81.55%
18.00m
$1.06
131 711
51.67m
BI-AAS45
RL.15
19.84
17.80
13.54%
7.55%
1,050
2.1
26.36
24.80
14,01%
1.70'%
2.38
4.555
0:7-
TSP-60
DIMES DIMES
RLrS-20gt
17.64
6,561
1.10m
24:11
1,29%
2,86n
000
TSP-500
RUrASeSS220p
17.29
4.4815
5.17%
4,500
2
DIFUSCO
SLIS
17:55
6.05%
5,60%
Slo4ts
Fai T3T (T-))
SE-8
1263
6.56%
S3
24.1
1.7w%
3mda
Feil 73T (T=5))
SL-8
17.02
185%
1n7
2407
4.10%
T27 12T1T,200 (T,
8
SL-8
17.04
2.9%
15m33,
24.55
7,49%
4halls
Best Tu 1T,
SL-88
17.0%
32116
2ml6
24:43
6.67%
4enss
16.73
19m1s
DD
25.0
Apha
Foo (T:5))
(Te (Tel))
S1-3
1663
16.72
0.49%
Ind
23,30
0.77%
1.17%
Figure 5: Effect of a to the performance drop.
122 (0.00 8
16.3
0,36%
23.37
1.80%
Fail 12t (T-
S1=3+20pp
16.44
0.545
2m33
23:31
0.895
6m144
Fost (T-55
20-s+
16.58
0.31%
23.23
0.43%
18m175
LKH3, which may find widespread applications requiring prompt responses. Other neural solver baselines fall far outside the comparable range; please refer to Fig. for intuitive illustration.
Ablation and Hyperparameter Study. Fig. 5 illustrates the performance variation when altering the noise hyperparameter a, and we discover relatively superior and stable performance at = 0.2. Fig. 6 shows the performance variation when varying the sampling and gradient search steps. We also include DIFUSCO 77) and T2T g for direct comparison, in order to see whether diffusion- based methods can achieve promising results using minimal sampling steps. In this case, we let the gradient search steps equal to the sampling steps for Fast T2T and T2T. The results show significant performance overwhelm of Fast T2T to diffusion-based counterparts.
6.2 Experiments for MIS
Datasets. Two datasets are tested for the MIS problem following 52 54 53 6 77, including RB
graphs (31) and Erdōs-Rényi (ER) graphs [55] We randomly sample 200 to 300 vertices uniformly and generate the graph instances. ER graphs are randomly generated with each edge maintaining
fixed probability of being present or absent, independently of the other edges. We adopt ER graphs of 700 to 800 nodes with the pairwise connection probability set as 0.15.
Metries. Following previous works 3 7 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. size compared to the optimal solution or the reference solution; 3) Time: the average computational time required to solve the problems.
Main Results. The baselines include SOTA neural methods with greedy and sampling decoding (x4), as well as exact solver Gurobi 49] and heuristic solver KaMIS [51]. The solving time of Gurobi is set as comparable to neural solvers, thus it does not reach optimality. Table. T shows that Fast T2T with merely one-step sampling and gradient search steps averagely approximates ffffusion-based

---

Table 4: Results MIS. TS: Tree Search, UL: Unsupervised
Learning. denotes results quoted from previous works g
31
RB- R8-12000200)
ER- 700-000000
ALGORITIMM
TyPn
SIZE
Drari
TIME
SIZE:
TIME
Deop (S)
KaMIS 51
Beuristies
20.10"
1624m
46.87
52.15m
Gurobu
19.88
0.015
47m844
50.00m
Intel 52
0
RL+G
6.12m
SL+G
18.52
7.81
18m5s
37.00
18.53%
5m30s
Fist 121 (1,-1)
SL4G
18.59
7:3788
35c
36.72
18.17%
11s
Bkep
Fist (T,5)
SL4G
18.74
6.65%
1m16:
37.80
15.76%
24c.
0.4
-,,10 15
3,29
1r.3%
Dop
Fast (T-I,__))
SL+G
19:37
3.51%
1m18s
60.25
10.30%
25%
02
(T.:S.;5)
DGL
SLa15
SL+TS
18.47
17.36
13.61%
12m477
13m4s
37.26
16.96%
20:00m
m
Step
10
15
Lwb
RL+5
41.17
8.25%
6.33m
Figure Effect of step num-
GelowNets
U1.48
19:18
4.57%
324
41.14
8.539
2.92m
(1,-100
"Lis
19.13
2,799%
220m224
39.12
12.81%
21a6455
ber to drop for diffusion/con- sistency based methods. GS
Fixt T2T (T,=I)
S1.48
18.91
5.81%
42s
37.91
15.53%
24s
Fas (1:45)
SLeS
19.38
3.46%
1m50s
11.27%
1mi
SLLS
19.58
3.30%
30m188
31.31
7.723
2hm435
stands for gradient search.
Fist (1-11:1--)
SL48
19:53
2.74%
1ma1%
Fost 121 (1,-511:55)
SL+S
19.70
1.90%
6m359s
41.73
6.99%
Smn5s
counterparts with approximately 100 sampling steps by slight performance gain of 2.5% and speedup 26.3x. Fast T2T variants with more sampling and gradient search steps achieve 23.7% % performance gain with 9.1x speedup compared to previous SOTA diffusion-based counterparts.
7 Conclusion
We introduce optimization consistency on top of the diffusion-basse framework for efficient and effective combinatorial optimization solving. Our proposed model facilitates rapid single-step solving, demonstrating comparable or superior performance to SOTA diffusion-based counterparts, offering a more effective and efficient alternative backbone for neural solvers. In addition, a novel consistency-based gradient search scheme is introduced to further complement the generalization capability during solving. Experimental results on TSP and MIS datasets showcase the superiority of our methods, exhibiting significant performance gains in both solution quality and speed compared to previous state-of-the-an neural solvers. Furthermore, our approach demonstrates superiority over LKH3 in the early stages of solving.
solving
References
[1] Y. Bengio, A. Lodi, and A. Prouvost, "Machine learning for combinatorial optimization: methodological tour d' d'horizon," European Journal of Operational Research, 2021.
[2] W. Kool, H. Van Hoof, and M. Welling, "Attention, learn to solve routing problems!" arXiv preprint arXiv: 1803.0887777 08475, 2018.
[3] C. K. Joshi, T. Laurent, and X. Bresson, "An efficient graph convolutional network technique 2019.
for the travelling salesman problem," arXiv preprint
[4] 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 188 21 198, 2020.
[5] M. Kim, J. Park, and J. Park, "Sym-neo: Leveraging symmetricity for neural combinatorial optimization." arXiv preprint arXiv:220S. 2022.
[6] R. Qiu, Z. Sun, and Y. Yang, "Dimes: A differentiable meta solver for combinatorial optimization problems," arXiv preprint 2rX1v:2210.04123, 2022.
[7] Z. Sun and Y. Yang, "DIFUSCO: Graph-based diffusion solvers for combinatorial optimization,"" Thirty-seventh Conference on Neural Information Processing Systems, 2023. [Online]. Available: http:///ppnnvvii...eermmmmmddddd
[8] Y. Li, J. Guo, R. Wang, and J. Yan, "T2t: From distribution learning in training to gradient search testing for combinatorial optimization," in Advances Neural Information Processing Systems, 2023.
10

---

[9] Y. Min. Y. Bai, and C. P. Gomes, "Unsupervised learning for solving the travelling salesman problem," Advances in Neural Information Processing Systems, vol. 36, 2024.
[10] O. Vinyals, M. Fortunato, and N. Jaitly. "Pointer networks," Advances in neural information processing systems, vol. 28, 2015.
[11] B. Hudson, Q. Li, M. Malencia, and A. Prorok, "Graph neural network guided local search for the traveling salesperson problem." " in International Conference on Learning Representations.
2022. [Online]. Available: bttps://openreview.ne//ooe Boooouummmmdaat/2oosssB....
[12] 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 Artificial Intelligence, vol. 35, no. 2021, pp. 7474-7482.
[13] F. Luo, X. Lin, Liu, Q. Zhang, and Z. Wang, "Neural combinatorial optimization with heavy decoder: Toward large scale generalization," Advances in Neural Information Processing Systems, vol. 36, 2024.
[14] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio, "Neural combinatorial optimization with reinforcement learning," arXiv preprint arXiv:1611.09945 2016.
[15] A. Hottung, Y.D.. Kwon, and K. Tiemnyy "Efficient active search for combinatorial optimization problems," arXiv preprint arXiv:2 126, 2021.
[16] Y. Song. P. Dhariwal, M. Chen, and I. Sutskever, "Consistency models," arXiv preprint urXiv:2303.01469 2023.
[17] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli, "Deep unsupervised learning using nonequilibrium thermodynamies," in International Conference on Machine Learning, 2015, pp. 2256-2265.
[18] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg. "Structured denoising diffusion models in discrete state-spaces," Advances in Neural Information Processing Systems, vol. 34, pp. 17 919 993, 2021.
[19] E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, and M. Welling, "Argmax flows and multinomial diffusion: Learning categorical distributions," Advances Neural Information Processing Systems, vol. 34, pp. 12 122 465, 2021.
[20] 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.
[21] A. Hottung, B. Bhandari, and Tierney, "Learnnn latent search space for routing problems using variational autoencoders," in International Conference on Learning Representations, 2021.
[22] S. Geisler, J. 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.
[23] X. Zheng, Y. Li, C. Fan, H. Wu, X. Song, and J. Yan, "Learning plaintext-ciphertext crypto- graphic problems via anf-based sat instance representation," Advances in Neural Information Processing Systems, 2024.
[24] 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.
[25] 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. 9, pp. 5057-5069, 2021.
[26] X. Chen and Y. Tian, "Learning to perform local rewriting for combinatorial optimization," Advances in Neural Information Processing Systems, vol. 32, 2019.
[27] 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-26 211, 2021.
[28] 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.

---

[29] R. Cheng, X. Lyu, Y. Li, J. Ye. J. Hao, J.d Yan, "The sabicyggradeet placement and generative routing neural networks for chip design." Advances in Neural Information Processing Systems, vol. 35, pp. 26 350-26 362, 2022.
[30] 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.
[31] 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. 170100 2023.
[32] Y. Song and S. Ermon, "Generative modeling by estimating gradients of the data distribution," Advances in neural information processing systems, vol. 32, 2019.
[33] J. Ho, A. Jain, and P. Abbeel, "Denoising diffusion probabilistic models," Advances in Neural Information Processing Systems, vol. 33, pp. 6840-6851, 2020.
[34] J. Song. C. Meng, and S. Ermon, "Denoising diffusion implicit models," arXiv preprint arXiv:2010.02502, 2020.
[35] Y. Song and S. Ermon, "Improved techniques for training score-based generative models," Advances in neural information processing systems, vol. 33, pp. 12438-12 448, 2020.
[36] A. Q. Nichol and P. Dhariwal, "Improved denoising diffusion probabilissic models," in Interna- tional Conference on Machine Learning, 2021, pp. 8162-8171.
[37] P. Dhariwal and A. Nichol, "Diffusion models beat gans on image synthesis," Advances in Neural Information Processing Systems, vol. 34, pp. 8780-8794, 2021.
[38] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole, "Score-based generative modeling through stochastic differential equations," arXiv preprint arXiv:2011. 2020.
[39] N. Karalias and A. Loukas, "Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs," " Advances in Neural Information Processing Systems, vol. 33, pp. 6659-6672, 2020.
[40] 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.
[41] Y. LeCun, S. Chopra, R. Hadsell, M. Ranzato, and F, Huang, "A tutorial on energy-based learning," Predicting structured data, vol. 1, no. 0, 2006.
[42] A. Graikos, N. Malkin, N. Jojic, and D. Samaras, "Diffusion models as plug-and-play priors," arXiv preprint arXiv:2206. 0000000990.2... 2022.
[43] 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,
[44] D. Applegate, R. Bixby, V. Chvatal, and W. Cook, "Concorde tsp solver," 2006.
[45] K. Helsgaun, "An extension of the inn-kemmihhnn-eelsgan tsp solver for constrained traveling salesman and vehicle routing problems," Roskilde: Roskilde University, pp. 24-50, 2017.
[46] G. A. Croes, "A method for solving traveling-salesman problems," Operations research, vol. 6,
no. 6. pp. 791-812, 1958.
[47] X. Bresson and T. Laurent, "The transformer network for the traveling salesman problem," 2021.
arXiv preprint
[48] 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 arX1v:2004.01608, 2020.
[49] Gurobi Optimization, "Gurobi optimizer reference manual," " http::/www.gurobb.com 2020.
[50] M. Deudon, P. Courut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau, "Learning heuristics for the tsp by policy gradient," in International conference on the integration of constraint programming, artificial intelligence, and operations research. Springer, 2018, pp. 170-181.
[51] S. Lamm, P. Sanders, C. Schulzz, D. Strash, and R. F. Werneck, "Finding near-optimal indepen- dent sets at scale," in 2016 Proceedings of the Fighteenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2016, pp. 138-150.
12

---

[52] Z. Li, Q. Chen, and V. Koltun, "Combinatorial optimization with graph convolutional networks and guided tree search," Advances neural information processing systems, vol. 31, 2018.
[53] M. Böther, O. Kißig, M. Taraz, S. Cohen, K. Seidel, and T. Friedrich, "What's wrong with deep learning in tree search for combinatorial optimization," arXiv preprint arXiv:2201. 2022.
[54] S. Ahn, Y. Seo, and J. Shin, "Learning what to defer for maximum independent sets," in International Conference Machine Learning. 2020, pp. 134-144.
[55] P. Erdós, A. Rényi et al., "On the evolution of random graphs," Publ. Math. Inst. Hung. Acad. Sci, vol. 5, no. 1, pp. 17-60, 1960.
[56] B. Hudson, Q- Li, M. Malencia, and A. Prorok, "Graph neural network guided local search for the traveling salesperson problem," arXiv preprini //.::2//000591,, 2021.
[57] H. H. Hoos and T. Stützle, "Satlib: An online resource for research on sat," Sat, vol. 2000, pp- 283-2922 2000.
13

---

Appendix
A Training Details
A.1 Training Algorithm
Algorithm 2 Optimization Consistency Training
1: Input dataset D, consistency model fo(:;-) ), initial model parameter 9, learning rate n, consistency
loss function d(.;,) inference steps T, scaling factor a, Bernoulli noise matrix Q I,....T weighting
function X(-)
2:
3: repeat
4:
Sample x" ~ D. ~ [1, + [at]]
5:
Sample ~ x x Z2 x'Q21
6:
((0) f A(t)) (fo (z1.tl) ó(z1 - x)))) + (fo (z2, ,2),1(z) - x*))
7:
t 0 V)L(()
8:
9:
until convergence
A.2 Design Choices for Optimization Consistency
We supplement the specific design choices of the optimization consistency models, and the listed hyperparameters correspond to those used in the algorithm presented in sections and 5
Training
Design Choice
Consistency Loss Function d(æ, y) = Binaryy Crross Entropy(x, y)
Scaling Factor
0.5
Weighting Function
A(t) =
Discretization Curriculum
t~ {1,2, ... T), randomly sampling 17 = 0.0002
Initial Learning Rate
Learning Rate Schedule
Cosine decay, decay rate 0.0001
Test
Design Choice
Sampling Step Schedule
4 = T(1 sin irr22)). 1g = T(1 sin(N (i + 1)
Guided Weighting Parameters
À 50, X2 50 on TSP Åι
2, A2 MIS
Rewrite Ratio
= 0.2 on TSP and ER-[700-800]
= 0.3 on RB-[200-300]
B
Supplementary Experiments
B.1 Results on TSP Real-World Data
Results on TSPLIB 50-200. We evaluate our model trained with random 100-node problems on
real-world TSPLIB instances with 50-200 nodes. The compared baselines include DIFUSCO (7].
T2T 8 and baselines listed in [56]'s Table 3. The hyperparameter settings of the compared baselines are: DIFUSCO: T,=50; T2T: 5,=50 and =3= Fast T2T (w/o GS): T,=10; Fast T2T (w/ GS): T,=10
and 110 The diffusion- based methods are compared in the same settings with greedy decoding and Two-Opt post-processing For each instance, normalize the coordinates to [0.1].
Results on TSPLIB 50-200. We also supplement the results (optimality drop) of diffusion-based baselines and Fast T2T on large-scale TSPLIB benchmark instances with 200-1000 nodes. The models are trained on TSP-500 and inference with greedy decoding and Two-Opt post-processing. For each instance, normalize the coordinates to [].
14

---

Table 5: Solution quality for methods trained on random 100-node problems and evaluated on
TSPLIB instances with 50-200 nodes. denotes results quoted from previous works [56].
INSTANCES
AM*
GCN*
Leam20PT*
GNNGLS
DIFUSCO
T2T
Fast T2T (wlo GS)
Fast T2T (2T GS)
ci151 16.767%
40.025%
1.725%
1.529%
2.82%
0.14%
0.00%
0.00%
berlin52
4.169%
33.225%
0.449%
0.142%
0.00%
0.00%
0.00%
0.00%
st70
1.737%
24.785%
0.040%
0.764%
0.00%%
0.00%
0.01%
0.00%
ci176
1.992%.
27.411% %
0.096%
0.163%
0.34%
0.00%
0.00%
0.00%
pr76
0.816%
27.793%
1.228%
0.039%
1.12%
0.40%
0.00%
0.00%
ra199
2.645%
17.633%
0.123
0,550%
0.09%
0.00%
0.00%
kroA 100
4.017%
28.828%
18.31.3%
0.728%
0.10%
0.00%
0.00%
0.00%
kmB1000
19%
2.29%
0.65%
knc1100
0.9721%
0.349
1.571%
0.00%
0.00/
0
0.00%
2.717%
38.018%
0.572%
0.07%
kroE100
1.470%
26.589%
1.832%
1.216%
3.83%
0.27%
1.13%
0.00%
rd100
3.407%
50.432%
1.725%
0,003%
0.08%
0.00%
0.00%
0.00%
cil101
2.994%
26.701%
0.387
1.529%
0.03%
0.00%
0.00%
0.00%
10n
1.739%
34. 34.902%
1.66%
0.606%
0.00%
0.00%
0.00%
0.00%
pr107
3,933%
80.564%
8984
0,439%
0.91%
0.61%
1.31%
0.62%
pr124
3.677%
70.146%
10.322%
0.755
1.02%
0.60%
0.08%
0.08 %
b2er
.900%%
45.561%
3.044%
1.948%
0.94%
0.54%
.550%
1,50%
ch130
3.182%
39.090%
0.709%
3,519%
0.29%
0.06%
0.00%
0.00%
pr136
3.064%
58.673%
3.387%
0.01%
prl44
7 7.641%
55.817%
1.526%
3.581%
0.80%
0.50%
0.39%
0.39%
ch
4.584%
49.743%
0.312
2.113%
0.57%
0.49%
000%
0.00%
150
3,784%
45.411%
0.724
2.984%
0.34%
0.14%
0.00%
0.00%
kroB
2.437%
56.745%
0.886%
3,258%
0.30%
0.00%
0.07%
0.07%
pr152
7.494%
33,925%
0.029%
3.119%
1.69%
0.83%
1.17%
0.19%
u159
7.551%
38.338%
0.054%
1.020%
0.82%
0.00%
0.00%%
0.00%
ra1195
6.893%
24.968%
0.743
1.666%
1.48%
1.27%
0.79%
0.79%
d198
373.020%
62.351%
0.522%
4,772%
3.32%
1.97%
1.35%
0.86%
kroA200
7.106%
40.885%
1441%
2.029%
2.28%
0.57%
1.79%
0.49%
kroB200
8.541%
43.643%
2.064%
2.589%
2.35%
0.92%
2.50%
2.50%
Mean
16.767%
40.025%
1.725%
1.529%
0.97%
0.35%
0.41%
0.28%
Table 6: Solution quality for methods trained on random 500-node problems and evaluated on TSPLIB instances with 200-1000 nodes.
INSTANCES
DIFUSCO
T2T
Fast T2T (w/o GS)
T2T (w/ GS)
a280
1.39%
1.39%
4.58%
0.10%
d493
1.81%
1.81%
3.48%
1.43%
d657
4.86%
2.40%
1,91 %
0.64%
f1417
3.30%
3.30%
7,45%
2.01% 1
gil262
2.18%
0.96%
0.64%
0.18%
lin318
2.95%
1.73%
2.24%
1.21 %
linhp318 38
2.17%
1.1
2.00%
0.78%
p654
7.49%
1.19%
4.84%
1.67%
pcb442
2.59%
1.70%
1.47%
0.61% %
pr226
4.22%
0.84%
0.66%
0.34%
pr264
0.92%
0,92%
0.77%
0.73%
pr299
1.46%
1.46%
2.16%
1.40%
pr439
2.73%
1.63%
0.53%
0.50%
rat575
2.32%
1.29%
1.74%
1.43%
rat783
3.04%
1.88%
1.76%
1.03%
rd400
1.18%
0.44%
0.16%
0.08%
ts225
4.95%
2.24%
3.31%
1.37%
tsp225
3.25%
1.69%
0.84%
0.81%
u574
2.50%
1.85%
1.31%
0.94%
u724
2.05%
2.05%
2.15%
1.41%
Mean
2.87%
1.59%
2.20%
0.93%
B.2 Results MIS Real-World Data
We supplement the results on the SATLIB real-world dataset [57] below. Initially, we did not include the SATLIB results because Fast T2T requires more data to learn the consistency mapping, which, due to its greater power, is more challenging to learn. Unfortunately. SATLIB does not provide sufficient data for this purpose. However, we still discover positive results of Fast T2T outperforming previous baselines.
15

---

Table Results on MIS SATLIB dataset.
Type
Method
Size
Drop
Time
Heuristic
KAMIS
425.96
37.58m
Gurobi
Exact
425.95
0.00%
26.00m
RL+Sampling
LwD
422.22
0.88%
18,83m
RL+Sampling
DIMES
423.28
0.63%
20.26m
UL+Sampling
GlowNets
423.54
0.57%
23.22m
SL+Sanpling
DIFUSCO (T, = 100)
425.14
0.19%
53m41s
SL+Sampling T2T (T, 50, T 30)
425.18
0.18%
38m1s
SLmSanlg
Fast T2T (T, = 5, Tg = 5)
425.23
0.17%
25m35s
B.3 Results for Generalization TSP Datasets
Fig. visualized the performance of DIFUSCO, T2T, and Fast T2T on different scales of TSP instances. The experimental settings are the same to Sec. 6.1
DIFUSCO (T:=50) Drop (%)
T2T (T:=50, T,=30) Drop (%)
0.09
0.25
2.55
2.71
TSP-50
0.02
0.11
1.60
1.10
Training problem
Training problem
TSP-100
1.44
0.23
3,44
3.31
TSP-100
50P
TSP-500
3.79
2.25
0.81
1.00
4.54
3.98
2.30
2.21
TSP-1000
4.66
3.16
1.51
1.23
T5P.50
TSP-100
TSP-500
TSP-1000 1000
TSP-50
TSP-100
TSP-500
TSP-1000
Testing problem
Testing problem
Fast T2T (T 5==5)
(%)
Fast T2T (T,-20 T.=20) Drop (%)
TSP-50
0.01
0.02
0.36
1.02
TSR50
0.00
0.01
Training problem
Training problem
TSP-100
0.12
0.02
0.40
0.55
7SP-100
0.08
0.01
0.23
0.34
TSP-500
2.67
2.87
0.36
0.51
TSP-500
2.34
2.54
0.20
0.33
TSP-1000
3.43
4.15
0.82
0.56
3.22
3.87
0.58
0.36
TSP 50
TSP-100
1SP.500
TSR-1000
TSP-50
TSR100
73P-500
TSP-1060
Testing problem
Testing problem
Figure 7: Confusion matrix of four scales from TSP datasets. Models are trained on scales on the y-axis, and tested with Greedy Decoding on scales on the r-axis. Values in matrices are corresponding drop compared to exact solvers.
B.4 Results for Generalization on MIS
We provide supplementary results for generalization results on the MIS problem below. We the model trained on ER 700-800 with 0.15 to different (the probability that each simple edge exists) and n (graph size). find that the generalization ability Fast T2T is significantly better than that of the previous diffusion-based methods DIFUSCO and T2T regarding both solution quality and speed, e.g., ER 350-400 Sampling setting Fast T2T achieves significant performance gain from (23.28% 24m31s) to (1 (11.4%% Imls). Results are presented in Tables 8 and
16

---

Table 8: Generalization Performance from p 0.15 to
0.2, p
0.3, and p 0.4.
Type
Method
Size
Drop
Time
DIFUSCO (7, 100)
26.25
25.65%
6m31s
T2T (T, 50, T, 30)
27.84
21.13%
7m52s
Greedy
Fast T2T (T, -1,T,-
20.58%
32s
Fast T2T (I, =5.7
29.52
16.38%
1m57s
0.2
DIFUSCO (T, 100)
27.98
20.73%
27m15s
T2T (T, 50,7, 30)
28.07
20.49%
33m58s
Sampling
Fast T2T (T, = =,, 1)
28.81
18.39%
1m40s
Fast T2T =,,T, 5)
30.10
14.74%
6ml3s
DIFUSCO (T, (T, 100)
15.84
34.99%
7m58s
T2T (T, = -50,7, 30)
16,43
32.55%
8m20s
Greedy
Fast T2T (T, = =.,T, 1)
17.43
28.45%
51s
Fast T2T (T, =0 =5,T, 5)
17.69
27.39%
2m52s
DIFUSCO (T, 100)
17.17
29.52%
30m3s
T2T (T, =50,-00,7, =3)
16.38
32.78%
37m27s
Sampling
Fast T2, = =1,7, 1)
17.79
26.97%
2m2s
Fast T2T (T, =5,,, 5)
18.38
24.53%
8m36s
DIFUSCO (T, - 100)
11.75
35.40%
9m40s
T2T (T, 50. 30)
12.77
29.77%
10m28s
Greedy
Fast T2T (T, =,,T,
12.86
29.30%
Imls
Fast T2T (I, =5,T, 5)
13.27
27.06%
3m36s
0.4
DIFUSCO (I, 100)
12.69
30.21%
40m22s
T2T (T, 50,T, = 30)
13.03
28.33%
45m2s
Sampling
Fast T2T (T, =1,7, 1)
13.31
26.80%
2m1 2s
Fast T2T (T, T, 5)
13.56
25.43%
8m58s
Table Generalization Performance from ER 700-800
ER 350-400 and 1400-1600.
Decoding
Method
Size
Drop
Time
DIFUSCO 100)
27.31
28.04%
Smls
Greedy
T2T (I. 50, 30)
28.54
24.80%
6m59s
Fast T2T T2, =I,=
32.56
14.20%
22s
350-400
DIFUSCO (T) = 100)
29.33
22.73%
20m12s
Sumpling
T2T (T, 50,T, 30)
29.12
23.28%
24m31s
Fast T2T (T,
33.61
11.45%
Imls
DIFUSCO (T, 100)
34.39
32.48%
22m7s
Greedy
T2T T2T = 50, 30)
0OM
0OM
OOM
Fast 121 (T, 11,7,
36.95
27.47%
1m39s
1400-1600
DIFUSCO (T, 100)
35.55
30.21%
1h27m31s
Sampling
T2T (I. 50.T, 30)
0OM
OOM
OOM
Fast T2T (T. 1.T 1)
38.59
24.25%
3m56s
We also supplement cross-dataset generalization results between RB graphs and ER graphs in Table 10 As seen, Fast T2T outperforms previous diffusion-based counterparts by a clear margin, e-g., in "Train:ER; Test:RB" "Sampling" setting, Fast T2T achieves significant performance gain from the previous (23.24 23, 30m13s) to (9.10%, 4m20s).
C Experimental Details
C.1
Computational Resources.
Test evaluations on TSP-50/100 and MIS are performed on a single GPU of NVIDIA RTX 4090, and evaluations TSP-500/1000 performed on single GPU of NVIDIA Telsla A100.
C.2 Graph Sparsification.
For large-scale TSP problems, we follow 7 to employ sparse graphs, as sparsified by constraining each node to connect only its & nearest neighbors, determined by Euclidean distances. For TSP-500,
17

---

Table 10: Performance Comparison Between Greedy and Sampling Methods (Train:ER: Test:RB).
Setting
Type
Method
Size
Drop
Time
DIFUSCO (T, 100)
15.87
21.00%
10m8s
T2T (T, = 50, 30)
16.59
17.41%
15m5s
Greedy
Fast T2T (7,, 1,7, 00TT,=1 = 1)
16.73
16.59%
40s
Fast T2T (7', =,7, = 5)
17.01
15.21 %
2m39s
Train:ER; Test:BB
DIFUSCO (T; 100)
16.75
16.62%
41m0s
T2T (T, 50, 30)
16.80
16.40%
29m48s
Sampling
Fast T2T (T, = 1, 1)
17.29
13.78%
57s
Fast T2T (7), 5,T, = 5)
17.38
13.38 %
4m33s
DIFUSCO (T; 100)
29.98
27.54%
10m48s
T2T (T, - 50, - 30)
31.47
23.96%
13m40s
Greedy
Fast T2T (?', = 1, =)
36.39
11.96%
43s
Fast T2T (T: =6
36.94
10.64 %
2m37s
Train:E;; Test:RB
DIFUSCO
100)
31.67
23.47%
44m0s
T2T (T, 50,T, 30)
31.77
23.24%
30m13s
Sampling
Fast T2T (T. =, =1
36.84
10.90%
57s
Fast T2T (T, = =5,T, 5)
37.58
9.10%
4m20s
set k = 50, and for TSP- 100. This strategy prevents the exponential increase in edges typical in dense graphs as node count rises.
C.3
Datasets.
The reference solutions for TSP-50/100 are labeled by the Concorde exact solver 44 and the solutions for TSP-500/1000 are labeled by the LKH-3 heuristic solver [45). The test set for TSP. 50/100 is taken from 2 3 with 1280 instances and the test set for TSP-500/1000) is from 12 with 128 instances for the fair comparison.
The reference solutions for both RB graphs and ER graphs are labeled with KaMIS [51] For RB graphs, we randomly generate 90000 instances for the training set and 500 instances for the test set. For ER graphs, we randomly generate 163840 instaces for the training set and the test is from [6].
C.4 Training Resource Requirement
We outline the offline training resource requirements of the Fast T2T framework Table 11 with computations conducted on A100 GPUs. For contextual comparison, AM (2) necessitates 28M instances generated on-the-fly to train TSP- 100, consuming 45.8 hours on 1080Ti GPUs. POMO mandates 200M instances generated dynamically for TSP-100 training, entailing approximately one week on a single Titan RTX. Sym-NCO (5), an extension of POMO, requires approximately two weeks on single A100 for training. Additionally, Sym-NCO (5) built upon AM [2] necessitates three days on 4 100 GPUs. Compared with DIFUSCO (7), Fast T2T necessitates approximately double training time and GPU memory under the same settings, because consistency training method requires forward twice for each training instance, leading to more time and memory consumption.
Table 11: Details about the training resource requirement of Fast T2T framework. The results are calculated on A100 GPUs
Problem Scale
Dataset Size
Batch Size
GPU
GPUs
GPUs
GPU Mem
TSP-50
1,502 k
32
112h 45m
62h 24m
41h 16m
16.5 GB
TSP-100
1,502
12
488h
268h 37m
139h 26m
GB
TSP-500
128 k
6
142h 17m
78h 58m
45h 2m
37.8 GB
1000
64
4
324h 43m
185h26s
101h 3m
20.2 GB
C.5 Hyperparamters
We conduct experiments on TSP and MIS benchmarks with our methods and compare the performance with prevalent learning-based solvers, heuristics, and exact solvers. The noise degree a associated with each benchmark is listed in Table. 22
18

---

Table 12: Noise Degree for each benchmark.
Benchmark
ISP-50
TSP-100
TSP-500
TSP-1000
RBB-200-300)
ER-1200-800]
0.20
0.20
0.20
0.20
0.30
0.20
C.6 Baseline Settings
C.6.1 TSP Benchmarks
TSP-50/100: the evaluation of TSP-50 and TSP-100, we compare our proposed Fast T2T against 11 baseline methods. These baselines include one exact solver, Concorde [44], two heuristic solvers 2OPT [46] and Farthest Insertion and seven learning- based solvers: AM (2), GCN [3), Trans- former 47 POMO [4] Sym-NCO [5], Image Diffussin 42). DIFUSCO 77,, and T2T (8) Our
post-processing involves greedy sampling and 2OPT refinement. To ensure equitable comparisons in terms of computational effort, limit the number of inference steps for DIFUSCO to 100, and for T2T, we set the number of inference steps and guided search steps to 50 and 30, respectively.
TSP-500/1000: In the evaluation of TSP-500 and TSP-1000, our method is compared with 2 exact
solvers, Concorde 44 and Gurobi [49], heuristic solvers, LKH-3 (45) and Farthest Insertion, and learning-based methods, including EAN [50], AM 22 GCN 3 POMO+EAS [15, DIMES [6. and DIFUSCO 77. These learning-baae based methods can further categorized into supervised learning (SL) and reinforcement learning (RL). Post- Post-processing techniques employed encompass greedy sampling (Grdy, G). multiple sampling (S), 2OPT refinement (2OPT), beam search (BS), active search (AS), and combinations thereof. To ensure fair comparisons in terms of computational resources, cap the number of inference steps for DIFUSCO at 100. Additionally, for T2T, we fix the number of inference steps and guided search steps at 50 and 30, respectively.
C.6.2 MIS Benchmarks
We assess our method on two distinct benchmarks: RB-(200-300) and ER-[700-800), Across both benchmarks, we compare the performance of Fast T2T against exact solver, Gurobi 44] one
heuristic solver, KaMIS [51] and learning-bass -based frameworks: Intel [52]. DGL [52], LwD [54], DIMES (6), and DIFUSCO M7 Post- poot-processing strategies encompass greedy sampling (Grdy) and tree search (TS). Specifically, on both benchmarks, we set the number of inference steps at 100 for DIFUSCO. For T2T, we set the number of inference steps and guided search steps 50 and 30, respectively.
D Network Architecture Details
D.1 Input Embedding Layer
Given node vector x N2 weighted edge vector R denoising timestep / {TI,..., TM J. where N denotes the number of nodes in the graph, and E denotes the number of edges, we compute the sinusoidal features each input element respectively:
T; concat(Ti.o. Ti,1)
(9)
sin Li.j T
Fi.j
Fi.j
Ti.j
Fi.j
Fi.j
J concat
008
sin
008
sin
COS
(10)
T
T
T
e
ē concat
sin 7
CO8
sin
sin
COS
(11)
T
T
T
T
t
t
t
= concat
sin T
CO8
sin
008
sin
CO8
(12)
T
T
T
7
T
where d is the embedding dimension, T large number (usually selected as 10000), concat denotes concatenation.
19

---

Next, we compute the input features of the graph convolution layer:
5 WP
(13)
0 W
(14)
5 = W((RCLU(W33)
(15)
where 1 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 e is computed above. For MIS, we initialize e a zero matrix Bxxd
D.2 Graph Convolution Layer
Following
S the cross-layer convolution operation is formulated as:
2 ot + ReLW(B + Σ Thy @ W2a)))
(16)
j
1
I+1 c ReLU
(17)
a(el))
T/i Eymi (dy)
(18)
where æ! and ciy denote the node feature vector and edge feature vector layer 1, Wi,".., Ws Raxh denote the model weights, n/ 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:
c dy ReLU(B + Wtat wsa/)) + ()(
(19)
For MIS, we aggregate the timestep feature with the node convolutional feature and reformulate the update for node features follows:
=
o + ReL
Σnl o w + (((LLU)()))
(20)
jM
D.3
Output Layer
The prediction of the edge heatmap in TSP and node heatmap in MIS as follows:
eij = Softnaxxporm((eLll
(21)
T; Softmax(norm(eeLL(WWW
(22)
where L is the number of GCN layers and norm is layer normalization.
D.4 Hyper-parameters
For both TSP and MIS tasks, construct 12-layer GCN derived above. We the node, edge, and timestep embedding dimension = 256, 128 for TSP and MIS tasks, respectively.
E Limitations and Broader Impacts
As the scale increases, our method's 's improvement in solving speed compared to diffusion- based methods will experience a certain degree of attenuation. This is because, with the expansion of the scale, the proportion of time required for relevant serial processing becomes larger, while the proportion of time for model inference is squeezed, resulting in weakening of the speed improvement the overall pipeline. This limitation can be addressed by combining our model with more efficient traditional solving strategies, which we leave for future work. Since the consistency model requires
20

---

two inference predictions with different noise levels during training, it requires twice the training cost of the original diffusion model. However, this overhead on training is offline, and the consistency model is much more efficient than diffusion at inference time.
powerful and efficient backbone for neural combinatorial optimization, enabling significant performance improvement and versatility, making its application feasible across various solving frameworks. This work can be integrated into existing and future research in this field, driving progress in related studies.
Our work provides
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction explicitly state the claims made, including the contributions made in the paper (Sec. The claims match the experimental results in
Sec. 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Appendix
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: The theoretical derivation of this paper has been given in Sec. and there no additional theorems needed be proved.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experimental details are in 6 Append. source code publicly available upon acceptance.
We will make our
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
23

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
The source code will be made publicly available upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //ipss.cc/pill wttp:ccppppcccceeeeeeeeee..c.ett httpa///giiieee/eeeeebiiissssss (Cooeooomiissssseeeeeeee ssioioliccyyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
The experimental details are in Sec. a Append. B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: follow the setting of previous works report the average solution quality over 128 or 1,280 instances Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the testing GPUs and cinecconsunttion our methods as well as previous works in Sec. 6 The training resource requirement is in Appendix. C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttp:://neurip::::: http://ss...pppooococccccccccala
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the borader impacts in Appendix.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The original papers that introduce models and datasets used in the paper cited in Sec.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Currently, the paper does not release assets. Our source code will be released upon the acceptance of the paper with comprehensive documents. As parts of the documents, formally describe proposed model and the corresponding details in Sec. and
The training details are presented in Appendix.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not incur such risks.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
27

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "7mgUuDDrWq", "reviewer": "Reviewer_3pWn", "summary": "This paper introduced a new algorithm for solving some classic combinatorial optimization problems. The method falls into the category of learn-based generative solvers. More specifically, it is a direct extension of the DIFUSCO [1] and T2t [2] solver, which are diffusion-based generative solvers. The improvement is mostly done through improving on the sampling step of the two aforementioned works with consistency models (CM) [3], a recent notable regime that enables drastic reduction of the number of function evaluations (NFE, or sampling steps) of vanilla diffusion models. The novelty lies in extending CM into discrete regime and combining it with consistency-based gradient search, which is necessary for combinatorial optimization problem. Empirical evaluations show the effectiveness of this new solver, where it achieves competitive objective value in a much shorter time, compared to various baselines. \n\n\n[1] Z. Sun and Y. Yang, “DIFUSCO: Graph-based diffusion solvers for combinatorial optimization, in Thirty-seventh Conference on Neural Information Processing Systems, 2023. \n\n[2] Y. Li, J. Guo, R. Wang, and J. Yan, “T2t: From distribution learning in training to gradient search in testing for combinatorial optimization,” in Advances in Neural Information Processing Systems, 2023.\n\n[3]  Y. Song, P. Dhariwal, M. Chen, and I. Sutskever, “Consistency models,” arXiv preprint arXiv:2303.01469, 2023", "questions": "See weakness.", "limitations": "Consistency training introduced additional training overhead; I think the authors did not discuss this in Appendix D.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Overall I think the method is novel. The extension of consistency training framework into diffusion-based CO solvers is not trivial, and this work is trying to solve a well-motivated problem. The empirical evaluations are quite convincing compared to diffusion-based CO solvers (of course, one expects so as consistency models inference time is much faster than diffusion generative models). \n\n2. The paper is overall well-written, and the authors seem to have done quite thorough literature reviews to gather sufficient baselines to compare to the performance of their work to.", "weaknesses": "1. It is necessary to elaborate on why the authors wrote \"... note F1 is exactly the (implicit) the objective of the diffusion and consistency models...\" at line 259. In other words we need to see why (should be a lemma with proof) we have the quantity $F_1$ in equation (6) is the equivalence of the loss in eq (4).\n\n2. It is unclear how the overall training paradigm takes place in practice, including the gradient search part. The authors should include an algorithm box on the training of their OptCM framework. Algorithm 1 on Multistep Consistency Sampling is almost the same as in the original Consistency Models paper, so I suggest the authors move them to the Appendix. If I'm not mistaken, the training of consistency models is quite tricky, for example, it is crucial to design a suitable training time discretization schedule for CM to work well. Could the authors elaborate on this for their problem? \n\n I'm willing to re-evaluate my score if the authors can answer these two points.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and insightful suggestions, as well as for acknowledging our novelty, motivation,  non-trivial contributions, and convincing evaluations. Your questions and suggestions are instrumental in further strengthening our paper. Below, we respond to your specific comments.\n\n> **Q1: Why we have the quantity F1 in equation (6) is the equivalence of the loss in eq (4)?**\n\nThanks for your valuable suggestion. We will supplement the derivation and intuition to the paper.\n\nRecall that $F_1=-\\mathbb{E}\\_{q(\\mathbf{x}|G)q(\\mathbf{h}|\\mathbf{x},G)}\\left[\\log p_\\theta(\\mathbf{x},\\mathbf{h}|G)- \\log q(\\mathbf{x})q(\\mathbf{h}|\\mathbf{x},G)\\right]$, we apply an approximation to the posterior over $\\mathbf{x}=\\mathbf{x}\\_0$ as a point estimate $q(\\mathbf{x}|G)=\\delta(\\mathbf{x}-\\mathbf{\\eta})$ and obtain $F_1=\\mathbb{E}\\_{q(\\mathbf{h}|\\eta,G)}\\left[\\log\\frac{q(\\mathbf{h}|\\mathbf{\\eta},G)}{p_\\theta(\\mathbf{\\eta},\\mathbf{h}|G)}\\right]$. This term is exactly the usual variational bound on negative log likelihood conditioned on graph $G$, which is exactly the optimization objective of the diffusion models. It can be further derived under the denoising diffusion framework similarly in the original DDPM paper:\n$$\\begin{aligned}F\\_1&=\\mathbb{E}\\_{q(\\mathbf{x}\\_{1:T}|\\eta,G)}\\left[\\log\\frac{q(\\mathbf{x}\\_{1:T}|\\mathbf{\\eta},G)}{p\\_\\theta(\\mathbf{\\eta},\\mathbf{x}\\_{1:T}|G)}\\right] \\\\\\\\ &= \\mathbb{E}\\_{q} \\left[ \\log \\frac{\\prod\\_{t=1}^T q(\\mathbf{x}\\_t | \\mathbf{x}\\_{t-1},G)}{p\\_\\theta(\\mathbf{x}\\_T) p\\_\\theta(\\eta | \\mathbf{x}\\_1, G) \\prod\\_{t=2}^T p\\_\\theta(\\mathbf{x}\\_{t-1} | \\mathbf{x}\\_t, G)} \\right] \\\\\\\\ &= \\mathbb{E}\\_q \\left[ -\\log p\\_\\theta(\\mathbf{x}\\_T) + \\sum\\_{t=2}^T \\log \\frac{q(\\mathbf{x}\\_{t}|\\mathbf{x}\\_{t-1},G)}{p\\_\\theta(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t, G)} + \\log \\frac{q(\\mathbf{x}\\_1|\\eta, G)}{p\\_\\theta(\\eta|\\mathbf{x}\\_1, G)} \\right]            \\\\\\\\ &= \\mathbb{E}\\_q \\left[ -\\log p\\_\\theta(\\mathbf{x}\\_T) + \\sum\\_{t=2}^T \\log \\left( \\frac{q(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t, \\eta,G) }{p\\_\\theta(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t,G)}\\cdot \\frac{q(\\mathbf{x}\\_t|\\eta,G)}{q(\\mathbf{x}\\_{t-1}|\\eta,G)} \\right) + \\log \\frac{q(\\mathbf{x}\\_1|\\eta,G)}{p\\_\\theta(\\eta|\\mathbf{x}\\_1,G)} \\right] \\\\\\\\ &= \\mathbb{E}\\_{q} \\left[ \\log \\frac{q(\\mathbf{x}\\_T|\\eta,G)}{p\\_\\theta(\\mathbf{x}\\_T)} + \\sum\\_{t=2}^T \\log \\frac{q(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t, \\eta,G)}{p\\_\\theta(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t,G)} - \\log p\\_\\theta(\\eta|\\mathbf{x}\\_1,G) \\right] \\\\\\\\ &= \\mathbb{E}\\_{q} \\left[ D\\_{KL}(q(\\mathbf{x}\\_T|\\eta,G) \\| p\\_\\theta(\\mathbf{x}\\_T)) + \\sum\\_{t=2}^T D\\_{KL}\\left(q(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t, \\eta,G) \\| p\\_\\theta(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t,G)\\right) - \\log p\\_\\theta(\\eta|\\mathbf{x}\\_1,G)\\right] \\\\\\\\ &= \\sum\\_t \\mathbb{E}\\_{q} \\left[D\\_{KL}\\left(q(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t,\\eta,G) \\| p\\_\\theta(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t,G)\\right)\\right] + C \\end{aligned}$$\nThis term is the optimization objective on point estimate $\\eta$. While in optimization consistency models, we do not directly predict $p\\_\\theta(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t,G)$ in the objective calculation, but we can virtually estimate this term using an additional predicted  $\\hat{\\eta}$ : \n$$\\begin{align}p\\_\\theta(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t,G)=q(\\mathbf{x}\\_{t-1}|\\mathbf{x}\\_t,\\hat{\\eta},G)=q(\\mathbf{x}\\_{t}|\\mathbf{x}\\_{t-1},\\hat{\\eta},G)\\frac{q(\\mathbf{x}\\_{t-1}|\\hat{\\eta},G)}{q(\\mathbf{x}\\_t|\\hat{\\eta},G)}.\\end{align}$$\nThen $F\\_1$ can be reduced to the distance between the estimated $\\hat{\\eta}$ and the real $\\eta$, i.e., \n$$\\begin{align} F\\_1 = \\sum\\_t \\mathbb{E}\\_{q} \\left[d\\big(p\\_\\theta^t(\\eta),\\delta\\left(\\mathbf{x}-\\mathbf{\\eta}\\right)\\big)\\right] + C,\\end{align}$$\nwhich is equivalent to the consistency loss which optimizes points from different noise level to map to the target point.\n\n> **Q2: The authors should include an algorithm box on the training of their OptCM framework.**\n\nThanks for the nice advice. We have included specific training algorithms in the PDF attachment of the general response and will incorporate them into our paper.\n\n\n> **Q3: More discussions on training details.**\n\nWe supplement the specific design choices of our OptCM, and the listed hyperparameters correspond to those used in the algorithm presented in the paper. We will supplement these details to the paper to enhance its comprehensiveness. \n\nMoreover, we affirm our commitment to making the source code publicly accessible upon publication. The objective of this work is to provide reference and contributions for the community. Open-sourcing the code is a fundamental obligation we undertake.\n\n|Train|Design Choice|\n|-|-|\n|Consistency Loss Function|$d(x,y)=$Binary_Cross_Entropy$(x,y)$|\n|Scaling Factor|$\\alpha=0.5$|\n|Weighting Function|$\\lambda (t)=1$|\n|Discretization Curriculum|$t\\sim \\{1, 2,...,T\\}$, randomly sampling|\n|Initial Learning Rate|$\\eta=0.0002$|\n|Learning Rate Schedule|Cosine decay, decay rate $\\omega=0.0001$|\n\n|Test|Design Choice|\n|-|-|\n|Sampling Step Schedule|$t_1=T(1-\\sin(N\\cdot i\\pi/2))$, $t_2=T(1-\\sin(N\\cdot (i+1)\\pi/2))$|\n|Guided Weighting Parameters|$\\lambda_1=50$, $\\lambda_2=50$ on TSP  <br> $\\lambda_1=2$, $\\lambda_2=2$ on MIS|\n|Rewrite Ratio| $\\epsilon=0.2$ on TSP and ER-[700-800] <br> $\\epsilon=0.3$ on RB-[200-300]|\n\n> **Q4: Consistency training introduced additional training overhead; I think the authors did not discuss this in Appendix D.**\n\nThanks for your careful review and suggestion. Since the consistency model requires two inference predictions with different noise levels during training, it requires twice the training cost of the original diffusion model. However, this overhead on training is offline, and the consistency model is much more efficient than diffusion at inference time. We will supplement this in our new revision.\n\n---\n\nWe hope this response could help address your concerns, and we are more than happy to address any further concerns you may have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b00iapDwKL", "reviewer": "Reviewer_P6jy", "summary": "This paper presents Optimization Consistency Models (OptCM) for solving combinatorial optimization (CO) problems efficiently. By leveraging the consistency model, OptCM maps varying noise levels to optimal solutions in a single step, significantly reducing computational overhead. This approach is validated through extensive experiments on the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), demonstrating significant superior efficiency compared with state-of-the-art diffusion-based models.", "questions": "See weaknesses.", "limitations": "The authors have discussed the limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper introduces a consistency model to improve the efficiency of diffusion-based combinatorial optimization solvers.\n2. Extensive experiments on TSP and MIS show that OptCM can outperform existing methods.", "weaknesses": "1. This work is mainly incremental, based on previous works DIFUSCO [1] and T2T [2].\n2. Larger-size TSPs, such as those with 100000 nodes, should be tested against state-of-the-art learning-based methods [3].\n3. Despite significantly improving solving efficiency, the proposed method is limited in addressing constrained COPs (e.g., CVRP and more complex COPs) and requires optimal solutions as labels.\n\n[1] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization, NeurIPS, 2023.\n\n[2] T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization, NeurIPS, 2023.\n\n[3] GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time, AAAI, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comment, nice suggestions, and for acknowledging our soundness, presentation, experimental extensiveness, and empirical performance. We seriously value the main novelty concern reflected in the comment and carefully address it in the general response. Below we respond to your specific comments. \n\n> **Q1: This work is mainly incremental, based on previous works DIFUSCO and T2T.**\n\nOptCM is inspired by some excellent previous works, which is one of the key supports for its ability to achieve such strong experimental results. However, we must note that the technical contributions of OptCM are highly non-trivial. Please kindly refer to the general response for the specific novelty claim, which we also briefly summarize here:\n\n1. Compared to DIFUSCO and T2T's diffusion models, OptCM's model design, including the model inference process and the training objective function, is very different. Indeed, consistency models are recognized as a new independent class of generative models in generative tasks, while we further establish optimization consistency models (OptCM) to tailor the model for optimization scenarios.\n2. The testing-phase gradient search method proposed by OptCM represents a completely novel approach compared to that of T2T. In fact, due to the difference between consistency mapping and diffusion inference, OptCM's framework and implementation are fundamentally independent. \n3. In terms of experimental results, OptCM demonstrates exceptional performance, not only in solution efficiency but also in the quality of the solutions. We believe such strong empirical results substantiate the claim that OptCM represents more than just incremental progress within the existing diffusion framework.\n\nIn addition, the reviews from reviewers 3pWn and rpwx firmly support our novelty claims: \"Overall I think the method is novel. The extension of consistency training framework into diffusion-based CO solvers is not trivial, and this work is trying to solve a well-motivated problem. The empirical evaluations are quite convincing compared to diffusion-based CO solvers.\" “Overall, the paper's strengths lie in its innovative approach to reducing computational complexity while maintaining high solution quality, its robust and versatile model design, and its impressive performance on benchmark tasks.”\n\n> **Q2: Larger-size TSPs, such as those with 100000 nodes, should be tested against state-of-the-art learning-based methods like GLOP.**\n\nThanks for the valuable question. In the rebuttal phase, we extend our model training to TSP-10000 and compare OptCM with several baselines, including DIFUSCO and GLOP.\n\n|Method|Length|Drop|Time|\n|-|-|-|-|\n|GLOP|75.62|5.36%|32s|\n|GLOP more revisions|75.29|4.90%|1.8m|\n|DIFUSCO(T_s=100)+2Opt|73.57|2.51%|31m24s|\n|OptCM(T_s=5)+2Opt|72.94|1.63%|15m35s|\n\nWe also explore generalizing the model to 100k nodes to assess its scalability. However, we discover that although OptCM can achieve quick prediction in seconds, the greedy decoding procedure—which sequentially inserts edges or nodes with the highest confidence into the partial solution until a feasible solution is obtained—can be prohibitively time-consuming, making it meaningless for the evaluation. OptCM is not yet suitable for large-scale evaluations without an optimized decoding procedure or a high-level divide-and-conquer strategy like GLOP. Indeed we suggest that there may be a chance for the combination of OptCM's backbone model and GLOP's divide-and-conquer strategy for scalability. \n\nWe will add the above evaluation to our paper and include the discussion of GLOP in related work and future work discussion to enhance the comprehensiveness of the paper.\n\n> **Q3: Limitations in addressing constrained COPs and supervision requirements.**\n\nIn fact, our method can handle various constrained problems. We rely on the powerful expressive capability of generative models to learn the constraints, ensuring that the generated heatmap results are as close to feasible as possible. This is followed by post-processing (e.g., greedy algorithms) to utilize the model's output while strictly satisfying the constraints. This paradigm theoretically handles any constraint, which is also the approach used in previous mainstream works such as Diffusco and T2T. However, for more complex constraints, the model's ability to capture constraints may be limited. In such cases, using sequential models to explicitly control constraints at each step can be more effective. For example, the mainstream methods for the CVRP problem are still based on sequence models.\n\nNevertheless, heatmap methods have their own advantages, such as not suffering from the sparse reward problem, enabling them to end-to-end handle larger-scale problems with better solution quality. These methods are currently the SOTA for classic problems like TSP and MIS, highlighting their strengths. There has also been considerable works in leading conferences that maintain competitive performance, demonstrating the value of this line of research. Additionally, currently works focusing on extending neural solvers for larger-scale problems using divide-and-conquer paradigms become a new important line of research. \n\nWe believe that different methodological routes have their own expertise in dealing with problems of different characteristics, and each route has its own advantages and disadvantages. We will add these discussions to our paper, including a discussion of some recent works such as GLOP and LEHD [1].\n\n---\nWe hope this response can help address your concerns. We believe that this work contributes to this community and could potentially provide a more powerful backbone for future works in this domain. We would sincerely appreciate it if you could reconsider your rating, and we are more than happy to address any further concerns you may have.\n\n[1] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ux8LKdi2B5", "reviewer": "Reviewer_rPB6", "summary": "This paper advances CO DM-based neural solvers under the setting where labeled training graphs are available by considering Consistency Models and gradient search (which was adopted from T2T).", "questions": "1- Generalization is a major problem for supervised neural solvers. The need to train a different model for each graph distribution is a bottleneck for these solvers. For example, in the MIS problem, how does a CM trained on ER700 with p=0.15 generalize when faced with an ER700 test instance with p=0.2? Which p would require different training given that n=700? Furthermore, does the proposed approach need to train a different model for ER2000 with p=0.15? These need to be explicitly explained/investigated as these could be considered as a limitation of the proposed method. The MIS problem differs based on different densities and degree distributions, not only the graph size. SATLIB, GNMs, SBMs can be considered. \n\n2- How does the size of the training dataset impact the outcomes? \n\n3- How does the proposed method handle real-world graphs (such as the SNAP graphs in https://snap.stanford.edu/data/)? What would be the training dataset? In most cases, these graphs do not follow a certain degree distribution or density. This is a major limitation in this method and all other learning-based methods. This point needs to be clearly discussed in the paper. As an alternative, the authors should clearly state that the proposed method only operates when training data points (with true optimal solutions) are available. \n\n4- Scalability results are missing for dense and sparse graphs if the models do generalize to higher n and same density. \n\n5- The run-time comparison with heuristics and ILP solvers does not include training times. The authors should either include them, or explicitly/clearly mention that.  \n\n6- The training dataset when using KAMIS to label graphs is similar to training a regression model with inaccurate true values as labels. The reason is KAMIS does not guarantee an optimal solution. For MIS, there are other techniques to generating graphs with guaranteed true MISs (maximum, not maximal) such as the following: Create a graph G with n nodes, make k of them completely connected, and randomly add edges to/from the remaining vertices with degree <= k. Then, the complement graph G' should have at least one independent set of size k and no independent set of greater size. \n\n7- Missing iSCO [1] and the differentiable solver in [2] for comparison. \n\n8- The ER results of DIFUSCO are not the same as were reported in the original paper? I know that DIFUSCO is a diffusion-based method where the sampling procedure starts with a random noise vector drawn from the standard Gaussian. However, a discussion is needed of why lower results are reported here. \n\n9- The novelty is not that significant from the T2T method other than the use of CMs and considering an encoding of size N X 2 instead of N X 1. Using CMs does improve the run-time, and slightly improve the solutions sizes. \n\n10- Generally, the proposed approach and other supervised methods such as DIFUSCO and T2T depend on additional post-processing procedures. This dependence needs to be further explained and investigated. The details for the post processing procedures (such as MCTS and Greedy Decoding) are needed, even if they were also adopted in DIMES and DIFUSCO. For example, if none of these procedures were used, how does this impact the outcomes? \n\n[References]\n\n[1] Revisiting sampling for combinatorial optimization. ICML, 2023.\n\n[2] A differentiable approach to the maximum independent set problem using dataless neural networks. Nueral Networks, 2022.", "limitations": "See Questions.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1- The paper is in general well-written and technically sound.\n\n2- The use of CMs to accelerate the sampling procedure.", "weaknesses": "See Questions.", "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 our writing and technical soundness. Nonetheless, we believe there may exist some misunderstandings, especially regarding the value of the research line of data-driven learning-based solvers. It seems the major concern of the comment is about the application of data-driven machine learning in problem solving, which might cause the model to fit a specific data distribution and limit its generalization to different distributions. To pre-clarify this potential misunderstanding that may affect the rating of our work, please kindly refer to the generalization discussion in the general response. This may also directly respond to the first question about the generalization ability of neural solvers.\n\nIn addition, we notice that the reviewer may focus more on the MIS problem. Here we note that Our paper introduces a foundational framework and a robust model for various CO problems. We conducted experiments on both the edge-selection problem TSP and the node-selection problem MIS, primarily focusing on TSP for a comprehensive evaluation of OptCM, including solving results, generalizability, runtime-drop curves, and hyperparameter studies. For MIS experiments, we mainly focus on showing OptCM's capability of handling different problems, while similar conclusions can be inferred from TSP results. This follows the typical experiment organization of previous works like DIMES, DIFUSCO, and T2T. As per your request, we also supplement generalization results on MIS to further strengthen our paper. Please see the specific comments below.\n\n> **Q1:  In the MIS problem, how does a CM trained on ER700 with p=0.15 generalize when faced with p=0.2? Scalability results on MIS problem to generalize to higher n.** \n\nWe provide supplementary results for generalization results on the MIS problem below. We test the model trained on ER 700-800 with p=0.15 to different p and n. We find that the generalization ability of OptCM is significantly better than that of the previous diffusion-based methods DIFUSCO and T2T regarding both solution quality and speed, e.g., in ER 350-400 Sampling setting OptCM achieves significant performance gain from (23.28\\%, 24m31s) to (11.45\\%, 1m1s).\n\n\n|p|Decoding|Method|Size|Drop|Time|\n|-|-|-|-|-|-|\n|0.2|Greedy|DIFUSCO (T_s=100)|26.25|25.65%|6m31s|\n|||T2T (T_s=50,T_g=30)|27.84|21.13%|7m52s|\n|||OptCM (T_s=1,T_g=1)|28.04|20.58%|32s|\n|||OptCM (T_s=5,T_g=5)|29.52|16.38%|1m57s|\n| |Sampling|DIFUSCO (T_s=100)|27.98|20.73%|27m15s|\n|||T2T (T_s=50,T_g=30)|28.07|20.49%|33m58s|\n|||OptCM (T_s=1,T_g=1)|28.81|18.39%|1m40s|\n|||OptCM (T_s=5,T_g=5)|30.10|14.74%|6m13s|\n\n|n|Decoding|Method|Size|Drop|Time|\n|-|-|-|-|-|-|\n|350-400|Greedy|DIFUSCO (T_s=100)|27.31|28.04%|5m1s|\n|||T2T (T_s=50,T_g=30)|28.54|24.80%|6m59s|\n|||OptCM (T_s=1,T_g=1)|32.56|14.20%|22s|\n| |Sampling|DIFUSCO (T_s=100)|29.33|22.73%|20m12s|\n|||T2T (T_s=50,T_g=30)|29.12|23.28%|24m31s|\n|||OptCM (T_s=1,T_g=1)|33.61|11.45%|1m1s|\n|1400-1600|Greedy|DIFUSCO (T_s=100)|34.39|32.48%|22m7s|\n|||T2T (T_s=50,T_g=30)|OOM|OOM|OOM|\n|||OptCM (T_s=1,T_g=1)|36.95|27.47%|1m39s|\n| |Sampling|DIFUSCO (T_s=100)|35.55|30.21%|1h27m31s|\n|||T2T (T_s=50,T_g=30)|OOM|OOM|OOM|\n|||OptCM (T_s=1,T_g=1)|38.59|24.25%|3m56s|\n\n> **Q2: How does the size of the training dataset impact the outcomes?**\n\nFor in-distribution evaluation, the larger the dataset, the better the learning outcome. This is a clear result of ML mechanisms, as having more data allows the model to better summarize more patterns and strategies. As for generalization, we can use a model pretrained on one dataset and apply it to the test data, which might only require a small amount of data from the new distribution for fine-tuning.\n\n> **Q3: How does the proposed method handle real-world graphs?**\n\nWe can train on data with a similar distribution and then test on a given real-world test set. In fact, we have already conducted tests on real-world TSPLIB data. While the out-of-distribution generalization results may degrade compared to in-distribution performance, our experimental results show that the degradation is not severe. OptCM's generalization ability is also better than other state-of-the-art learning-based solvers.\n\nWe note again that data-driven machine learning methods have their own value and role in various applications, such as optimization problems, including automatic strategy discovery, GPU acceleration, and adaptation to specific data distribution problems. The learning-based solver approach has also received significant attention from the machine learning community, underscoring the importance and acceptance of these methods. On the other hand, dataless methods and traditional solvers have their own advantages, such as better generalization performance and robustness. We will include related work, such as iSCO and MIS_dNN, in our paper for discussion.\n\n\n> **Q4: The training time comparison with heuristics and ILP solvers**\n\nTraditional solvers do not require training, and we will supplement the training time for OptCM in the paper. For intuition, OptCM for TSP-500 requires about 45 hours of training on 4 A100 GPUs. For comparison, POMO for TSP-100 requires about 1 week on a single Titan RTX and Sym-NCO for TSP-100 requires 2 weeks on a single A100 GPU. It should be additionally noted that the training time is offline and does not affect the inference time during solving.\n\n> **Q5: Label generation with KAMIS.**\n\nThank you for your suggestion. It is very beneficial for constructing training data for MIS. On the other hand, we need to point out that since we adopt the generative model to learn the distribution of high-quality solutions, we do not have strict requirements for the optimality of the training data labels.  T2T's Fig. 5 shows that training with worse labels can still yield plausible solutions (better than the supervision quality) during inference by sampling from the generative distribution.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AoMPXAl8H1", "reviewer": "Reviewer_rpwx", "summary": "The paper introduces Optimization Consistency Models (OptCM) as a novel method for solving combinatorial optimization (CO) problems efficiently. Traditional diffusion models, although powerful, are computationally intensive due to their iterative denoising processes. OptCM overcomes this limitation by learning direct mappings from noise levels to optimal solutions, enabling rapid single-step solution generation. The contributions of this paper are three-fold. First, OptCM reduces the computational overhead significantly by enabling fast, single-step solution generation while maintaining high solution quality. Second, This protocol ensures that samples from different generative trajectories converge consistently to the optimal solution. Thrid, Introduced at the test stage, this method enhances solution exploration and quality during inference.", "questions": "How does the computational complexity of OptCM compare with traditional diffusion models and other state-of-the-art neural solvers? What specific optimizations were implemented to achieve the reported speedup in solution generation?\n\nHow does OptCM compare with classical optimization algorithms like simulated annealing or genetic algorithms in terms of both performance and computational resources? \n\nCan OptCM be effectively applied to real-world problems with noisy, incomplete, or dynamically changing data?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "OptCM significantly reduces the computational overhead by enabling fast, single-step solution generation, compared to the multiple steps required by traditional diffusion models. This efficiency allows for rapid inference, making it practical for real-time and large-scale applications.\n\nDespite the reduced computational steps, OptCM maintains high solution quality, often outperforming state-of-the-art methods that require more extensive processing. The optimization consistency training ensures that the generated solutions are close to the optimal solution.\n\nThe optimization consistency training protocol is a novel approach that minimizes the differences among samples from varying generative trajectories, ensuring robust and consistent solution generation. This method enhances the model's ability to generalize across different problem instances.\n\nThe introduction of a consistency-based gradient search during the test stage allows for further exploration and refinement of the solution space, improving the final solution quality. This approach bridges the gap between training and inference, making the model more adaptable to new instances.", "weaknesses": "Overall, the paper's strengths lie in its innovative approach to reducing computational complexity while maintaining high solution quality, its robust and versatile model design, and its impressive performance on benchmark tasks. However, there are some weaknesses in this paper. Some weaknesses listed below might be found to be too general and don't require the authors to address them now.\n\nThe advanced techniques used in OptCM, such as optimization consistency training and gradient-based search, may be challenging to implement and require a deep understanding of the underlying principles.\n\nThe model's performance is closely tied to the quality and diversity of the problem instances used during training. If the training set does not adequately represent the test instances, the model's effectiveness might be reduced.\n\nWhile the paper demonstrates the superiority of OptCM over state-of-the-art neural solvers, it could provide a more detailed comparison with traditional, non-neural methods in terms of both performance and computational efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments and for acknowledging novelty, model design, and empirical performance. Below we respond to the specific comments.\n\n> **Q1: How does the computational complexity of OptCM compare with traditional diffusion models and other state-of-the-art neural solvers?**\n\nSince the consistency model requires two inference predictions with different noise levels during training, it requires twice the training cost of the original diffusion model. However, this overhead on training is offline, and the consistency model is much more efficient than diffusion at inference time. As shown in Table 1, 2, and 4, OptCM can achieve 82.8x speedup on TSP-50/100, 16.8x speedup on TSP-500/1000, and 26.3x speedup on MIS compared to previous SOTA diffusion counterparts even with solution quality advantage.\n\n\n> **Q2: What specific optimizations were implemented to achieve the reported speedup in solution generation?**\n\nCompared to the time-consuming iterative sampling process requiring denoising across multiple noise levels, the speedup of OptCM comes from the method design that learns direct mappings from different noise levels to the optimal solution for a given instance. This facilitates high-quality generation with minimal shots. To learn such direct mappings, we propose an optimization consistency training protocol, which, for a given instance, minimizes the difference among samples originating from varying generative trajectories and time steps relative to the optimal solution. Please refer to Sec. 4 for algorithm details. We also supplement the specific algorithm in the PDF attachment of the general response.\n\nWe also supplement the specific design choices of our OptCM, and the listed hyperparameters correspond to those used in the algorithm presented in the paper. We will supplement these details to the paper to enhance its comprehensiveness.\n\n| Training                  | Design Choice                             |\n| ------------------------- | ----------------------------------------- |\n| Consistency Loss Function | $d(x,y)=$Binary_Cross_Entropy$(x,y)$ |\n| Scaling Factor            | $\\alpha=0.5$                              |\n| Weighting Function        | $\\lambda (t)=1$                           |\n| Discretization Curriculum | $t\\sim \\{1, 2,...,T\\}$, randomly sampling |\n| Initial Learning Rate     | $\\eta=0.0002$                             |\n| Learning Rate Schedule    | Cosine decay, decay rate $\\omega=0.0001$  |\n\n\n| Test                        | Design Choice                                                |\n| --------------------------- | ------------------------------------------------------------ |\n| Sampling Step Schedule      | $t_1=T(1-\\sin(N\\cdot i\\pi/2))$, $t_2=T(1-\\sin(N\\cdot (i+1)\\pi/2))$ |\n| Guided Weighting Parameters | $\\lambda_1=50$, $\\lambda_2=50$ on TSP  <br> $\\lambda_1=2$, $\\lambda_2=2$ on MIS |\n| Rewrite Ratio               | $\\epsilon=0.2$ on TSP and ER-[700-800] <br> $\\epsilon=0.3$ on RB-[200-300] |\n\n\n\n> **Q3: How does OptCM compare with classical optimization algorithms like simulated annealing or genetic algorithms in terms of both performance and computational resources?**\n\nThanks for noting classical algorithms, which are indeed important for the comprehensive evaluation. Indeed we have already included traditional algorithms in our comparison: 1) For TSP, we compare SOTA traditional exact solvers Concorde and Gurobi, as well as Heuristic solvers LKH-3 and Fasthest Insertion. 2) For MIS, the compared SOTA traditional solvers include the exact solver Gurobi and the heuristic solver KaMIS. \n\nThe mentioned algorithms like simulated annealing or genetic algorithms are indeed not very competitive in solving hard problems. We supplement the experimental results of SA and GA below; please refer to Table 1 and 2 for the corresponded performance of other SOTA baselines, where competitive results fall within the drop of 1%.\n\n\n\n| Setting   | Length  | Drop    | Time  |\n| ---------- | ------ | -------- | ----- |\n| SA_TSP100  | 18.40  | 138.43%  | 1h58m |\n| SA_TSP500  | 108.87 | 558.12%  | 2m5m  |\n| SA_TSP1000 | 248.99 | 975.28%  | 2h22m |\n| GA_TSP100  | 39.14  | 407.41%  | 2h3m  |\n| GA_TSP500  | 240.70 | 1355.94% | 2h15m |\n| GA_TSP1000 | 497.18 | 2047.16% | 2h32m |\n\n\n> **Q4: Can OptCM be effectively applied to real-world problems with noisy, incomplete, or dynamically changing data?**\n\nWe have provided the performance of OptCM on real-world datasets such as TSPLIB, and the relevant results are shown in Tables 5, 6, and Appendix A. The experimental results show that OptCM can generalize to the real-world data, which outperforms all the previous SOTA baselines. While for specific environments such as scenarios with noisy, incomplete, and dynamically changing data, we have not made customized designs to deal with them at the moment. Currently, OptCM is a fundamental model that focuses purely on the performance of the solving task on relatively clean data, but we also acknowledge the importance of studying the application to various noisy, incomplete, and dynamically changing scenarios, and we will take this as the future direction of our subsequent research. Thank you for your suggestions.\n\n\n---\n\nWe hope this response could help address your concerns. We believe that our work can have an important impact on the field of ML4CO as a possible new backbone model to drive the effectiveness of existing methods further. Thank you again for your firm support and recognition of our paper. If our response has satisfactorily addressed your concerns, we would be sincerely grateful if you could consider a higher score, as it would greatly support our efforts. Thank you once again for your consideration.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely appreciate the reviewers’ time, valuable feedback, and constructive suggestions. Overall, the reviewers deem our work as "well-motivated" (3pWn), "well-written" (3pWn, rPB6), and "technically sound" (rPB6), acknowledging our "novel" "robust" "versatile" methodology and model design (3pWn, rpwx), with "convincing" "significantly superior" "extensive" "impressive" empirical evaluations (3pWn, P6jy, rpwx). The primary concerns revolve around the novelty and inherent limitations in generalization associated with the data-driven learning paradigm, where fitting a specific data distribution may hinder generalization to different distributions. To preempt the potential misunderstandings that might impact the evaluation of our work, we first restate our contributions and address the generalization concerns.


**(1) Novelty Claim.**

OptCM is inspired by some excellent previous works, which is one of the key supports for its ability to achieve such strong experimental results. However, we must note that the technical contributions of OptCM are highly non-trivial, as supported by reviewers 3pWn and rpwx. 

1. Compared to DIFUSCO and T2T's diffusion models, OptCM's model design, including the model inference process and the training objective function, is very different from the previous diffusion model. Indeed, consistency models are recognized as a new independent class of generative models in generative tasks, and in this paper, we further introduce the optimization consistency condition and establish optimization consistency models (OptCM) to tailor the model for optimization scenarios. This stands the model to be a new highly effective and efficient backbone for future development of learning-based solvers. 
2. In terms of T2T's two-stage framework, we merely refer its high-level concept to introduce instance-tailored solving during testing, thus bridging the gap between training and problem-solving. In fact, due to the difference between consistency mapping and diffusion inference, OptCM's framework and implementation are fundamentally independent. The testing-phase search is an additional effort building upon the original inference model. With the consistency mapping-based model, the search procedure is an innovative method that is completely different from that of T2T.
3. For experimental results, OptCM demonstrates exceptional performance in both solution efficiency and quality. Notably, our improvements over previous SOTA diffusion-based methods are of a significant magnitude, e.g., OptCM variants with more sampling and gradient search steps can achieve 82.1% performance gain with 14.7x speedup compared to previous diffusion-based counterparts on TSP-50/100. Additionally, this is the first time end-to-end solvers have surpassed LKH on the runtime-gap curve for the TSP problem within a given timeframe. We believe that such strong empirical results substantiate the claim that OptCM represents more than just incremental progress within the existing diffusion framework.


**(2) Generalization Discussion.**

The major concern of Reviewer rPB6 is about the application of data-driven machine learning in problem solving, which might cause the model to fit a specific data distribution and limit its generalization to different distributions. Here we provide a targeted discussion.

Firstly we must note that Generalization challenges are common across data-driven machine learning methods, not just ours. Any machine learning method that automatically learns solving strategies and data structures from training data (whether supervised, reinforcement learning, or unsupervised) faces generalization challenges. Nonetheless, Machine Learning for Combinatorial Optimization (ML4CO) has gained significant traction, evidenced by numerous publications at leading conferences such as NeurIPS, ICML, and ICLR—each annually featuring about 20 papers on this subject. Please refer to [1] for a summarized list of ML4CO papers, including 34 CO problems and problems like TSP has more than 50 papers recorded. Around 20 survey papers, including Yoshua Bengio's first-authored paper [2], provide extensive summaries and highlight ML4CO's critical research value. Therefore, considering the demonstrated success in the ML4CO field, it would be inappropriate to evaluate a method primarily on its machine learning attributes.

On the other hand, learning from the given data is indeed one of the advantages of learning-based solvers. Data in real-world applications often exhibits a certain problem structure within the implicit distribution. In many cases, we need machine learning methods to uncover patterns within the data and solve problems associated with a specific distribution. It is also supported by Bengio in [2] that "ML4CO focuses on CO algorithms that automatically perform learning on a chosen implicit distribution of problems", and "ML can help improve an algorithm on a distribution of problem instances in two ways: 1) replace some heavy computations by a fast approximation; 2) explore the decision space and learn out of the experience the best-performing behavior (policy)."

Regarding the empirical results, we have already performed many experiments on the generalization results, including generalizing to different scales of TSP (from 50 to 1000)  as shown in Sec. 6.1 and Table 3, and generalizing to different distributions like real-world TSP instances from TSPLIB as shown in Appendix A and Table 1, 2. These results show that OptCM maintains good generalization results and outperforms previous SOTA diffusion-based baselines. We also supplement generalization results on MIS to strengthen our paper in the specific individual comments. On the other hand, generalization is itself an independently important research domain, which can typically be orthogonal to our method.

[1] github.com/Thinklab-SJTU/awesome-ml4co

[2] Machine Learning for Combinatorial Optimization: a Methodological Tour d'horizon. EJOR 2021.

Meta-review: This was a borderline paper. 
The authors introduce a new method for solving combinatorial optimization problems like TSP and Max Independent Set. Previous recent works (DIFUSCO and T2T) introduced diffusion solvers for combinatorial optimization and this paper introduces Consistency to accelerate the samplers for these discrete domains. This is a very reasonable thing to do, and some reviewers considered it somewhat incremental. Still, the scientific evaluation is detailed and the performance benefits are valuable. 
Also, the reviewers raised several questions ranging from training details to additional comparisons and additional combinatorial optimization problems. 
There was an extensive discussion and the authors provided numerous additional details in the rebuttals. The Reviewers were not fully excited, but overall the paper merits acceptance esp. given the additional clarifications that the authors provided.
Decision: Accept (poster)