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_cc_2024_Conference
Published: 2024-05-14 15:54:43

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.

Main paper: 
 introduction: 
 Combinatorial Optimization (CO) problems, which involve optimizing discrete variables under given objectives, are essential in computer science and operational research. Due to the inherent computational difficulty, e.g. NP-hardness, solving efficiency poses significant challenges and requires exhaustive human efforts to design solving heuristics. Recent progress in this domain has shown promise in automatically learning heuristics with Machine Learning (ML) in a data-driven manner [1, 2, 3, 4, 5, 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 or new instance distributions where experts are not there.Learning-based solvers for CO typically employ neural networks to generate neural predictions for solution construction or search guidance, aiming to minimize either the objective score [2, 4, 5, 6, 9] or the deviation from reference solutions [10, 3, 11, 12, 13] . 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 instance. Thus, methods [14, 15, 6, 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-conditioned quality solution distributions [7, 8] with robust expressive power to achieve state-of-the-art performance, which also provides more informative support for further exploitation like gradient search in the solving stage, which was previously proposed as the diffusion-based training-to-testing (T2T) framework [8] . However, a major drawback of the diffusion backbone lies in its costly inference process, which necessitates tens or 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, 8] can exhibit superiority in inference speed compared to certain traditional methods and prior learning-based 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 to speed up the diffusion-based T2T framework, dubbed as Fast T2T, specifically for optimization problem-solving. We follow [8] 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. 1 , Fast T2T builds upon the methodology foundation of the discrete diffusion models [17, 18, 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 a 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 t to step t -1, the consistency modeling enables generating solutions (x 0 in Fig. 1 ) from random noise vectors (x T in Fig. 1 ) by a 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 0 to generate a less noisy point x t and solution reconstruction to obtain a new x 0 . Additionally, we design a novel objective gradient-based search on top of the learned consistency mapping to further explore the learned solution distribution for every test instance. We introduce instance-specific guidance from the objective to the learned solution prior p θ (x|G) and obtain the posterior p θ (x|y * , 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-decision and node-decision types respectively, i.e., Traveling Salesman Problem (TSP) and Maximum Independent Set (MIS). We show that Fast T2T, even with a single-step initial solution generation and a single-step gradient search, can mostly outperform the SOTA diffusion-based 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 a highly effective and efficient backbone for learning-based solvers. 2) To complement the learned prior and bridge the disparity between data-driven training and the requirement of problem-solving, we introduce a novel gradient search with objective guidance based on consistency mappings to conduct a 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. 
related work: 
 Machine Learning for Combinatorial Optimization. Current learning-based CO solvers can be categorized into constructive approaches and improvement-based approaches. Constructive approaches refer to autoregressive methods [20, 2, 4, 21, 5] that directly construct solutions by sequentially determining decision variables until a complete solution is constructed, and non-autoregressive methods [3, 12, 22, 6, 7, 23] that predict soft-constrained solutions in one shot and then perform postprocessing to achieve feasibility. Improvement-based solvers [24, 25, 26, 27, 28] learn to iteratively refine a 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 task for learning solution distributions conditioned on given instances [21, 29, 7, 30, 31, 8] . Drawing from diffusion models, DIFUSCO [7] has attained SOTA performance in solving TSP and MIS. Nonetheless, it does not incorporate any instance-specific search paradigms to fully capitalize on the estimated solution distribution. Addressing this limitation, the T2T framework [8] further introduces an objective-guided 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 a 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, 32, 33, 34, 35, 36, 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/categorial noises [17, 18, 19] . On top of the foundation of diffusion models, consistency models [16] define the self-consistency 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 are employed on the discrete multinomial data for the benefit of CO. 
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) ∈ 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 ∈ {0, 1} N ×2 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 2 and x i,j indicates whether E i,j is included in x. For node-decision problems, N = n and x i indicates whether V i is included in x. The feasible set Ω 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 l(•; G) : {0, 1} N ×2 → R ≥0 :EQUATIONTSP is defined on an undirected complete graph G = (V, E), where V represents n cities and each edge E i,j is assigned a non-negative weight w i,j representing the distance between cities i 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 ⊆ V such that no two vertices in S are adjacent in G. MIS entails finding an independent set of maximum cardinality in G.4 Training-Stage Optimization Consistency Modeling 
solution encoding and noising process: 
 Using the notations in Sec. 3, we represent the solutions of CO problems as x ∈ {0, 1} N ×2 with x ∈ Ω. The distribution of x is represented by N Bernoulli distributions indicating whether each entry should be selected, i.e., p(x) ∈ [0, 1] N ×2 . The objective of utilizing generative modeling for problemsolving is to capture the distribution of high-quality solutions conditioned on a given instance G, denoted as p θ (x|G). The neural models try to establish transition trajectories from random uniform noise to high-quality soft-constrained solutions, i.e., x ∈ {0, 1} N ×2 . These soft-constrained solutions are directly sampled from the estimated Bernoulli distributions where feasibility constraints can be broadly captured through learning and eventually hard-guaranteed by post-processing.To establish the transition trajectories of data, we follow the discrete diffusion modeling [7, 8] to define the noising process, which takes the initial solution x 0 sampled from the distribution q(x 0 |G) and progressively introduces noise to generate a sequence of latent variablesx 1:T = x 1 , x 2 , • • • , x T .Specifically, the noising process is formulated as q(x 1:T |x 0 ) = T t=1 q(x t |x t-1 ), which is achieved by multiplying x t ∈ {0, 1} N ×2 at step t with a forward transition probability matrixQ t ∈ [0, 1] 2×2which indicates the transforming probability of decision state. We setQ t = β t 1 -β t 1 -β t β t [18],where β t ∈ [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 t-step marginal are formulated as:EQUATIONwhere Cat(x; p) is a categorical distribution over N one-hot variables andQ t = Q 1 Q 2 • • • Q t .Unlike the diffusion models modeling p θ (x t-1 |x t , G), we aim to directly map random noise to data by p θ (x 0 |x t , G) in an optimization context. In continuous-time diffusion models defined on (ϵ, T ] [38], consistency models [16] defines the self-consistency property as points on the same trajectory map to the same initial point, and optimize the learned consistency function f θ (•, •) to satisfy the requirement by: 1) boundary condition: f θ (x ϵ , ϵ) = x ϵ ; 2) self-consistency property: f θ outputs consistent estimation for arbitrary pairs of (x t , t) that belong to the same trajectory, i.e.,f θ (x t , t) = f θ (x t ′ , t ′ ), ∀ t, t ′ ∈ [ϵ, T ].The joint effect of these two constraints serves as the necessary and sufficient condition to achieve a reliable data prediction from noise step T to data, i.e., f θ (x T , T ) → x ϵ . In the optimization scenario of mapping instance G to 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 [18, 7, 8] , we use the consistency function to Optimization consistency enforces that all trajectories conditioned on G consistently map to the same initial point, i.e., the optimal solution of G.estimate the optimal solution distribution as a point estimate δ(x -x * ) where δ(•) represents Dirac delta. Below defines optimization consistency for the conditional context of problem-solving. Definition 4.1 (Optimization Consistency). Given a solution trajectory {x t } t∈[0,T ] , we define the consistency function as f : (x t , t, G) → δ(x -x * ), which maintains the optimization consistency property: conditioned on instance G, all points along any trajectory map to its optimal solution, i.e.,f θ (x i t , t, G) = f θ (x j t ′ , t ′ , G) = δ(x -x * )for distinct trajectories i and j at distinct steps t and t ′ . As illustrated in Fig. 2 , the goal of the consistency model f θ 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 f : G → x * , given its nature as a conditional generation 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.e., L CM (θ) = E d f θ (x, t, G) , f θ (x ′ , t ′ , G) , we introduce x * to optimize the upper bound of L CM through triangle inequality of distance measures asEQUATIONHere d(•, •) 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, we can directly utilize the neural network θ to estimate the consistency function f θ (•, •, •). 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 a single trajectory. Definition 4.2. The optimization consistency loss for conditional problem-solving is defined as:EQUATIONwhere the expectation is taken with respect toG ∼ p G , n ∼ U[1, N t -1], x i tn ∼ Cat(x tn ; p = x * Q tn ), and x j tn+1 ∼ Cat(x tn+1 ; p = x * Q tn+1 ). Here U[1, N t -1] denotes the uniform distribution over {1, 2, • • • , N -1}, λ(•) ∈ R + is a positive weighting function.Since the model outputs N Bernoulli distributions as the distribution of x 0 , we adopt the binary cross entropy to measure the distance between the estimation p θ (x) and δ(x -x * ). We set λ(t n ) ≡ 1 and discover a decent empirical performance. x i tn and x j tn+1 are identically and independently sampled from different noising trajectories, in comparison tox i tn ∼ Cat(x tn ; p = x * Q tn ), x i tn+1 ∼ Cat(x tn+1 ; p = x tn Q tn+1 • • • Q tn+1 ) where x itn and x i tn+1 are from the same trajectory. Since very close t n and t n+1 would make Eq. 4.2 very easy to learn, we reschedule the time horizon into [34] . This training procedure enforces the model to learn 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 to the Dirac delta on x * , the generative modeling process with a 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 θ is embodied as an anisotropic graph neural network with edge gating mechanisms [3] , and instance G serves as a 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 t 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 t 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 p θ (x 0 |x t , G) ∈ [0, 1] N ×2 featuring N Bernoulli distributions for N entries in x 0 via a linear layer followed by a Softmax layer.N t -1 sub-intervals t 1 = 1 < t 2 < • • • < t Nt = T through the cosine denoising schedular such that t i = ⌊cos 1-π•ci 2 • T ⌋ following DDIMQuestion: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: The experimental details are in Sec. 6 and Append. B, C. We will make our source code publicly available upon acceptance. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
