Rethinking the "Heatmap + Monte Carlo Tree Search'' Paradigm for Solving Large Scale TSP

Q1: Use of Optimal Solutions for TSP-10000: Line 360 mentions using 3,000 optimal solutions for TSP-500 and TSP-1000 but only 128 for TSP-10000. Given the larger scale of TSP-10000, why were fewer instances used? Additionally, is it appropriate to base statistics on only 128 instances for TSP-10000?

The use of 128 instances for statistical collection was due to the substantial computational cost of solving TSP10k instances. To address this concern, we conducted additional experiments using 3,000 TSP10k instances to collect GT-Prior statistics. The results are as follows:

GT-Prior from 3,000 instances:

[4.40954829e-01, 2.53630246e-01, 1.33515263e-01, 7.21532501e-02,         
 4.04198735e-02, 2.33079141e-02, 1.37615144e-02, 8.31309549e-03,
 5.06598423e-03, 3.14667758e-03, 1.97710685e-03, 1.26587106e-03,
 8.18402837e-04, 5.30468506e-04, 3.56334569e-04, 2.46000853e-04, 
 1.61667227e-04, 1.05600366e-04, 7.76336025e-05, 5.29001834e-05,
 3.85334669e-05, 2.70667605e-05, 1.99000690e-05, 1.42333827e-05, 
 1.16000402e-05, 7.56669290e-06, 5.73335321e-06, 3.96668042e-06,
 3.50001213e-06, 2.10000728e-06, 1.50000520e-06, 1.46667175e-06,1.16667071e-06, 1.03333692e-06]

Compared to GT-Prior from 128 instances:

[4.4175625e-01, 2.5409375e-01, 1.3292500e-01, 7.1950000e-02, 
 3.9518750e-02, 2.3750000e-02, 1.4143750e-02, 8.0937500e-03,
 4.9125000e-03, 3.3312500e-03, 1.8437500e-03, 1.1125000e-03, 
 8.3750000e-04, 5.5625000e-04, 3.7500000e-04, 2.6250000e-04, 
 1.8125000e-04, 8.7500000e-05, 6.8750000e-05, 5.0000000e-05, 
 5.0000000e-05, 2.5000000e-05, 2.5000000e-05, 6.2500000e-06, 1.2500000e-05, 
 6.2500000e-06, 6.2500000e-06, 6.2500000e-06, 6.2500000e-06, 6.2500000e-06]

The comparison shows minimal differences in the statistical patterns (MSE: 8.5e-08, KL divergence: 5.68e-05). This is further validated by the performance on the TSP10k test set:

While the GT-Prior collected from more instances indeed achieves slightly better results, the improvement is marginal. Although we acknowledge that more instances would provide better statistical reliability, these results demonstrate that even a smaller number of instances can yield effective performance.

This finding reinforces two key advantages of our proposed GT-Prior for large-scale TSP solving:

1. Scale-invariance: Prior knowledge collected from smaller instances (e.g., TSP500) can be effectively applied to larger instances (e.g., TSP10k)

2. Sample-efficiency: The method's performance is relatively insensitive to the number of instances used for collecting statistics, enabling cost-effective GT-Prior generation.

Q2: Consistency in Instance Use Across Experiments: Please confirm whether the heatmaps used in experiments (Table 2 and Table 3) were generated using the same number of instances.

Yes, we maintained consistency in our experimental setup. For Tables 2 and 3, we used the same test instances as provided by [1] and the same heatmaps as provided by [2], ensuring fair comparison with previous works. This standardized evaluation protocol allows direct performance comparisons across different methods.

Ref:

[1] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7474–7482, 2021.

[2] Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoc search-based neural approaches for solving large-scale traveling salesman problems. In Proceedings of the 41st International Conference on Machine Learning, pp. 54178–54190, 2024.

Dear Reviewer 3WVZ,

Opening Statement

