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

Authors: Xuanhao Pan, Chenguang Wang, Chaolong Ying, Ye XUE, Tianshu Yu
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Travelling Salesman Problem, Heatmap, Monte Carlo Tree Search, Combinatorial optimization, k-nearest neighbor

Abstract:
The Travelling Salesman Problem (TSP) remains a fundamental challenge in combinatorial optimization, inspiring diverse algorithmic strategies. This paper revisits the ``heatmap + Monte Carlo Tree Search (MCTS)" paradigm that has recently gained traction for learning-based TSP solutions. Within this framework, heatmaps encode the likelihood of edges forming part of the optimal tour, and MCTS refines this probabilistic guidance to discover optimal solutions. Contemporary approaches have predominantly emphasized the refinement of heatmap generation through sophisticated learning models, inadvertently sidelining the critical role of MCTS. Our extensive empirical analysis reveals two pivotal insights: \textbf{1}) The configuration of MCTS strategies profoundly influences the solution quality, demanding meticulous tuning to leverage their full potential; \textbf{2}) Our findings demonstrate that a rudimentary and parameter-free heatmap, derived from the intrinsic $k$-nearest nature of TSP, can rival or even surpass the performance of complicated heatmaps, with strong generalizability across various scales. Empirical evaluations across various TSP scales underscore the efficacy of our approach, achieving competitive results. These observations challenge the prevailing focus on heatmap sophistication, advocating a reevaluation of the paradigm to harness both components synergistically.

Decision: reject
Reviewer scores: 3, 5, 3

Reviews and discussion:
<thread>
creation date:
1729838265137

thread_type:
official_review

<thread_object>
creator: reviewer_3wvz

<content>
summary:
This paper emphasizes the importance of tuning the hyperparameters of MCTS in the heatmap+MCTS strategy for solving TSP. It conducts experiments to analyze the impact of each hyperparameter setting in MCTS. Additionally, it proposes a method to generate the heatmap at a very low computational cost and verifies its performance through experiments.

strengths:
- This paper experimentally shows that significant performance improvements can be achieved in solving TSP using heatmap+MCTS strategy by tuning the hyperparameters of MCTS.

- The proposed GT-Prior method demonstrates relatively superior results while consuming less computational cost compared to existing methods.

weaknesses:
- One major part of this paper, the hyperparameter tuning of MCTS, lacks novelty. In this paper, the authors simply tuned the existing hyperparameters of MCTS without introducing new hyperparameters or proposing a new tuning method, and in doing so, confirmed that it is possible to improve the accuracy of solving TSP. The authors claim that previous studies have not paid attention to the values of MCTS hyperparameters and emphasize the need for careful tuning of MCTS hyperparameters. In previous studies proposing new heatmap generation methods, it seems that MCTS hyperparameters were intentionally left untuned to allow for a fair comparison of the heatmap's performance. While this paper’s confirmation that tuning MCTS hyperparameters can improve TSP solution accuracy has some value, it is not novel that tuning hyperparameters can enhance solver performance. Therefore, simply finding better values for existing hyperparameters through traditional tuning methods is considered to lack novelty.


- The newly proposed GT-Prior heatmap generation method in this paper suggests a way to create a heatmap with minimal computation. Although this method showed the best performance in TSP-10000, it yielded worse results than existing methods (DIFUSCO, SOFTDIST) in TSP-500 and TSP-1000. Additionally, since the GT-Prior method statistically calculates the likelihood of inclusion in the optimal solution based on a ranking of **distances between nodes**, it is likely difficult to apply this method to problems other than TSP, especially those with complex constraints.

questions:
- In line 360, it is mentioned that 3,000 optimal solutions were used to calculate $\hat{P}_N()$ for TSP-500 and TSP-1000, while only 128 optimal solutions were used for TSP-10000. Given that TSP-10000 is larger in scale, I would expect more instances to be used than for the smaller TSP problems, yet only 128 were used. What is the reason for this? Similarly, I would like to know the authors' opinion on whether it is appropriate to calculate $\hat{P}_N()$ based on statistics from only 128 instances for TSP-10000. 
- Additionally, please confirm whether the $\hat{P}_N()$ used in the experiments in Table 2 and Table 3 was generated using the same number of instances.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730694204829

thread_type:
official_review

<thread_object>
creator: reviewer_ddhk

<content>
summary:
The paper revisits the “heatmap + Monte Carlo Tree Search (MCTS)” approach for the Travelling Salesman Problem (TSP). It argues that excessive focus on heatmap refinement in previous research has overshadowed the significant impact of MCTS configuration. Through empirical evaluation, the authors demonstrate that tuning MCTS parameters is critical for solution quality, and a basic k-nearest neighbor-based heatmap performs comparably to complex models.