testing-stage problem solving via consistency-based gradient search: 
 The solving involves obtaining the initial solution from the raw consistency sampling process and a consistency-based gradient search process with objective feedback for iterative solution improvement.Input: Consistency model f θ (•, •, •), graph problem instance G, sequence of time points τ 1 > τ 2 > • • • > τ Nτ -1 Sample x T from uniform distribution U p θ (x 0 |G) ← f θ (x T , T, G) x 0 ∼ p θ (x 0 |G) for n = 1 to N τ -1 do Sample x τn ∼ Cat(x τn ; p = x 0 Q τn ) p θ (x 0 |G) ← f θ (x τn , τ n , G) x 0 ∼ p θ (x 0 |G) end for Output: Solution x 0With a well-trained f θ (•, •, •), we generate solutions for a given instance G by sampling x T from the uniform distribution and then evaluate it for x 0 ∼ p θ (x 0 ) = f θ (x T , T, G). This process requires only one forward pass through the consistency model, resulting in sampling in a single step. Solution sampling with multiple steps of inferences can also be accomplished via alternating denoising and noise injection, allowing trading runtime for improved solving quality. Given a sequence of time pointsτ 1 > τ 2 > • • • > τ Nτ -1, in time step τ n , the multistep sampling process adds noise to the x 0 obtained from the last step τ n-1 by x τn ∼ Cat(x τn ; p = xQ τn ), then denoise to find the new solution by x 0 ∼ f θ (x τn , τ n , G), as shown in Algorithm. 1.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-step 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 p θ (x|G), this section aims to introduce a constraint c(x, y * |G) on x to this prior for inference, where y * represents the optimal objective score given the instance G. That is, we want to find an approximation to the posterior distribution p θ (x|y * , G) ∝ p θ (x|G)c(x, y * |G) to guide the sampling process to the optimal x * .Here we follow [8] to determine c(x, y * |G) by utilizing energy-based modeling [41] with the energy function E(y, x, G) = |y -l(x; G)|, which quantifies the compatibility between y and (x, G), and it 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 to maintain the highest probability density and the probability density is positively correlated with the matching degree. Then we employ the Gibbs distribution to characterize the probability distribution over a collection of arbitrary energies:EQUATIONFollowing [42] , we introduce an approximate variational posterior q(x|G) and the free energyEQUATIONis minimized when KL(q(x|G)||p θ (x|y * , G)) is minimized. Here h = x 1 , • • • , x T represent the latent variables. Through the diffusion process, we can obtain q(h|x) = T t=1 q(x t |x t-1 ). We apply an approximation to the posterior over x = x 0 as a point estimate q(x|G) = δ(x -η). F 1 aligns with the objective of the consistency and diffusion models and F 2 can be transformed using Eq. 5:EQUATIONInitializing η from Sec. 5.1, we aim to update η to reach conditional solution distribution p θ (x|y * , G) through exponential gradient decent on the latent continuous probabilityp x = p(x αT ) = ηQ αT ∈ [0, 1] N ×2 at each iteration minimizing F 1 and F 2 .Here p x parameterizes N Bernoulli distributions and α serves as a hyperparameter to control the noise degree. We view p x as the expectation of x αT over p x , i.e., E px (x αT ) = p x , since p x is a multivariate Bernoulli. To obtain reliable gradients on p x , we estimate the expected distribution of x 0 by f θ (p x , αT, G). Note F 1 is exactly the (implicit) objective of the diffusion and consistency models, i.e., the variational upper bound of the negative log-likelihood with the targeted data η, which we optimize by minimizing the consistency over the re-predicted solutions d f θ (p x , αT, G), δ(x -η) . While F 2 can be optimized by minimizing l f θ (p x , αT, G); G + Const(p x ), where the objectives are defined following [8] as l MIS (x; G) ≜ -1≤i≤N x i + β (i,j)∈E x i x j and l TSP = x ⊙ D where D ∈ R n×n + denotes the distance matrix.In each iteration, with current η, we obtain p x = ηQ αT , p θ (η) = f θ (p x , αT, G) and update p x byEQUATIONwhere λ 1 , λ 2 are weighting hyperparameters. Then we sample x αT ∼ p x and reconstruct a new distribution estimate of η by p ′ θ (η) = f θ (x αT , αT, G). To guarantee the feasibility, we utilize the logits of p θ (η) and p ′ θ (η) to produce the heatmaps where each element denotes each edge/node's confidence to be selected, and then adopt post-processing2 to obtain two feasible solutions. This iteration concludes by outputting the lower-cost solution as η.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [No] Justification: The source code will be made publicly available upon acceptance. 
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-based models, we adopt T s and T g to represent the number of inference steps in initial solution sampling and the number of gradient search steps, respectively. For diffusion-based baselines including DIFUSCO [7] and T2T [8] , we adopt T s =50 and involve 3 iterations with 5 guided denoising steps per iteration for T2T's gradient Training and testing instances are generated via uniformly sampling N nodes from the unit square [0, 1] 2 , which is a standard procedure as adopted in [2, 21, 3, 48, 6, 7, 8] . We experiment on various problem scales including TSP-50, 100, 500, and 1000.Metrics. Following [2, 3, 6, 7, 8], we adopt three evaluation metrics: 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 to solve the problems.Results for TSP-50/100. Given the recent success of learning-based solvers in achieving near-optimal performance on small-scale problems, we follow [8] to assess methods within the naive greedy decoding setting, aiming for a more discernable evaluation. The comparison includes state-of-the-art learning-based methods with greedy decoding and traditional solvers. Hyperparameter α is set as 0.2.The sampling steps and gradient search steps are explicitly marked. Results for Generalization. Based on the problem set {TSP-50, TSP-100, TSP-500, TSP-1000}, we train the model on a specific problem scale and then evaluate it on all problem scales. Table 3 presents the generalization results of Fast T2T compared with diffusion-based counterparts with greedy decoding. The results show the satisfying cross-domain generalization ability of Fast T2T, e.g., the model trained on TSP-1000 achieves less than a 0.6% optimality gap on all other problem scales.Soving Time vs. Optimality Drop on TSP-100/1000. Fig. 3 and Fig. 4 illustrate 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 in the early solving stage while also performing comparably in the later stage. This suggests that Fast T2T can serve as an effective rapid solver for approximate solutions outperforming LKH3, which may find widespread applications requiring prompt responses. Other neural solver baselines fall far outside the comparable range; please refer to Fig. 6 for an intuitive illustration.Ablation and Hyperparameter Study. Fig. 5 illustrates the performance variation when altering the noise hyperparameter α, and we discover a 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 [7] and T2T [8] for direct comparison, in order to see whether diffusionbased 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 a significant performance overwhelm of Fast T2T to diffusion-based counterparts.Datasets. Two datasets are tested for the MIS problem following [52, 54, 53, 6, 7] , 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 a 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.Metrics. Following previous works [2, 3, 6, 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.e. 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 (×4), 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.  
conclusion: 
 We introduce optimization consistency on top of the diffusion-based training-to-testing solving 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-art neural solvers. Furthermore, our approach demonstrates superiority over LKH3 in the early stages of solving. 3: repeatQuestion: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: we follow the setting of previous works to report the average solution quality over 128 or 1,280 instances in Sec. 6.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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. E.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The original papers that introduce models and datasets used in the paper are cited in Sec. 6.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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 new assets. Our source code will be released upon the acceptance of the paper with comprehensive documents. As parts of the documents, we formally describe our proposed model and the corresponding details in Sec. 4 and 5. The training details are presented in Appendix. C.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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 an equivalent approval/review based on 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 crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: 4: Sample x * ∼ D, t 1 ∼ [1, T ], t 2 ← ⌈αt 1 ⌉ 5: Sample z 1 ∼ x * Qt1 , z 2 ∼ x * Qt2 6: L(θ) ← λ(t 1 ) (d (f θ (z 1 , t 1 ) , δ(z 1 -x * ))) + d (f θ (z 2 , t 2 ) , δ(z 1 -x * )) 7:θ ← θ -η∇ θ L(θ)8:9: until convergenceWe supplement the specific design choices of the optimization consistency models, and the listed hyperparameters correspond to those used in the algorithm presented in sections 4 and 5.Consistency Loss Function d(x, y) = Binary_Cross_Entropy(x, y) Scaling Factor α = 0. T2T [8] , and baselines listed in [56] 's Table 3 . The hyperparameter settings of the compared baselines are: DIFUSCO: T s =50; T2T: T s =50 and T g =30; Fast T2T (w/o GS): T s =10; Fast T2T (w/ GS): T s =10 and T g =10. The diffusion-based methods are compared in the same settings with greedy decoding and Two-Opt post-processing. For each instance, we 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, we normalize the coordinates to [0,1]. 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 a positive results of Fast T2T outperforming previous baselines. Fast T2T (T =20, T =20) Drop (%) We 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 (the probability that each simple edge exists) and n (graph size). We find that the generalization ability of Fast T2T 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 Fast T2T achieves significant performance gain from (23.28%, 24m31s) to (11.45%, 1m1s) . Results are presented in Tables 8 and 9 . 13.03 28.33% 45m2s Fast T2T (T s = 1, T g = 1) 13.31 26.80% 2m12s Fast T2T (T s = 5, T g = 5) 13.56 25.43% 8m58s 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%, 30m13s) to (9.10%, 4m20s).C.1 Computational Resources.Test evaluations on TSP-50/100 and MIS are performed on a single GPU of NVIDIA RTX 4090, and evaluations on TSP-500/1000 are performed on a single GPU of NVIDIA Telsla A100.For large-scale TSP problems, we follow [7, 8] to employ sparse graphs, as sparsified by constraining each node to connect to only its k nearest neighbors, determined by Euclidean distances. For TSP-500, 31.77 23.24% 30m13s Fast T2T (T s = 1, T g = 1) 36.84 10.90% 57s Fast T2T (T s = 5, T g = 5) 37.58 9.10% 4m20swe set k = 50, and for TSP-1000, k = 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] .We outline the offline training resource requirements of the Fast T2T framework in Table 11 , with computations conducted on A100 GPUs. For contextual comparison, AM [2] necessitates 128M instances generated on-the-fly to train TSP-100, consuming 45.8 hours on 2 1080Ti GPUs. POMO [4] 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 a single A100 for training. Additionally, Sym-NCO [5] built upon AM [2] necessitates three days on 4 A100 GPUs. Compared with DIFUSCO [7] , Fast T2T necessitates approximately double training time and GPU memory under the same settings, because our consistency training method requires forward twice for each training instance, leading to more time and memory consumption. 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 α associated with each benchmark is listed in Table . 12. TSP-50/100: In 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] , Transformer [47] , POMO [4] , Sym-NCO [5] , Image Diffusion [42] , DIFUSCO [7] , and T2T [8] . Our post-processing involves greedy sampling and 2OPT refinement. To ensure equitable comparisons in terms of computational effort, we 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] , 2 heuristic solvers, LKH-3 [45] and Farthest Insertion, and 6 learning-based methods, including EAN [50] , AM [2] , GCN [3] , POMO+EAS [15] , DIMES [6] , and DIFUSCO [7] . These learning-based methods can be further categorized into supervised learning (SL) and reinforcement learning (RL). 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, we 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.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 one exact solver, Gurobi [49] , one heuristic solver, KaMIS [51] , and 5 learning-based frameworks: Intel [52] , DGL [52] , LwD [54] , DIMES [6] , and DIFUSCO [7] . Post-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 at 50 and 30, respectively.Given node vector x ∈ R N ×2 , weighted edge vector e ∈ R E , denoising timestep t ∈ {τ 1 , . . . , τ M }, where N denotes the number of nodes in the graph, and E denotes the number of edges, we compute the sinusoidal features of each input element respectively:EQUATIONxi,j = concat sin EQUATIONwhere d is the embedding dimension, T is a large number (usually selected as 10000), concat(•) denotes concatenation.Next, we compute the input features of the graph convolution layer:EQUATIONEQUATIONEQUATIONwhere t 0 ∈ R dt , d t is the time feature embedding dimension. Specifically, for TSP, the embedding input edge vector e is a weighted adjacency matrix, which represents the distance between different nodes, and e 0 is computed as above. For MIS, we initialize e 0 to a zero matrix 0 E×d .Following [3] , the cross-layer convolution operation is formulated as:EQUATIONEQUATIONEQUATIONwhere x l i and e l ij denote the node feature vector and edge feature vector at layer l, W 1 , • • • , W 5 ∈ R h×h denote the model weights, η l ij denotes the dense attention map. The convolution operation integrates the edge feature to accommodate the significance of edges in routing problems.For TSP, we aggregate the timestep feature with the edge convolutional feature and reformulate the update for edge features as follows:EQUATIONFor MIS, we aggregate the timestep feature with the node convolutional feature and reformulate the update for node features as follows:EQUATIONThe prediction of the edge heatmap in TSP and node heatmap in MIS is as follows:e i,j = Softmax(norm(ReLU(W e e L i,j )))EQUATIONEQUATIONwhere L is the number of GCN layers and norm is layer normalization.For both TSP and MIS tasks, we construct a 12-layer GCN derived above. We set the node, edge, and timestep embedding dimension d = 256, 128 for TSP and MIS tasks, respectively.As the scale increases, our method'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 a weakening of the speed improvement in 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 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.Our work provides a more 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.Answer: [Yes] Justification: The theoretical derivation of this paper has been given in Sec. 5, and there are no additional theorems needed to 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material.We follow previous works[6,7,8] to perform greedy decoding by sequentially inserting edges or nodes with the highest confidence if there are no conflicts. For TSP, the 2Opt heuristic[43] is optionally applied. 