First of all, We earnestly request that you reconsider our work from a different perspective. Our primary contribution does not lie in proposing a novel hyperparameter tuning method; rather, we present a critical viewpoint that challenges the current research trajectory in this field. Our work aims to provoke a fundamental reassessment of the "Heatmap + MCTS" paradigm for large-scale TSP solving. We firmly believe that our insights and conclusions make a significant contribution by encouraging the research community to critically examine established assumptions and potentially redirect research efforts more effectively.

W1: Lack of Novelty in Hyperparameter Tuning: The focus on hyperparameter tuning for MCTS lacks novelty, as it involves tuning existing MCTS hyperparameters without introducing new ones or proposing new tuning methods. Previous studies intentionally left MCTS hyperparameters untuned to ensure fair heatmap performance comparisons, and this paper’s tuning approach lacks originality.

We maintain that comparing the best achievable performance of each heatmap approach provides the most fair evaluation, which motivated our decision to employ naive grid search for MCTS hyperparameter tuning.

For the novelty and contraibution of our work, we kindly direct you to the Opening Statement and the first point under "Common Concerns" in the Global Response: "1. Regarding Novelty and Research Values".

W2: Limited Applicability and Mixed Performance of GT-Prior

We would like to emphasize again that our primary objective is not to propose another SOTA heatmap. Instead, our work makes two critical observations:

1. From a problem-solving perspective, current heatmap methods still have significant room for improvement through proper MCTS hyperparameter tuning, as demonstrated in Table 2: Performance Improvement after Hyperparameter Tuning.

2. A simple, parameter-free heatmap, when combined with well-tuned MCTS parameters, can achieve comparable performance to previous resource-intensive methods.

We believe these findings should prompt serious reflection within the research community, potentially leading to more efficient approaches for solving large-scale TSP instances. While we acknowledge that our GT-Prior and MCTS configurations are specifically designed for TSP's problem structure and therefore do not generalize to other types of combinatorial optimization problems, this limitation is inherent and, more importantly, falls outside the scope of our research objectives.

We also kindly suggest the reviewer to refer to the second point under "Common Concerns" in the Global Response: "2. Generalization to Other CO Tasks"

Q1: Generalization to Other CO Tasks: The paper focuses on TSP. Do the authors anticipate that similar results could be achieved in other combinatorial optimization (CO) tasks, such as CVRP, or are these findings specific to TSP?

Please refer to our response to W1.

Q2: Clarification of Experimental Setup in Section 5.3: In the "GENERALIZATION ABILITY" section, the experimental setup needs clarification. For example, for DIMES on TSP-1000, does the original (ORI.) setup use a model and MCTS tuned for TSP-500 or TSP-1000? Similarly, does the generalization (GEN.) setting use MCTS tuned specifically for TSP-1000 or for TSP-500? Adding a table or flowchart to illustrate the configurations would enhance clarity.

We apologize for any confusion regarding Table 4. Let us clarify the experimental setup in detail: The table demonstrates the generalization capabilities of different methods from TSP500 to larger instances (TSP1k and TSP10k). Specifically:

For "Gen." results:

• DIMES, UTSP, and DIFUSCO: Models trained on TSP500 are used to generate heatmaps for TSP1k and TSP10k instances

• SoftDist: Parameters tuned on TSP500 are used to generate heatmaps for larger instances

• GT-Prior: The same heatmap obtained from TSP500 is directly used (requiring no additional inference)

• All methods use MCTS parameters that were optimally tuned for each specific test scale

For "Ori." results:

• These correspond to Table 3, where models were trained/tuned specifically for each problem scale

• We acknowledge a discrepancy between Tables 3 and 4/6 due to additional iterations in Table 3's results. We have corrected them in the updated manuscript.

We appreciate your attention to detail and will enhance the clarity of this experimental setup description in the next version of the manuscript.

Dear Reviewer DdHK,

Opening Statement

First of all, We earnestly request that you reconsider our work from a different perspective. Our primary contribution does not lie in proposing a novel hyperparameter tuning method; rather, we present a critical viewpoint that challenges the current research trajectory in this field. Our work aims to provoke a fundamental reassessment of the "Heatmap + MCTS" paradigm for large-scale TSP solving. We firmly believe that our insights and conclusions make a significant contribution by encouraging the research community to critically examine established assumptions and potentially redirect research efforts more effectively.

