From Global Assessment to Local Selection: Efficiently Solving Traveling Salesman Problems of All Sizes

Thank you for your review comments and providing us the insightful and critical feedback. Here are our detailed responses to your comments. We are more than happy to discuss any further concerns or questions that you may have.

Weakness 1:

Although the hyperparameters are set based on certain considerations, a more in-depth exploration could be beneficial. For example, the impact of different values of m_r and m_c (the numbers of rows and columns for partitioning in RALA) on the model's performance for different TSP sizes and distributions could be further investigated.

Response 3.1 (sensitivity analysis on hypeprarameter $m$):

Thank you for your valuable suggestion. The hyperparameter $m$ divides a TSP topology into $m$ regions. The rationale behind this design is to strive for a good balance between model performance and computational complexity. As we mentioned in Section 4.1 and Appendix B.1, respectively:

"the hyperparameter $m=m_r\cdot m_c$ determines the granularity of the regional view: A larger m allows the model to capture more detailed local features but increases computational complexity. To balance performance and computational complexity, we set the numbers of rows and columns to $m_r$ = 3 and $m_c$ = 3, respectively, resulting in $m$ = 3 × 3 = 9 regions."

Per your suggestion, we have now conducted a sensitivity analysis on $m$ by retraining GELD (first-stage training) with three configurations:

• $m_r=2, m_c=2, m=4$ regions
• $m_r=3, m_c=3, m=9$ regions
• $m_r=4, m_c=4, m=16$ regions

Notably, we set the numbers of rows and columns equal to reserve the TSP's square topology, thereby preventing potential biases from specific distribution patterns that occupy only a subset of the TSP topology (see Figure 3).

The results on TSPs of the uniform and clustered distribution are as follows (see Table 10 of the revised manuscript for all results):

The results indicate that increasing $m$ generally improves model performance with a slightly lengthened inference time. Hence, our model is shown as robust given the consistently high overall performance obtained with various settings of $m$.

Thank you for your review comments and providing us the insightful and critical feedback. Here are our detailed responses to your comments. We are more than happy to discuss any further concerns or questions that you may have.

Weakness 1:

Weak experimental quantity: Obviously, as an auto-regressive model, conducting experiments only on TSP is far from enough. I believe, as the author mentioned in the summary section, at least another type of CO problem, such as CVRP or JSSP, needs to be done.

Response 2.1 (weak experimental quantity):

Our study focuses exclusively on TSP to ensure the depth of our research (i.e., using a unified model that both functions as a standalone solver and as an improvement method to solve various sorts of TSPs of all sizes), which coincides with the scope of recent studies published in top-tier conferences such as ICLR, ICML, and NeurIPS (see Response 1.1 to Reviewer Wg4P for details). Therefore, we strongly believe that given the depth of our research, comprehensive experimentation (on various sorts of TSPs of all sizes), and SOTA results achieved, our revised manuscript deserves an impartial consideration of being accepted by the flagship ML conference ICLR.

We acknowledge that using a unified model to effectively solve COPs (not only TSPs) of all sizes while efficiently enhancing solution quality is an exciting and worthwhile direction for future work. However, these problems involve greater complexity and distinct requirements, making it challenging to comprehensively address them alongside TSP in a single study.

Nonetheless, we are optimistic about the (future) application of GELD on other COPs because prior studies have shown that models performing well on TSP can achieve excellent results on other COPs (e.g., CVRP [1], JSSP [2], and Maximum Independent Set [3]). Importantly, GELD does not rely on operations (often) specifically tailored to TSP, such as heatmap+2-opt or Monte Carlo Tree Search Sampling [4].

Because we had conducted extensive experiments on TSPs of various sizes (ranging from 29 to 744,710 nodes) and distributions (including four synthetic and real-world patterns) to demonstrate the robustness and effectiveness of our proposed GELD model, we respectfully disagree with the characterization of the experimental quality as "weak".

Weakness 2:

Low novelty: The proposed PRC is conceptually similar to LCP in GLOP. Methodologically, especially in solving large-scale TSP problems, the two are almost identical, both relying on iterative reconstruction based on random greedy insertion.

Response 2.2 (low novelty):

We would like to clarify that one key innovation of our work lies in the enhancement of the effectiveness of re-construction by increasing the diversification of model inputs, not the concept of PRC itself (see Sections 3.4 and 4.1).

Methodologically, our proposed model differs from GLOP [5] in two significant aspects as follows:

1. Dual Functionality
   As stated in Section 2.2, "To the best of our knowledge, there does not exist a unified approach capable of both producing and improving TSP solutions". Unlike GLOP [5], which functions solely as a post-processing method relying on initial solutions generated via random greedy insertion, our model functions both as a neural construction model for independently generating TSP solutions and as a post-processing method for improving initial solutions produced by various models.