Decision: 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.

Reviews: review: paper_summary: paper_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. 


[1] Z. Sun and Y. Yang, “DIFUSCO: Graph-based diffusion solvers for combinatorial optimization, in Thirty-seventh Conference on Neural Information Processing Systems, 2023. 

[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.

[3]  Y. Song, P. Dhariwal, M. Chen, and I. Sutskever, “Consistency models,” arXiv preprint arXiv:2303.01469, 2023
strength_weakness: strength_weakness: 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).

2. 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? 

 I'm willing to re-evaluate my score if the authors can answer these two points.
questions: questions: See weakness.
limitations: limitations: Consistency training introduced additional training overhead; I think the authors did not discuss this in Appendix D.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. This work is mainly incremental, based on previous works DIFUSCO [1] and T2T [2].
2. Larger-size TSPs, such as those with 100000 nodes, should be tested against state-of-the-art learning-based methods [3].
3. 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.

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

[2] T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization, NeurIPS, 2023.

[3] GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time, AAAI, 2024.
questions: questions: See weaknesses.
limitations: limitations: The authors have discussed the limitations.
paper_summary: paper_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).
strength_weakness: strength_weakness: See Questions.
questions: 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. 

2- How does the size of the training dataset impact the outcomes? 

3- 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. 

4- Scalability results are missing for dense and sparse graphs if the models do generalize to higher n and same density. 