W1: Limited Scope to TSP: The study focuses only on TSP, which limits the generality of its findings. Addressing other CO problems would have increased the paper's impact.

Please refer to the second point under "Common Concerns" in the Global Response: "2. Generalization to Other CO Tasks"

W2: Lack of Novelty in MCTS Contribution: While the paper highlights the impact of MCTS tuning, this may not be seen as particularly novel, given the well-known power of MCTS. Including a discussion on why MCTS is preferred over other algorithms (e.g., 2-opt) and analyzing its synergy with the heatmap approach could add depth.

For our stance on the novelty of our work, we kindly direct you to the "Opening Statement" and the detailed discussion in the first point of "Common Concerns" in the Global Response: "1. Regarding Novelty and Research Values".

Regarding the Comparison between MCTS and Other Search Algorithms, we respectfully disagree with the suggestion to include comparisons with other search algorithms for the following reasons:

1. As indicated by our paper title, our work specifically focuses on analyzing the "Heatmap + MCTS" paradigm and the relative importance of its components. Comparing MCTS with other search algorithms falls outside the scope of our research objectives.

2. The superiority of MCTS-based approaches over other search algorithms (such as beam search) for large-scale TSP has been well-established in previous works. Given that the "Heatmap + MCTS" framework represents the current state-of-the-art in solving large-scale TSP, we believe a thorough analysis of this specific framework is both timely and necessary.

3. Regarding the 2-opt algorithm mentioned in your comments, we have already incorporated a more powerful k-opt operator in our MCTS implementation, as described in Section 3.2 under "Simulation." The k-opt operator inherently subsumes and outperforms the 2-opt algorithm, making additional comparisons redundant.

W3: Complexity and Sensitivity of MCTS Hyperparameters: MCTS requires numerous hyperparameters and appears highly sensitive to these settings, which could make practical implementation challenging and limit accessibility.

Given MCTS's remarkable success in solving TSP, despite its apparent complexity, understanding its internal mechanics is crucial. Our work systematically deconstructs the MCTS algorithm for TSP solving, and Section 4.1 provides a detailed examination of the five most critical parameters, effectively demystifying this seemingly black-box approach.

Furthermore, our SHAP analysis precisely identifies the most influential parameters, and we demonstrate that these can be efficiently optimized using SMAC3 with minimal computational overhead. Rather than viewing parameter tuning as a limitation, our work makes MCTS optimization more accessible by providing clear, practical implementation guidelines.

Q1: Parameter Tuning Difference: How does the parameter tuning approach in this paper fundamentally differ from prior methods like grid search?

No. However, as stated in our discussion on novelty and contribution, our primary objective is not to propose a new method, but rather to present a different perspective and validate it using straightforward approaches. Specifically, we employed grid search on MCTS parameters to obtain the best performance for each method type (which could only be definitively demonstrated through grid search) to illustrate two key points:

1. The critical importance of MCTS parameter tuning, as evidenced in Table 2: Performance Improvement after Hyperparameter Tuning.

2. The actual role of heatmaps within this framework, demonstrating that competitive performance can be achieved using a parameter-free, generalizable GT-Prior without any resource intensive model training.

For practical applications, various advanced hyperparameter tuning methods can be employed. As shown in Appendix F, using SMAC3 for parameter tuning demonstrates that the entire optimization process can be completed efficiently.

Q2: GT-Prior Extensibility: Can GT-Prior be applied to other combinatorial optimization domains beyond TSP, such as CVRP or MIS?

No, the non-generalizability of GT-Prior to other Combinatorial Optimization Problems (COPs) stems from two fundamental aspects:

1. Problem-Specific Structure: GT-Prior relies on statistical patterns derived from k-nearest neighbor relationships in optimal solutions, which is inherently tied to TSP's unique problem structure. This statistical prior is not naturally transferable to other COPs with different underlying structures.

2. TSP-Specific Search Operations: The MCTS implementation heavily depends on k-opt, a local search algorithm specifically designed for TSP.