strengths:
1, The paper highlights the often-overlooked role of MCTS in improving solution quality, shedding light on its critical impact in the TSP solution process.

2, By introducing a simple, training-free k-nearest neighbor-based heatmap algorithm, the paper demonstrates a practical approach that achieves performance comparable to state-of-the-art models.

3, Experiments across varying TSP scales reinforce the findings, with clear evidence supporting the role of MCTS tuning.

weaknesses:
1, It would have been beneficial if the paper addressed a broader range of combinatorial optimization (CO) problems rather than focusing solely on TSP.

2, MCTS is a very powerful algorithm, and previous studies have shown significant performance improvements when MCTS is added. Considering this, the paper’s finding that ‘MCTS has a large impact and careful tuning improves performance’ doesn’t feel particularly novel. It would be helpful to include a discussion on the advantages of MCTS over other local search algorithms (e.g., 2-opt) to clarify why MCTS is chosen. Additionally, an analysis of the synergy between MCTS and the heatmap approach would add value, especially considering that, as seen in Table 2, algorithms like Dimes and UTSP perform worse than Zero when MCTS is used.

3, MCTS involves numerous hyperparameters and appears highly sensitive to these settings, which could make practical implementation challenging and less accessible.

questions:
1, The paper currently addresses only the TSP problem. Do you anticipate that similar results would be achieved if this approach were applied to other CO tasks, such as CVRP? Or are these findings specific to TSP? I’m curious to know if the method generalizes well to tasks beyond TSP.

2, The experimental setup in Section 5.3 (“GENERALIZATION ABILITY”) could be clarified. For example, for DIMES on TSP-1000, it is unclear whether the original (ORI.) setup uses 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 is it using MCTS tuned for TSP-500? Adding a table or flowchart to illustrate the training and testing configurations, specifying the problem sizes for model training, MCTS tuning, and evaluation, would greatly enhance clarity.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730706640075

thread_type:
official_review

<thread_object>
creator: reviewer_rlav

<content>
summary:
This paper suggests a novel approach to solving the traveling salesman problem (TSP) by leveraging neural combinatorial optimization techniques, focusing on Monte-Carlo tree search (MCTS) that utilizes a probability distribution in the form of a heatmap for city-to-city edges. Although existing studies have also explored methods combining heatmaps and MCTS, this paper highlights that optimizing MCTS parameters within the conventional 'heatmap + MCTS' framework can enhance performance. Building on this insight, the authors propose a new, parameter-free algorithm for heatmap generation called GT-Prior. Experimental results from TSP-500, TSP-1000, and TSP-10000 demonstrate that performance improvements can be achieved through MCTS parameter optimization in current heatmap-based methods. Furthermore, the GT-Prior algorithm, when integrated with MCTS, achieves performance that is comparable to or slightly better than traditional approaches.

strengths:
The paper is well-written and easy to follow. It provides a detailed explanation of MCTS algorithm parameter tuning for the TSP problem, dedicating significant effort to the experimental performance improvement and analysis of existing heatmap algorithms through MCTS parameter optimization. The newly proposed GT-Prior algorithm effectively captures the characteristics of the TSP problem and demonstrates a simple yet competitive performance compared to traditional heatmap generation algorithms.

weaknesses:
As the authors mentioned, heatmap-based MCTS algorithms have been studied in the past. It would have been more impactful if the proposed MCTS algorithm in this paper had shown new technical contributions beyond parameter tuning. 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. Additionally, it is a limitation that the experiments were conducted solely within the TSP domain. It would have been more compelling if additional experiments had been performed across various CO domains, such as the Maximal Independent Set (MIS). Furthermore, while the paper addresses large-scale problems like TSP-1000 and TSP-10000, including real-world experiments using datasets like TSPLIB would have strengthened the work.

questions:
1. Previous MCTS studies have employed parameter tuning methods like grid search. What fundamentally differentiates the parameter tuning approach in this paper from those in prior research?

2. Would it be possible for GT-Prior to be extended and applied to other combinatorial optimization domains, such as CVRP or MIS, beyond the TSP problem?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731596390143

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We sincerely thank all SACs, PCs, ACs, and reviewers for their time and effort on our manuscript. While we appreciate the constructive comments, we believe there are some misunderstandings about our work's core contributions and significance. In this response, we will first highlight our key contributions to learning-based TSP solving, followed by addressing the common concerns raised by reviewers.