5- 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.  

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

7- Missing iSCO [1] and the differentiable solver in [2] for comparison. 

8- 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. 

9- 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. 

10- 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? 

[References]

[1] Revisiting sampling for combinatorial optimization. ICML, 2023.

[2] A differentiable approach to the maximum independent set problem using dataless neural networks. Nueral Networks, 2022.
limitations: limitations: See Questions.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

The 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.

The 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.

While 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.
questions: 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?

How does OptCM compare with classical optimization algorithms like simulated annealing or genetic algorithms in terms of both performance and computational resources? 

Can OptCM be effectively applied to real-world problems with noisy, incomplete, or dynamically changing data?
limitations: limitations: Yes

Comments: title: Gentle Reminder for Possible Re-evaluation
Kind Reminder
Acknowledgement of authors' response
Response to Authors - Final Remarks
Official Comment by Authors (Cont.)
Official Comment by Authors (Cont.)
Official Comment by Authors
Response to Authors
Thanks for the Prompt Reply
Rebuttal by Authors (Cont.)
comment: Thanks for your acknowledgment. We appreciate your time and effort in reviewing our paper and are grateful for your feedback throughout this process. We will incorporate all supplementary results and explanations into the final version of the paper and will continue to refine our work and add additional results based on your valuable feedback.
Dear Reviewer 3pWn,

Thank you for your quick reply and for clarifying your position regarding the evaluation of our submission. We apologize if our previous communications appeared to overstep; it was certainly not our intention to dilute the review process but rather to ensure all concerns were thoroughly addressed.

