Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization

Thanks for your insightful comments and for acknowledging novelty, model design, and empirical performance. Below we respond to the specific comments.

Q1: How does the computational complexity of OptCM compare with traditional diffusion models and other state-of-the-art neural solvers?

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. As shown in Table 1, 2, and 4, OptCM can achieve 82.8x speedup on TSP-50/100, 16.8x speedup on TSP-500/1000, and 26.3x speedup on MIS compared to previous SOTA diffusion counterparts even with solution quality advantage.

Q2: What specific optimizations were implemented to achieve the reported speedup in solution generation?

Compared to the time-consuming iterative sampling process requiring denoising across multiple noise levels, the speedup of OptCM comes from the method design that learns direct mappings from different noise levels to the optimal solution for a given instance. This facilitates high-quality generation with minimal shots. To learn such direct mappings, we propose an optimization consistency training protocol, which, for a given instance, minimizes the difference among samples originating from varying generative trajectories and time steps relative to the optimal solution. Please refer to Sec. 4 for algorithm details. We also supplement the specific algorithm in the PDF attachment of the general response.

We also supplement the specific design choices of our OptCM, and the listed hyperparameters correspond to those used in the algorithm presented in the paper. We will supplement these details to the paper to enhance its comprehensiveness.

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

Thanks for noting classical algorithms, which are indeed important for the comprehensive evaluation. Indeed we have already included traditional algorithms in our comparison: 1) For TSP, we compare SOTA traditional exact solvers Concorde and Gurobi, as well as Heuristic solvers LKH-3 and Fasthest Insertion. 2) For MIS, the compared SOTA traditional solvers include the exact solver Gurobi and the heuristic solver KaMIS.

The mentioned algorithms like simulated annealing or genetic algorithms are indeed not very competitive in solving hard problems. We supplement the experimental results of SA and GA below; please refer to Table 1 and 2 for the corresponded performance of other SOTA baselines, where competitive results fall within the drop of 1%.

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

We have provided the performance of OptCM on real-world datasets such as TSPLIB, and the relevant results are shown in Tables 5, 6, and Appendix A. The experimental results show that OptCM can generalize to the real-world data, which outperforms all the previous SOTA baselines. While for specific environments such as scenarios with noisy, incomplete, and dynamically changing data, we have not made customized designs to deal with them at the moment. Currently, OptCM is a fundamental model that focuses purely on the performance of the solving task on relatively clean data, but we also acknowledge the importance of studying the application to various noisy, incomplete, and dynamically changing scenarios, and we will take this as the future direction of our subsequent research. Thank you for your suggestions.

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 possible new backbone model to drive the effectiveness of existing methods further. Thank you again for your firm support and recognition of our paper. If our response has satisfactorily addressed your concerns, we would be sincerely grateful if you could consider a higher score, as it would greatly support our efforts. Thank you once again for your consideration.

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.

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

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.

Thanks for the valuable comments, and for acknowledging our writing and technical soundness. Nonetheless, we believe there may exist some misunderstandings, especially regarding the value of the research line of data-driven learning-based solvers. It seems the major concern of the comment is about the application of data-driven machine learning in problem solving, which might cause the model to fit a specific data distribution and limit its generalization to different distributions. To pre-clarify this potential misunderstanding that may affect the rating of our work, please kindly refer to the generalization discussion in the general response. This may also directly respond to the first question about the generalization ability of neural solvers.

In addition, we notice that the reviewer may focus more on the MIS problem. Here we note that Our paper introduces a foundational framework and a robust model for various CO problems. We conducted experiments on both the edge-selection problem TSP and the node-selection problem MIS, primarily focusing on TSP for a comprehensive evaluation of OptCM, including solving results, generalizability, runtime-drop curves, and hyperparameter studies. For MIS experiments, we mainly focus on showing OptCM's capability of handling different problems, while similar conclusions can be inferred from TSP results. This follows the typical experiment organization of previous works like DIMES, DIFUSCO, and T2T. As per your request, we also supplement generalization results on MIS to further strengthen our paper. Please see the specific comments below.