Therefore, to extend the "heatmap + MCTS" framework to other COPs, two problem-specific adaptations are essential:

1. Design problem-specific GT-Prior that captures the unique structural properties of the target problem

2. Embed problem-specific local search algorithms into the MCTS framework,

We believe that these adaptations to other COPs, while interesting, fall beyond the scope of our current research objectives.

Ref:

[1] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7474–7482, 2021.

Dear Reviewer RLaV:

Opening Statement

First of all, We earnestly request that you reconsider our work from a different perspective. Our primary contribution does not lie in proposing a novel hyperparameter tuning method; rather, we present a critical viewpoint that challenges the current research trajectory in this field. Our work aims to provoke a fundamental reassessment of the "Heatmap + MCTS" paradigm for large-scale TSP solving. We firmly believe that our insights and conclusions make a significant contribution by encouraging the research community to critically examine established assumptions and potentially redirect research efforts more effectively.

W1: Lack of Novel Contributions: Limited to parameter tuning without introducing new technical contributions.

For our stance on the novelty of our work, we kindly direct you to the "Opening Statement" and the detailed discussion in the first point of "Common Concerns" in the Global Response: "1. Regarding Novelty and Research Values".

W2: Unclear Parameter Importance Application: Although the study included an analysis of parameter importance using SHAP, it would have been more informative if the paper had elaborated on how these results were applied and their overall significance.

We believe the SHAP analysis effectively reveals the contribution of each parameter to solution quality and have provided detailed instructions on how to interpret the SHAP plots in the caption of Fig. 1. Specifically, it serves two crucial purposes:

1. It quantitatively demonstrates which parameters most impact performance, challenging previous works' default configurations.

2. It guides efficient tuning by identifying key parameters to focus on.

Our performance improvements (Table 2) and efficient tuning results (Section 6) directly leverage these insights, validating the practical value of this analysis.

W3: Experiments Limited to TSP: Results would be more compelling with experiments in other domains, e.g., MIS.

Please refer to the second point under "Common Concerns" in the Global Response: "2. Generalization to Other CO Tasks"

W4: No Real-World Dataset Experiments: Including tests on real-world datasets like TSPLIB would strengthen the work.

We have conducted extensive experiments on the TSPLIB dataset, analyzing three categories:

• Small (0-500 nodes, 43 instances)

• Medium (500-2000 nodes, 21 instances)

• Large (2000-18512 nodes, 14 instances)

For detailed per-instance results, please refer to Table 7-12, Appendix E in the revised paper.

Our experiments used two hyperparameter settings:

1. Tuned parameters optimized on uniform TSP instances

2. Default parameters from [1]

Our TSPLIB experiments reveal several key findings:

1. Impact of Parameter Tuning: The dramatic performance variations between tuned and default parameters (e.g., UTSP's 26.51% vs 1481.66% on large instances) demonstrate the substantial impact of hyperparameter tuning.

2. Generalization Challenge: The limited transferability of parameters from uniform instances to TSPLIB reveals a fundamental generalization issue shared by all methods except the Zero heatmap, further emphasizing the crucial role of MCTS tuning in the framework. To illustrate the distribution shift between uniform and TSPLIB instances, we present visualizations of representative hard and easy instances across different scales in Figure 6, Appendix E in the revised paper.

3. Zero Heatmap Stability: The Zero heatmap's consistently stable performance across various instance sizes and distributions validates our claim that MCTS's contribution has been historically undervalued.

4. GT-Prior Effectiveness: Our proposed GT-Prior demonstrates remarkable adaptability, achieving superior performance particularly on large instances (3.52% with tuned parameters) and maintaining consistent performance across different parameter settings, suggesting it effectively combines the benefits of TSP prior knowledge with MCTS optimization.

5. Computational Efficiency: Unlike learning-based baselines that heavily rely on GPUs for both training and inference, GT-Prior's independence from GPU requirements removes a significant bottleneck when dealing with large scale real-world instances.

[1] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7474–7482, 2021.

[2] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35:25531–25546, 2022.

[3] Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural Information Processing Systems, 36:3706–3731, 2023.

[4] Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems, 36, 2024.