We respect your decision to maintain the current score and appreciate the time and consideration you have given to our work. Your insights have been invaluable to us, and we will take them into account as we continue to refine our work.

Thank you once again for your contributions to the review process.

Best Regards,

The Authors
Dear authors,

I respectfully request you to stop diluting the review section of the submission by constantly posting comments pressing me to increase the evaluation. 

I think my previous comment has clearly stated that I will keep my current score as final, there is no need to send several messages. The main reason for this decision is I think the score reflects well the my view of the work, and as well as after taking into accounts all other reviews. 

Best regards,

Reviewer 3pWn.
Dear Reviewer 3pWn,

Thanks again for your time and effort involved in the review process. As the discussion period is approaching its conclusion, we want to respectfully remind you of our last correspondence. Given your earlier indication that a re-evaluation of the score was possible based on our response, if there are no further concerns, might we kindly ask you to consider reassessing your score? Your continued support would be greatly appreciated, as it would significantly bolster our efforts. Thank you once again for your time and consideration.
Thank you once again for your constructive feedback and your willingness to consider raising your score to 5. We greatly appreciate your support. We have noticed, however, that the updated score has not yet been reflected in the system. If it’s not too much trouble, could you kindly take a moment to update the rating at your earliest convenience? We greatly appreciate your attention to this detail, which is crucial for the final evaluation of our work. Thank you very much for your continued support and consideration.
Thank you for acknowledging our work and raising the score, as well as for the insightful suggestions and valuable discussions. We fully concur that a thorough investigation of the limitations and a clear identification of the settings where our method excels are essential for the comprehensiveness of our study. We also appreciate the valuable suggestion for handling the SNAP dataset. We will incorporate all supplementary results and explanations into the final version of the paper and will continue to refine our work and add additional results based on your valuable feedback.
Thanks for the rebuttal; I am inclined to keep my current score, which is leaning to accept this paper.
Thank you for providing more results to evaluate your model and the additional clarification. I do acknowledge the following: 

- The use of CMs did improve the results in terms of solution quality and run-time when compared to other DM-based methods. 

- The sampling procedure inherited in pre-trained CMs (or generally DMs) at inference can be modified to be a per-instance solver and allow for conditional sampling. When compared to the inference of GNNs, I think the proposed approach has a better potential to further improve. I fully accept this point from the authors. 

- When compared to problem-specific heuristics, the method does achieve a significant improvement in terms of *inference* time due to the fast sampling of CMs and the use of GPUs. However, the method significantly under-performs when compared to these classic solvers in terms of solution quality. 

In short, under the setting that (1) a large accurately-labeled training set is accessible, (2) the massive "offline" training time can be ignored, and (3) the testing instances are not that different from the training set, the proposed solver can obtain "descent" solutions extremely fast. 

I am not suggesting that the proposed solver must outperform on every metric for every COP across all datasets. Instead, I am emphasizing that the authors should thoroughly investigate the limitations of their method and identify the setting in which it excels. 