Q1: In the MIS problem, how does a CM trained on ER700 with p=0.15 generalize when faced with p=0.2? Scalability results on MIS problem to generalize to higher n.

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 and n. We find that the generalization ability of OptCM is significantly better than that of the previous diffusion-based methods DIFUSCO and T2T regarding both solution quality and speed, e.g., in ER 350-400 Sampling setting OptCM achieves significant performance gain from (23.28%, 24m31s) to (11.45%, 1m1s).

Q2: How does the size of the training dataset impact the outcomes?

For in-distribution evaluation, the larger the dataset, the better the learning outcome. This is a clear result of ML mechanisms, as having more data allows the model to better summarize more patterns and strategies. As for generalization, we can use a model pretrained on one dataset and apply it to the test data, which might only require a small amount of data from the new distribution for fine-tuning.

Q3: How does the proposed method handle real-world graphs?

We can train on data with a similar distribution and then test on a given real-world test set. In fact, we have already conducted tests on real-world TSPLIB data. While the out-of-distribution generalization results may degrade compared to in-distribution performance, our experimental results show that the degradation is not severe. OptCM's generalization ability is also better than other state-of-the-art learning-based solvers.

We note again that data-driven machine learning methods have their own value and role in various applications, such as optimization problems, including automatic strategy discovery, GPU acceleration, and adaptation to specific data distribution problems. The learning-based solver approach has also received significant attention from the machine learning community, underscoring the importance and acceptance of these methods. On the other hand, dataless methods and traditional solvers have their own advantages, such as better generalization performance and robustness. We will include related work, such as iSCO and MIS_dNN, in our paper for discussion.

Q4: The training time comparison with heuristics and ILP solvers

Traditional solvers do not require training, and we will supplement the training time for OptCM in the paper. For intuition, OptCM for TSP-500 requires about 45 hours of training on 4 A100 GPUs. For comparison, POMO for TSP-100 requires about 1 week on a single Titan RTX and Sym-NCO for TSP-100 requires 2 weeks on a single A100 GPU. It should be additionally noted that the training time is offline and does not affect the inference time during solving.

Q5: Label generation with KAMIS.

Thank you for your suggestion. It is very beneficial for constructing training data for MIS. On the other hand, we need to point out that since we adopt the generative model to learn the distribution of high-quality solutions, we do not have strict requirements for the optimality of the training data labels. T2T's Fig. 5 shows that training with worse labels can still yield plausible solutions (better than the supervision quality) during inference by sampling from the generative distribution.

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.

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.

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.

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.

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.

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

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.

Thank you for your valuable comments and insightful suggestions, as well as for acknowledging our novelty, motivation, non-trivial contributions, and convincing evaluations. Your questions and suggestions are instrumental in further strengthening our paper. Below, we respond to your specific comments.

Q1: Why we have the quantity F1 in equation (6) is the equivalence of the loss in eq (4)?

Thanks for your valuable suggestion. We will supplement the derivation and intuition to the paper.