2. Unified Parameterization
   GLOP requires multiple pre-trained models (e.g., trained separately for TSP-20, TSP-50, and TSP-100) while our model employs a single set of pre-trained parameters. This unified model reduces the reliance on scale-specific training and enhances the model's practical applicability, a primary goal of our research and a key focus in the field.

We emphasize that the use of random greedy insertion algorithm in our study is intended to demonstrate the effectiveness of our model as a post-processing method, not to establish dependency on it. Unlike GLOP, which inherently depends on the random greedy insertion algorithm, our model demonstrates significant improvements over initial solutions across eight baselines (see Table 3).

Therefore, we believe the assessment of low novelty may stem from a misunderstanding of our contributions. While conceptual similarities between our work and GLOP exist, ours addresses critical challenges in the field by proposing innovative architectural solutions and achieving improved scalability and versatility. Therefore, we respectfully disagree with the characterization of our work as lacking novelty.

Thank you for your 2nd-round review comments. Here are our detailed responses to your comments.

Comment 1:

The datasets I am referring to are the following, all of which are publicly available and unified: DIMES: https://github.com/DIMESTeam/DIMES/tree/main/TSP/data Att-GCN and : https://github.com/Spider-scnu/TSP/tree/master/MCTS DIFUSCO T2TCO: https://github.com/Thinklab-SJTU/T2TCO/tree/main/data/tsp

Response 2.6:

Thank you for providing a list of publicly available synthetic datasets. While the provided datasets are publicly available, all of them are limited to uniformly distributed TSP instances. In contrast, we used the publicly available MSVDRP dataset (ICML'24), which includes instances from four distribution patterns: Uniform, Clustered, Explosion, and Implosion, as stated in our previous response (Response 2.3, Round 1):

Synthetic Data: The MSVDRP dataset from [1], encompassing TSPs of 5 sizes (TSP-{100, 500, 1000, 5000, 10000}) and 4 distribution patterns (uniform, clustered, explosion, and implosion). Each of these 5×4=20 subsets contains 200 instances (for TSP-{100, 500, 1000}) or 20 instances (for TSP-{5000, 1000}).

We believe the datasets encompassing these four distribution patterns better reflect the variety and complexity encountered in real-world scenarios than those only having one distribution pattern. Furthermore, we conducted experiments on the real-world TSPLIB dataset, which is also used in the studies you referenced [2–3]. Therefore, we consider our choice of datasets as reasonable and representative.

Comment 2:

I hope you can provide the solution length of LKH and neural models. Since the solver you used is not an exact solution, so only reporting the gap is unfair to other articles that you didn't cite. Alternatively, you can use Concorde as the baseline, and the corresponding dataset can be accessed through this link: https://github.com/Thinklab-SJTU/T2TCO/tree/main/data/tsp

Response 2.7:

Thank you for your comments. We have now included the LKH results on the synthetic dataset in Table 6 of the revised manuscript. The solution lengths of the neural models can be directly derived from the reported gaps based on the LKH results.

Regarding your statement that "Since the solver you used is not an exact solution, so only reporting the gap is unfair to other articles that you didn't cite", we respectfully disagree on this for the following reasons:

1. Use of Exact Solvers

   While exact solvers such as Concorde provide optimal solutions, they are computationally infeasible for large-scale TSPs (e.g., TSP-10000). Moreover, even with exact solvers, the resulting gaps reported in one study could not directly be used in other studies, because differences in (synthetic) datasets and solver configurations can lead to inconsistent benchmarks. We believe that a fair comparison can only be made if all baseline models are evaluated under the same conditions, as we have done in all experiments in this work.

2. Comprehensive Evaluation Metrics

   Evaluating model performance requires the assessment of both solution quality and inference speed. Focusing exclusively on solution quality may neglect critical practical aspects such as inference speed, which is particularly vital in real-world applications like smart logistics hubs and automated ports and terminals. Therefore, we report results for all baseline models under consistent experimental settings on our hardware. Directly comparing solution quality across models without running the respective code to get the inference time would fall short in the evaluations of reliability and comprehensiveness.

Nonetheless, per your suggestion, we have now conducted additional experiments using the datasets accessed through the links you provided (see Appendix B.8 of the revised manuscript).

Thank you for your review comments and providing us the insightful and critical feedback. Here are our detailed responses to your comments. We are more than happy to discuss any further concerns or questions that you may have.

Weakness 1:

The motivation is not clear. Authors mention that Destroy&Repair may fail to provide valuable insights for solving other COPs such as JSSP, but the results of other problems are missing.

Response 1.1 (unclear motivation):

First of all, we would like to clarify that our manuscript did not claim that the Destroy & Repair (D&R) strategy may fail to provide insights for solving other combinatorial optimization problems (COPs). Instead, the discussion in the Introduction section highlights the limitations of the Divide & Conquer (D&C) approach. The D&C strategy fundamentally differs from the D&R-based strategies such as re-construction which we had discussed in Section 3.4 of our manuscript.

Regarding the absence of results on other COPs, our study focuses exclusively on the Traveling Salesman Problem (TSP) to ensure research depth. Specifically, we fill the corresponding research gap by developing a unified model that functions both as a standalone solver and as an improvement method to solve TSPs of all sizes. Furthermore, we conduct extensive experiments on 20 synthetic datasets (across 5 scales and comprising 4 distribution patterns) and 2 real-world datasets (77 instances from TSPLIB and 27 National TSP instances and 4 extremely large TSP instances from World TSP) with 7 state-of-the-art (SOTA) baseline models to demonstrate the effectiveness of our model. Our in-depth study coincides with the scope of a number of recent studies published in top-tier conferences, such as ICLR [1], NeurIPS [2], ICML [3], AAAI [4–7], SIGKDD [8], and AISTATS [9], and some submitted to ICLR'25 [10-12]. These works also focus exclusively on TSP without conducting experiments on other COPs. Therefore, we strongly believe that given the depth of our research, comprehensive experimentation (on various sorts of TSPs of all sizes), and SOTA results achieved, our revised manuscript deserves an impartial consideration of being accepted by the flagship ML conference ICLR.

While our current study only presents the results on TSP, we are optimistic about the (future) application of GELD on other COPs because prior studies have shown that models performing well on TSP can achieve excellent results on other COPs (e.g., CVRP [13] and JSSP [14]). Importantly, GELD does not rely on operations (often) specifically tailored to TSP, such as heatmap+2-opt or Monte Carlo Tree Search Sampling [15].

To sum it up, we believe the manuscript’s motivation is clear and appropriately presented. It is justified for us to exclusively focus on TSP among many other COPs by providing in-depth technical contributions and comprehensive experimental results on various types of TSPs of all sizes.

Weakness 2:

The contribution 1 is not rigorous. Heatmap-based methods such as Att-GCN and D&R methods Select and Optimize also use the same set of pre-trained model parameters for all the TSP scales.

Response 1.2 (contribution 1 not rigorous ):

We would like to emphasize that GELD fundamentally differs from the models you referenced. Specifically:

• Comparison to Att-GCN [7] and Select-and-Optimize [9]:
  • Both Att-GCN and Select-and-Optimize leverage advanced heuristic algorithms, namely Monte Carlo Tree Search in Att-GCN and refined POPMUSIC and Lin-Kernighan algorithm in Select-and-Optimize, and only function as improvement methods to iteratively refine initial solutions.
  • In contrast, GELD is a TSP solver that can learn from scratch, capable of directly generating high-quality solutions as a neural construction model, while additionally functioning as an improvement method to optimize initial solutions.

In response to your feedback, we have revised the first contribution for greater clarity and precision as follows:

"To the best of our knowledge, GELD is the first unified model with a single set of pre-trained parameters that effectively solves TSPs of all sizes while efficiently enhancing solution quality."

We believe this refinement more accurately highlights GELD's novelty and distinctiveness compared to existing methods.

Thank you for the authors' responses.

I am sorry I meant D&C, not D&R in W1. Thank you for pointing it out.

I have read your responses carefully, but I still have some questions:

1. The authors have mentioned that the biggest contribution/novelty is addressing the lack of a unified method for both producing and improving TSP solutions. Is it necessary to unify the two? Do you have any insights on this?

2. There are many related works for solving TSP based on D&C [1][2] or heatmap[3], and their work can be applied to various kinds of COPs, including TSP. I still have doubts about the application scope of this paper, especially for ICLR 2025.

3. The authors list the SOTA algorithms for large-scale TSPs in the experimental part. Actually, I would like to see more analysis, specifically:

• It would be clearer to list the Heatmap-based and the D&C methods separately, and you can refer to [1].
• There could be more discussions on the performance of GELD and other Heatmap-based / D&C methods to further claim the advantages of your framework.
• LKH results should be included in the experiments for comparison.

References:

[1] Zheng, Zhi, et al. UDC: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. (NeurIPS 2024)

[2] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. (NeurIPS 2023)

[3] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. (NeurIPS 2023)