A suggestion regarding SNAP graphs (very sparse and very large graphs): If the authors are still okay with labeling their training graphs using KaMIS (though I still have some reservations and believe this should be further investigated in subsequent versions of the paper), then KaMIS should be capable of obtaining solutions in a fair amount of time (albeit not guaranteed to be optimal), as it relies heavily on various graph reductions (see their results in the LwD paper for an example). Additionally, Google has introduced a SAT solver called CP-SAT (https://developers.google.com/optimization), which can solve very sparse/very large instances using the MIS ILP formulation significantly faster than Gurobi and KaMIS.

Although I have doubts over the practicality of the settings where this method excels, which I believe would require further investigations, I will raise my score to 5 given the potential of further improvements on the per-instance conditional sampling in trained CMs.
> **IV. How does the proposed method handle real-world graphs (such as SNAP graph in MIS)?**

Thank you for the question. We would like to reiterate that this paper primarily focuses on TSP evaluation as the main experiment, with MIS results included as supplementary evidence to demonstrate the model's ability to handle different problems. This structure aligns with the organization of leading conference works like DIMES, DIFUSCO, and T2T, and it's worth noting that many studies focus solely on TSP, such as GNNGLS and UTSP. We believe that TSPLIB experiments effectively supports the real-world performance of OptCM on the TSP problem. As for the MIS problem, we add the experiments on SATLIB dataset and we believe the results effectively demonstrate the model's capility to generalize to real-world graphs. 

Regarding SNAP graphs, we faced challenges completing experiments within the tight time constraints. The majority of SNAP graphs contain millions of nodes, making it extremely time-consuming for heuristic solvers to provide ground truth within the allotted time. Additionally, our model was primarily trained on problems with fewer than 1,000 nodes, and scaling up to the size of SNAP graphs might exceed the current generalization capabilities of our learning-based model. We intuitively believe a large-scale training dataset (e.g., ER-[9000-11000]) is necessary to better generalize to SNAP graphs. Although we are unable to provide results at this time, we are happy to extend our work to address this dataset in the immediate future.

---

Thank you for the advice and the opportunity to engage in this valuable discussion. We hope our response satisfactorily addresses your concerns and we will include all these meaningful empirical results and discussions in our final version.

We believe this work advances the field by making important strides in improving NCO's performance, given OptCM's strong empirical results and the potential to serve as a more powerful backbone model for future works. We would sincerely appreciate it if you could reconsider your rating, and we are more than willing to address any further concerns you may have.
1. Generalization results on the MIS problem for other p values. The models are trained on ER 700-800 with p=0.15. We can discover that OptCM outperforms all other learning baselines. 

| p   | Type      | Method               | Size      | Drop       | Time   |
| --- | --------- | -------------------- | --------- | ---------- | ------ |
| 0.2 | Heuristic | KAMIS                | 35.30     | -          |    58m37s    |
|     | Greedy    | DIFUSCO (T_s=100)    | 26.25     | 25.65%     | 6m31s  |
|     |           | T2T (T_s=50,T_g=30)  | 27.84     | 21.13%     | 7m52s  |
|     |           | OptCM (T_s=1,T_g=1)  | 28.04     | 20.58%     | 32s    |
|     |           | OptCM (T_s=5,T_g=5)  | **29.52** | **16.38%** | 1m57s  |
| 0.3 | Heuristic | KAMIS                | 24.36     | -          |    1h14m    |
|     | Greedy    | DIFUSCO (T_s=100)    | 15.84     | 34.99%     | 7m58s  |
|     |           | T2T (T_s=50, T_g=30) | 16.43     | 32.55%     | 8m20s  |
|     |           | OptCM (T_s=1, T_g=1) | 17.43     | 28.45%     | 51s    |
|     |           | OptCM (T_s=5, T_g=5) | **17.69** | **27.39%** | 2m52s  |
| 0.4 | Heuristic | KAMIS                | 18.19     | -          |     1h22m   |
|     | Greedy    | DIFUSCO (T_s=100)    | 11.75     | 35.40%     | 9m40s  |
|     |           | T2T (T_s=50, T_g=30) | 12.77     | 29.77%     | 10m28s |
|     |           | OptCM (T_s=1, T_g=1) | 12.86     | 29.30%     | 1m1s   |
|     |           | OptCM (T_s=5, T_g=5) | **13.27** | **27.06%** | 3m36s  |



2. We supplement the results on the SATLIB real-world dataset below. Initially, we did not include the SATLIB results because OptCM 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 a positive results of OptCM outperforming previous baselines.

|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+Sampling|DIFUSCO (T_s=100)|425.14|0.19%|53m41s|
|SL+Sampling|T2T (T_s=50,T_g=30)|425.18|0.18%|38m1s|
|SL+Sampling|OptCM (T_s=5,T_g=5)|**425.23**|**0.17%**|25m35s|


3. We supplement cross-dataset generalization results between RB graphs and ER graphs below. As seen, OptCM outperforms previous diffusion-based counterparts by a clear margin, e.g., in "Train:ER; Test:RB" "Sampling" setting, OptCM achieves significant performance gain from the previous (23.96%, 13m40s) to (10.64%, 2m37s).

|Setting|Type|Method|Size|Drop|Time|
|-|-|-|-|-|-|
|Train:ER; Test:RB|Greedy|DIFUSCO (T_s=100)|15.87|21.00%|10m8s|
|||T2T (T_s=50,T_g=30)|16.59|17.41%|15m5s|
|||OptCM (T_s=1,T_g=1)|16.73|16.59%|40s|
|||OptCM (T_s=5,T_g=5)|**17.01**|**15.21%**|2m39s|
|Train:ER; Test:RB|Greedy|DIFUSCO (T_s=100)|29.98|27.54%|10m48s|
|||T2T (T_s=50,T_g=30)|31.47|23.96%|13m40s|
|||OptCM (T_s=1,T_g=1)|36.39|11.96%|43s|
|||OptCM (T_s=5,T_g=5)|**36.94**|**10.64%**|2m37s|

> **III. Is the CM used in this paper in the generalization or memorization regime?**

Thank you for this very interesting question. OptCM indeed employs an atypical generative framework where we learn a high-quality solution distribution for a given instance, which can be viewed as a conditional generation process. However, since each condition (instance) is unique and the same instance conditions will not reappear during testing, the model cannot achieve plausible results by simply memorizing solutions for certain instance conditions. This is perhaps the intuitive response to your question. Nevertheless, we believe it is a rather open and intriguing question. Although we cannot provide empirical evidence due to the tight time window, we plan to investigate and analyze this question further in the future.
Thanks for acknowledging our efforts and the advice for a more comprehensive evaluation. Below we respond to your comments.

> **I. The value of ML4CO. "I also recognize 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." However, are any of these examples specifically combinatorial optimization problems?"**

Thanks again for the valuable point. Indeed, the discussion in the general response (2) is exactly for the CO context. We would like to summarize below.

1. Please first notice that ML4CO papers in [1] (e.g., DIMES, DIFUSCO, T2T, AM, POMO) and Bengio's first authored paper [2] claimed 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)." Traditionally, experts have to research on a given problem typically for many years to achieve a strong heuristic solver. While for ML solvers, they can learn from the historical data to implicitly discover strategies to plausibly handle a certain problem within a underlying data distribution. The neural inference also allows for GPU acceleration compared to traditional solvers. And the value of adapting to specific data distribution problems can be supported by [1] (e.g., DIMES, DIFUSCO, T2T, AM, POMO) and Bengio's first authored paper [2], which indicates that 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. **Please notice in these cases, we focus more on the  generalization performance under the IID assumption.**

2. The development of the ML4CO community can support the value of this research line. 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. 

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

[2] Bengio, Yoshua, Andrea Lodi, and Antoine Prouvost. Machine Learning for Combinatorial Optimization: a Methodological Tour d'horizon. EJOR 2021.

> **II. The comprehensiveness of the evaluation.**

Thanks for the suggestion. We still have to first note that we primarily focus 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. This follows the typical experiment organization of previous works like DIMES, DIFUSCO, and T2T.

For the TSP problem, 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. While for MIS problems, we try our best to further supplement more results within the tight time window below.
Thank you for acknowledging our efforts and raising the rating. We will continue refining our work to make a meaningful contribution to the community. However, we would still like to emphasize our novelty and respond to the concern of the capability for other constrained COPs.


**1) Novelty.**

Indeed CMs 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. 

Compared to diffusion solvers, the difference between the consistency mapping ($x_t\to x_0$) and the denoising function ($x_t\to x_{t-1}$) makes all the designs including model inference process, the training objective function, the gradient search procedure, etc., totally different. It is challenging to design such a new system with strong empirical performance.

Moreover, the experimental results can support our claims. 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. We believe that such strong empirical results substantiate the claim that OptCM represents more than just incremental progress within the existing diffusion framework.

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.

**2) Concern of the capability for other constrained COPs.**

As we previously mentioned, OptCM is theoretically capable of addressing any problem that can be framed as an edge-selecting or node-selecting problem. However, it is unrealistic to expect a single model to excel across all tasks. Different problems possess unique characteristics that may be better suited to specific methodologies. For problems like TSP, heatmap-based methods (using only basic greedy decoding) can achieve state-of-the-art performance, whereas RL-based approaches often struggle with sparse rewards and training instability, which may impede direct scaling to larger problem sizes. However, for problems with more complex constraints, sequence models demonstrate superiority by explicitly managing constraints at each step. Indeed, we do not yet know whether strong generative models can directly handle problems like CVPR; perhaps they already can, or at least have the potential to. (Though the discussion period is approaching its end, we will continue to adapt the framework to the CVRP task to validate this point.) The key point is that each methodological approach has its own strengths and weaknesses, and we do not expect the certain model to excel across all tasks. Indeed, there are also many papers in leading conferences merely focus on addressing a single problem, e.g., for TSP [1,2,3], MIS [4,5], SAT [6,7,8], etc., yet these contributions are still highly valued by the community.


[1] H-tsp: Hierarchically solving the large-scale traveling salesman problem. AAAI, 2023.

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

[3] Unsupervised Learning for Solving the Travelling Salesman Problem. NeurIPS, 2023.