Recall that $F_1=-\mathbb{E}\_{q(\mathbf{x}|G)q(\mathbf{h}|\mathbf{x},G)}\left[\log p_\theta(\mathbf{x},\mathbf{h}|G)- \log q(\mathbf{x})q(\mathbf{h}|\mathbf{x},G)\right]$, we apply an approximation to the posterior over $\mathbf{x}=\mathbf{x}\_0$ as a point estimate $q(\mathbf{x}|G)=\delta(\mathbf{x}-\mathbf{\eta})$ and obtain $F_1=\mathbb{E}\_{q(\mathbf{h}|\eta,G)}\left[\log\frac{q(\mathbf{h}|\mathbf{\eta},G)}{p_\theta(\mathbf{\eta},\mathbf{h}|G)}\right]$. This term is exactly the usual variational bound on negative log likelihood conditioned on graph $G$, which is exactly the optimization objective of the diffusion models. It can be further derived under the denoising diffusion framework similarly in the original DDPM paper: $\begin{aligned}F\_1&=\mathbb{E}\_{q(\mathbf{x}\_{1:T}|\eta,G)}\left[\log\frac{q(\mathbf{x}\_{1:T}|\mathbf{\eta},G)}{p\_\theta(\mathbf{\eta},\mathbf{x}\_{1:T}|G)}\right] \\\\ &= \mathbb{E}\_{q} \left[ \log \frac{\prod\_{t=1}^T q(\mathbf{x}\_t | \mathbf{x}\_{t-1},G)}{p\_\theta(\mathbf{x}\_T) p\_\theta(\eta | \mathbf{x}\_1, G) \prod\_{t=2}^T p\_\theta(\mathbf{x}\_{t-1} | \mathbf{x}\_t, G)} \right] \\\\ &= \mathbb{E}\_q \left[ -\log p\_\theta(\mathbf{x}\_T) + \sum\_{t=2}^T \log \frac{q(\mathbf{x}\_{t}|\mathbf{x}\_{t-1},G)}{p\_\theta(\mathbf{x}\_{t-1}|\mathbf{x}\_t, G)} + \log \frac{q(\mathbf{x}\_1|\eta, G)}{p\_\theta(\eta|\mathbf{x}\_1, G)} \right] \\\\ &= \mathbb{E}\_q \left[ -\log p\_\theta(\mathbf{x}\_T) + \sum\_{t=2}^T \log \left( \frac{q(\mathbf{x}\_{t-1}|\mathbf{x}\_t, \eta,G) }{p\_\theta(\mathbf{x}\_{t-1}|\mathbf{x}\_t,G)}\cdot \frac{q(\mathbf{x}\_t|\eta,G)}{q(\mathbf{x}\_{t-1}|\eta,G)} \right) + \log \frac{q(\mathbf{x}\_1|\eta,G)}{p\_\theta(\eta|\mathbf{x}\_1,G)} \right] \\\\ &= \mathbb{E}\_{q} \left[ \log \frac{q(\mathbf{x}\_T|\eta,G)}{p\_\theta(\mathbf{x}\_T)} + \sum\_{t=2}^T \log \frac{q(\mathbf{x}\_{t-1}|\mathbf{x}\_t, \eta,G)}{p\_\theta(\mathbf{x}\_{t-1}|\mathbf{x}\_t,G)} - \log p\_\theta(\eta|\mathbf{x}\_1,G) \right] \\\\ &= \mathbb{E}\_{q} \left[ D\_{KL}(q(\mathbf{x}\_T|\eta,G) \| p\_\theta(\mathbf{x}\_T)) + \sum\_{t=2}^T D\_{KL}\left(q(\mathbf{x}\_{t-1}|\mathbf{x}\_t, \eta,G) \| p\_\theta(\mathbf{x}\_{t-1}|\mathbf{x}\_t,G)\right) - \log p\_\theta(\eta|\mathbf{x}\_1,G)\right] \\\\ &= \sum\_t \mathbb{E}\_{q} \left[D\_{KL}\left(q(\mathbf{x}\_{t-1}|\mathbf{x}\_t,\eta,G) \| p\_\theta(\mathbf{x}\_{t-1}|\mathbf{x}\_t,G)\right)\right] + C \end{aligned}$ This term is the optimization objective on point estimate $\eta$. While in optimization consistency models, we do not directly predict $p\_\theta(\mathbf{x}\_{t-1}|\mathbf{x}\_t,G)$ in the objective calculation, but we can virtually estimate this term using an additional predicted $\hat{\eta}$ :

Then $F\_1$ can be reduced to the distance between the estimated $\hat{\eta}$ and the real $\eta$, i.e.,

which is equivalent to the consistency loss which optimizes points from different noise level to map to the target point.

Q2: The authors should include an algorithm box on the training of their OptCM framework.

Thanks for the nice advice. We have included specific training algorithms in the PDF attachment of the general response and will incorporate them into our paper.

Q3: More discussions on training details.

We supplement the specific design choices of our OptCM, and the listed hyperparameters correspond to those used in the algorithm presented in the paper. We will supplement these details to the paper to enhance its comprehensiveness.

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

