ZEROs baseline in Table3

[Wastedzz]

Hi Yifan, thanks for providing this insightful work. I'm confused about the setting of ZEROs baseline in Table 3, following the description in the paper: "Actually, all elements of the heatmap are set to 10−10 to avoid division by zero errors" Should the diagonal values be 0？Did you conduct the column-wise softmax normalization? Or, naively, all values in the heatmap are 10−10 and no further post-processing.

And, what are the parameters used for MCTS in ZEROs baseline? How to evaluate this baseline following your codes?

Looking forward to your reply!

Best, Chenguang

[xyfffff]

Hi Chenguang,

Thank you for your interest in our work.

1. The diagonal values are not set to 0; they are also set to $$10^{-10}$$, as mentioned in the paper: "all elements of the heatmap are set to $$10^{-10}$$." We did not perform any post-processing, such as softmax normalization. The matrix where all elements of the heatmap are set to $$10^{-10}$$ is directly used as the heatmap.

2. The parameters used for MCTS in the ZEROs baseline can be referenced from the paper "Unsupervised Learning for Solving the Travelling Salesman Problem." In summary, the authors of UTSP tuned the MCTS hyperparameters and introduced randomness. If you’re interested in the specifics, you can check the MCTS source code in utsp and compare it with the one in default_mcts. As for how to evaluate this tweaked MCTS version, our paper discusses how the effect of the heatmap is neutralized, meaning different heatmaps have minimal impact on this version of MCTS.

Best regards,
Yifan

[Wastedzz]

Thank you for your feedback, I have reproduced the results of ZEROs in Table3. Unbelieveable, the MCTS provided by UTSP is insensitive to the quality of heatmap. If available, I would very appreciate that you can specify the differences between UTSP's version and that in default_mcts ? What's the magic leading to this？

Best, Chenguang

[xyfffff]

Hi Chenguang,

1. Why the performance improved after MCTS tuning: You can refer to Table 4 in the appendix of Unsupervised Learning for Solving the Travelling Salesman Problem, which lists the hyperparameters for the UTSP version of MCTS. These settings differ from the default MCTS. In fact, the UTSP version's hyperparameters were manually tuned to fit the TSP scale.

2. Why the impact of the heatmap is negligible: The way the heatmap is handled in MCTS also differs between the UTSP and default versions. UTSP applied sparsification and symmetrization to the heatmap, and there are also differences in how the edge potential is calculated. The default MCTS uses:

   $$ Z{i,j} = \frac{W{i,j}}{\frac{\sum{j \neq i}W{i,j}}{\sum{j \neq i}1}} + \alpha \sqrt{\frac{\ln (M+1)}{Q{i,j}+1}}, $$

   whereas the UTSP version uses:

   $$ Z{i,j} = H{i,j} + \alpha \sqrt{\frac{\ln (M+1)}{Q_{i,j}+1}}, $$

   Unfortunately, I haven't conducted ablation studies to pinpoint exactly which of these modifications diminished the impact of the heatmap, so I can't provide a definitive answer.

Best regards, Yifan

[Wastedzz]

Thanks for your insights and explanations. What an impressive work!