[4] Learning What to Defer for Maximum Independent Sets. ICML, 2020.

[5] Maximum Independent Set: Self-Training through Dynamic Programming NeurlPS, 2023.

[6] Learning a SAT solver from single-bit supervision. NeurIPS, 2019.

[7] NSNet: A General Neural Probabilistic Framework for Satisfiability Problems NeurIPS, 2022.

[8] Online Bayesian Moment Matching based SAT Solver Heuristics. ICML, 2020.


---
Thank you again for the advice. We hope our response satisfactorily addresses your remained concerns. We believe OptCM advances the field by making important strides in improving NCO's performance, given OptCM's strong empirical results and the potential to serve as a more powerful backbone model for future works. We appreciate your previous acknowledgment and hope that our clarifications will merit a higher rating for our work.
Thank you very much for your thoughtful feedback throughout the review process. We are pleased to hear that you found our rebuttal satisfactory, and we are making every effort to improve the paper owing to your valuable feedback. We believe OptCM advances the field by making important strides in improving NCO's performance, given OptCM's strong empirical results and the potential to serve as a more powerful backbone model for future works.

Given your earlier indication that a re-evaluation of the score was possible based on our response, do you have any other concerns keeping you from raising your score? If any other concerns remain, we are more than willing to offer clarifications or engage in further discussions. Your continued support would be greatly appreciated, as it would significantly bolster our efforts. Thank you once again for your time and consideration.
Thank you for the extensive rebuttal. I am happy to keep my current score, which is leaning acceptance.
Thank you for your response.

I still believe that the contribution of this work is somewhat incremental, and the method may not be well-suited for constrained COPs. Nevertheless, I do see that the authors have made efforts to refine this work. Therefore, I am raising my score to 5. This neutral score means that if other reviewers and AC lean to accept this work, I would not oppose it. I encourage the authors to make more contributions in future version.
I would like to the thank the authors for their response. While I still have major concerns about the evaluation of this method, I will increase my score to 4 given the authors' efforts, clarity of presentation, using CMs, and developing the gradient search approach at inference.

### Generalization Discussion: 