Q4: Consistency training introduced additional training overhead; I think the authors did not discuss this in Appendix D.

Thanks for your careful review and suggestion. Since the consistency model requires two inference predictions with different noise levels during training, it requires twice the training cost of the original diffusion model. However, this overhead on training is offline, and the consistency model is much more efficient than diffusion at inference time. We will supplement this in our new revision.

We hope this response could help address your concerns, and we are more than happy to address any further concerns you may have.

Thanks for your valuable comment, nice suggestions, and for acknowledging our soundness, presentation, experimental extensiveness, and empirical performance. We seriously value the main novelty concern reflected in the comment and carefully address it in the general response. Below we respond to your specific comments.

Q1: This work is mainly incremental, based on previous works DIFUSCO and T2T.

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, which we also briefly summarize here:

1. Compared to DIFUSCO and T2T's diffusion models, OptCM's model design, including the model inference process and the training objective function, is very different. Indeed, consistency models are recognized as a new independent class of generative models in generative tasks, while we further establish optimization consistency models (OptCM) to tailor the model for optimization scenarios.
2. The testing-phase gradient search method proposed by OptCM represents a completely novel approach compared to that of T2T. In fact, due to the difference between consistency mapping and diffusion inference, OptCM's framework and implementation are fundamentally independent.
3. In terms of experimental results, OptCM demonstrates exceptional performance, not only in solution efficiency but also in the quality of the solutions. We believe such strong empirical results substantiate the claim that OptCM represents more than just incremental progress within the existing diffusion framework.

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

Q2: Larger-size TSPs, such as those with 100000 nodes, should be tested against state-of-the-art learning-based methods like GLOP.

Thanks for the valuable question. In the rebuttal phase, we extend our model training to TSP-10000 and compare OptCM with several baselines, including DIFUSCO and GLOP.

We also explore generalizing the model to 100k nodes to assess its scalability. However, we discover that although OptCM can achieve quick prediction in seconds, the greedy decoding procedure—which sequentially inserts edges or nodes with the highest confidence into the partial solution until a feasible solution is obtained—can be prohibitively time-consuming, making it meaningless for the evaluation. OptCM is not yet suitable for large-scale evaluations without an optimized decoding procedure or a high-level divide-and-conquer strategy like GLOP. Indeed we suggest that there may be a chance for the combination of OptCM's backbone model and GLOP's divide-and-conquer strategy for scalability.

We will add the above evaluation to our paper and include the discussion of GLOP in related work and future work discussion to enhance the comprehensiveness of the paper.

Q3: Limitations in addressing constrained COPs and supervision requirements.

In fact, our method can handle various constrained problems. We rely on the powerful expressive capability of generative models to learn the constraints, ensuring that the generated heatmap results are as close to feasible as possible. This is followed by post-processing (e.g., greedy algorithms) to utilize the model's output while strictly satisfying the constraints. This paradigm theoretically handles any constraint, which is also the approach used in previous mainstream works such as Diffusco and T2T. However, for more complex constraints, the model's ability to capture constraints may be limited. In such cases, using sequential models to explicitly control constraints at each step can be more effective. For example, the mainstream methods for the CVRP problem are still based on sequence models.

Nevertheless, heatmap methods have their own advantages, such as not suffering from the sparse reward problem, enabling them to end-to-end handle larger-scale problems with better solution quality. These methods are currently the SOTA for classic problems like TSP and MIS, highlighting their strengths. There has also been considerable works in leading conferences that maintain competitive performance, demonstrating the value of this line of research. Additionally, currently works focusing on extending neural solvers for larger-scale problems using divide-and-conquer paradigms become a new important line of research.

We believe that different methodological routes have their own expertise in dealing with problems of different characteristics, and each route has its own advantages and disadvantages. We will add these discussions to our paper, including a discussion of some recent works such as GLOP and LEHD [1].

We hope this response can help address your concerns. We believe that this work contributes to this community and could potentially provide a more powerful backbone for future works in this domain. We would sincerely appreciate it if you could reconsider your rating, and we are more than happy to address any further concerns you may have.

[1] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023.

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