## Motivation of the "heatmap + MCTS" paradigm
The "heatmap + MCTS" paradigm first introduced by [1] and subsequently adopted by several state-of-the-art methods  [2,3,4], has emerged as one of the most successful approaches for solving large-scale TSP  instances with up to 10,000 nodes, significantly outperforming previous neural approaches. One should note, the main motivation of this series of works is:

**Main motivation**: To better solve large-scale TSPs 

This motivation inspires an abundance of following works to develop more sophisticated heatmap generation methods seeking to push the boundary of solution quality. Here, please remember the **main motivation of all this line of work**.

## Our Motivation
We want to emphasize that our motivation aligns with the **Main motivation** stated above in the first place. Designing fancy heatmap generation methods, in our opinion, serves as a path to the **Main motivation**. Despite its remarkable success of "heatmap+MCTS", there has been a notable gap in systematically analyzing which component plays the pivotal role in this framework. Previous works have implicitly assumed the dominance of the heatmap component, directing most research efforts towards developing sophisticated learning-based heatmap construction methods. However, our comprehensive experiments reveal a surprising and novel finding: even with a simple zero-initialized heatmap devoid of any prior information, properly tuned MCTS parameters can achieve remarkably competitive results. This finding fundamentally challenges the prevailing assumption about the heatmap's primacy in the framework, and can be a big step towards the **Main motivation**.

## Our Contribution
Our work makes two significant contributions to address this research gap. 
1. First, through systematic parameter tuning - the most straightforward approach - we demonstrate the crucial importance of MCTS  in the framework, which has been previously underestimated. 
2. Second, we propose a parameter-free heatmap based on optimal solution priors, which exhibits strong generalization capabilities and achieves comparable  performance to many existing learning-based heatmaps. 

While we acknowledge the impressive performance of previously proposed heatmaps, our findings raise important questions for the research community:  

> **Should we continue investing substantial computational resources and research efforts in designing increasingly complex heatmaps for TSP?  Have we perhaps strayed from our primary goal of solving the TSP efficiently?** 

We believe these questions merit serious consideration as we move forward in this field. And we believe these helpful findings represent substantial contributions, and stick to the **Main motivation** to better solve large-scale TSP, rather than proposing complicated methodical designs.

## Response to Common Concerns
### 1. Regarding Novelty and Research Values
We appreciate the reviewers' concerns about novelty, but we believe there might be a misunderstanding about the fundamental value and contribution of our work. We would like to emphasize that true scientific advancement doesn't always necessitate complex, novel methodologies; sometimes, **it requires challenging established assumptions and redirecting research focus through straightforward yet insightful analysis**. 
Our work's novelty lies in its critical examination of a widely accepted paradigm rather than proposing another sophisticated solution. We deliberately chose simple, interpretable approaches to demonstrate our findings because they most clearly illuminate the overlooked aspects of the "heatmap + MCTS" framework. 
We respectfully ask reviewers to reconsider our work's value through this lens as a contribution that **promotes critical thinking** and **potentially redirects research efforts** toward more efficient problem-solving approaches.
### 2. Generalization to Other CO Tasks
As proposed in the title of our manuscript, we specifically focused on TSP as the "Heatmap + MCTS" paradigm is uniquely successful in this domain, with state-of-the-art results from multiple recent works [1,2,3]. Notably, this paradigm has not yet been successfully adapted to other CO problems - current leading approaches for CVRP and other tasks use different methodologies entirely.

We will address the specific concerns raised by each reviewer in the following individual responses. We sincerely appreciate your time and  attention in reading through this global response.

The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This work re-evaluates the “heat map + MCTS” paradigm for solving large traveling salesmen problems (TSP) (e.g., those with up to 10,000 nodes).  This work has the potential to change the way researchers think about large-scale TSP. The authors run extensive experiments examining the effect of MCTS HPs, and propose simple baselines (“GT-Prior” or “Zero”)  that when combined with HP optimization result in optimization performance that rivals competing approaches.

Many reviewers found the scope of the paper to be narrow (focused exclusively on TSP) (RLaV, DdHK), and did not find the contribution of highlighting the importance of HPs for heat map algorithms to be sufficiently compelling for publication at ICLR.  All reviewers did not advocate for acceptance, even after the rebuttal period and reviewer discussion.  In general, this paper is a bit of an odd fit for a conference on representation learning, and a different audience, such as AAAI or perhaps NeurIPS may have an audience that can better appreciate and critique the contributions. 

As an aside: it would be interesting to use more standard methods for measuring sensitivity to HPs, such as Sobol indices or derivative-based methods for hyper parameter importance.  Some findings about what ranges of HPs tend to work best across problems could be helpful.  If importances do not generalize across problems, that could be put more simply in the main text.