I agree that generalization in data-driven ML is, in itself, a significant research topic across many applications. In fact, learning theory (such as: User-friendly introduction to PAC-Bayes bounds https://arxiv.org/pdf/2110.11216) does not really support good OOD performance. However, this paper proposes a supervised ML solver for combinatorial optimization problems, not image classification. Before deep learning, we lacked the capability to classify large-scale images like those in ImageNet. In contrast, combinatorial optimization problems have been well-studied in the past, with many problem-specific heuristics, such as LKH-3 and KAMIS, that remain unbeaten in terms of solution quality. While the proposed method did show faster run-time (excluding offline training time) when training data was available, the method should explore its limitations/capabilities to support the claims in [2].

I believe that evaluating graphs of different sizes and densities is feasible, as tools like NetworkX include several random graph generators that can help identify the instances the proposed method can effectively solve. In fact, a reasonable approach to evaluate whether the proposed model is learning patterns of solutions is to evaluate its OOD performance. 

I am not disputing the merit of conventional machine-learning-based methods for combinatorial optimization (ML4CO), rather highlighting that the authors should comprehensively evaluate their approach. An example of an ML4CO method (an RL-based approach) that fully evaluated its approach is the LwD method, which the authors considered as a baseline on only ER and RB graphs. 

### In the MIS problem, how does a CM trained on ER700 with p=0.15 generalize when faced with p=0.2? 

- I acknowledge the new results and the comparison with diffusion-based methods. However, I believe that reporting the results of KAMIS would provide more insight into the actual performance when training with p=0.15 and testing with p=0.2. The authors should evaluate with other values of p along with other graph random generators. 

- The SATLIB dataset (not considered) contains hard sparse instances that most dataless and data-centric methods consider, including T2T. Is it because OptCM cannot handle relatively sparser graphs than ER (with p=0.15)? Or is it because SATLIB does not provide enough data for training? 

### How does the size of the training dataset impact the outcomes?

OptCM uses CMs, which are essentially diffusion models designed for faster sampling. However, these models require an extensive amount of training data to enter the generalization regime (see Figure 2b of "The Emergence of Reproducibility and Generalizability in Diffusion Models"). Is the CM used in this paper in the generalization or memorization regime?

### How does the proposed method handle real-world graphs (such as SNAP graph in MIS)?

I acknowledge that the authors' reference to TSPLIB partially addresses the question. However, COPs vary significantly, so experimenting on the SNAP dataset using your MIS-trained model would help further understand the limitations/capabilities of the proposed method.

I also recognize 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." **However, are any of these examples specifically combinatorial optimization problems?**


### Label generation with KAMIS.

Yes, It would be beneficial for constructing training data. You could, in fact, use it to partially control the density in the graph. However, I am unsure how much it can help when the nodes degree distribution is different at testing time.

If you adopt a generative model to learn the distribution of *high-quality* solutions, how do you justify not having strict requirements for the optimality of the training data labels? The empirical observation in Figure 5 of the T2T paper pertains to the TSP problem, not the MIS problem.

### Q6: Missing iSCO and the differentiable solver in for comparison.

I acknowledge the comparison with iSCO for TSP and MIS. Excluding the training time and assuming dataset availability, OptCM generally requires less run-time compared to iSCO for in-distribution test instances.

### Q7: The ER results of DIFUSCO are not the same as were reported in the original paper?

Does the authors' response mean that the DIFUSCO results in this paper use a different diffusion model than the one used in the original DIFUSCO paper? If so, the authors should use the baseline method as is.
Thanks for the prompt reply. During the rebuttal process, we presented our novelty claim, supplemented large-scale results, and responded to the limitations of handling complex constraint problems. Despite this, the reviewer continues to express concerns regarding the limitations of heatmap-based methods, which we believe warrant meaningful discussion. Below, we offer our detailed response to this remaining concern.

> **1: While these heatmap methods incorporate post-processing techniques to theoretically handle any constraints, their practical performance may be inadequate, as the model often struggles to fully capture these constraints.**

We totally agree with this point. Relying on neural models to capture the constraints would require balancing the tradeoff between the model expressiveness and the task difficulty. When focusing on more complex constraints, sequence models will show their superiority in handling constraints by explicitly controlling constraints at each step. We will highlight this point in our final version. 

Nevertheless, we still need to note that 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 still the current SOTA for classic problems like TSP and MIS, highlighting their strengths. There have also been considerable heatmap-based works in leading conferences that maintain an impact on the community, like GCN, DIMES, DIFUSCO, T2T, etc., showing its value as an important research line in the Neural CO domain. 

Again, we note 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 believe our method, with a novel model backbone and strong empirical performance, can contribute to this community and inspire future works to further enhance NCO.

> **2. Due to the NP-hard nature of COPs with complex constraints, obtaining optimal solutions as labels remains impractical.**

Since we use a generative model to learn the distribution of high-quality solutions, we do not impose strict requirements on the optimality of the training data labels. As demonstrated in Fig. 5 of T2T, training with suboptimal labels can still produce plausible solutions—surpassing the quality of the supervision—by sampling from the generative distribution. Indeed, in our experiments, we obtain the labels of large-scale problems from heuristic methods like LKH and KAMIS, which only require high solution quality rather than strict optimality to produce reasonable empirical results. We will include a discussion of supervision requirements and also mention this in the discussion of the comparison between RL and SL in our paper.

> **3. Recent research [1] also questions the effectiveness of ML-based heatmap generation, suggesting that the performance is largely driven by the post-hoc search rather than the heatmap.**

Please note that [1] primarily focuses on heatmap-based methods paired with strong post-hoc search techniques like MCTS. In contrast, our approach only employs basic decoding strategies, such as greedy decoding. Yet without MCTS, OptCM still demonstrates highly competitive performance, even surpassing LKH within limited time budgets (please see Figs. 3 and 4). In our settings, compared to previous heatmap-based methods like DIMES, DIFUSCO, and T2T, OptCM significantly outperforms them across all decoding settings, underscoring the substantial impact of heatmap quality on solving performance (please see Tables 1, 2, and 4).

---
Thank you for the opportunity to engage in this valuable discussion. We hope our response effectively addresses your concerns. We believe this work advances the field by making important strides in improving NCO's performance. We would sincerely appreciate it if you could reconsider your rating, and we are more than willing to address any further concerns you may have.
Thank you for your response. However, I still believe this method faces significant challenges when addressing constrained COPs, such as CVRP, even with its relatively simple constraints.

1. While these heatmap methods incorporate post-processing techniques to theoretically handle any constraints, their practical performance may be inadequate, as the model often struggles to fully capture these constraints.
2. Due to the NP-hard nature of COPs with complex constraints, obtaining optimal solutions as labels remains impractical.
3. Recent research [1] also questions the effectiveness of ML-based heatmap generation, suggesting that the performance is largely driven by the post-hoc search rather than the heatmap.

[1] Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems, ICML, 2024.
> **Q6: Missing iSCO and the differentiable solver in for comparison.**

Thanks for providing the related works. The iSCO and MIS_dNN methods mentioned are more traditional methods, which are somewhat different from the previous data-driven machine learning solution algorithms. However, as another important line of algorithms also has an important reference value, we compare iSCO as follows. At the same time, for MIS_dNN's approach, we do not include it in the comparison for the time being, as we did not find implementations that can run through it. We will continue to make efforts to include the comparison of these two approaches in the paper, as well as a discussion of similar works in the related work section. 

For the experimental results, we discover that OptCM and iSCO perform better on TSP and MIS problems, respectively. On the other hand, OptCM significantly outperforms all data-driven learning-based methods by significant margins.

Comparison of the TSP problem. 

|N|Method|Size|Drop|Time|
|-|-|-|-|-|
|500|iSCO|16.64|0.54%|6m56s|
||DIFUSCO (T_s=100)|16.80|1.50%|4m40s|
||T2TCO (T_s=50,T_g=30)|16.68|0.82%|6m29s|
||OptCM (T_s=5,T_g=5)|16.61|0.39%|2m10s|
|1000|iSCO|23.33|0.91%|7m56s|
|| DIFUSCO (T_s=100)|23.55|1.89%|14m25|
|| T2TCO (T_s=50,T_g=30)|23.44|1.40%|19m39|
|| OptCM (T_s=5,T_g=5)|23.25|0.58%|8m37s|
|10000|iSCO|74.02|3.14%|1h36s|
|| DIFUSCO (T_s=100)|73.57|2.51%|31m24s|
||T2TCO (T_s=50,T_g=30)|-|-|-|
||OptCM (T_s=5)|72.94|1.63%|15m35s|


Comparison on the MIS ER-[700-800] dataset.

|Decoding|Method|Size|Drop|Time|
|-|-|-|-|-|
|Greedy|DIFUSCO (T_s=100)|37.03|18.53%|5m30s|
||T2TCO (T_s=50,T_g=30)|39.81|11.28%|7m7s|
||OptCM (T_s=1,T_g=1)|40.25|10.30%|25s|
||OptCM (T_s=5,T_g=5)|40.68|9.34%|1m32s|
|Sampling|iSCO (Few steps)|44.77|0.2%|1m23s|
||iSCO (More steps)|45.15|0.6%|5m34s|
||DIFUSCO (T_s=100)|39.12|12.81%|21m43s|
||T2TCO (T_s=50,T_g=30)|41.41|7.72%|27m45s|
||OptCM (T_s=1,T_g=1)|40.98|8.66%|1m19s|
||OptCM (T_s=5,T_g=5)|41.73|6.99%|5m51s|


> **Q7: The ER results of DIFUSCO are not the same as were reported in the original paper?**

To ensure fairness, all comparisons between DIFUSCO and T2T are based on categorical diffusion (discrete diffusion). The original DIFUSCO paper used Gaussian diffusion for the ER dataset (categorical diffusion was used for other data), which may lead to some performance differences. We will explain this in the paper.


> **Q8: The novelty is not that significant from the T2T method.**

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. Please kindly refer to the general response for the specific novelty claim.

In 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.”

> **Q9: The dependence on additional post-processing procedures needs to be further explained and investigated.**

OptCM does not rely on complex post-processing methods like MCTS. We only use a greedy approach to "round" the continuous output of the neural network to the nearest feasible path. Specifically, we sequentially insert edges or nodes with the highest confidence to the partial solution if there are no conflicts until we obtain a feasible solution. The sampling operation simply involves generating multiple heatmaps simultaneously and then applying the greedy method. Our comparisons with previous state-of-the-art methods are consistent and fair, demonstrating our advantages under various post-processing methods.

For all learning methods, since the neural network output is continuous, we cannot obtain feasible solutions without using greedy decoding (sequence models perform the greedy procedure within their models). The complexity of the greedy operation is O(num_of_decision_variables), which takes almost no time and is merely to ensure feasibility. This operation is similar to rounding continuous outputs between 0 and 1 to either 0 or 1. We would supplement the detailed descriptions to the main paper.

---
We 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 more powerful backbone model to drive the effectiveness of existing methods further. We would be sincerely grateful if you could reconsider your rating, and we are more than happy to address any further concerns you may have.