Reproduce Table 4 in the Paper

[XX4869]

Thank you for releasing the awesome code. Very insightful work!

I was wondering if the code in this repository can reproduce the numerical results of Table 4 in the paper, specifically those of MCTS without heat map (right column)? I tried to modify the initialization of weight matrix W in the TSP_MCTS.h file to $W_{ij}=1$ (link to where I modified the code). But this gives me similar results as using heat map to initialize $W$, very different from the numbers reported in Table 4.

In addition, I came across this paper of yours together with your other repository. This paper (Table 1 last row) reports that on TSP-20, 50, and 100, MCTS with uniform initialization of $W$ (i.e., no predicted heat map) delivers similar performance as Concorde/LKH, which seems to be the opposite of Table 4 of the first paper. I must be missing something here. Could you please let me know what implementation difference of the two works is causing this (at least on TSP-20, 50, and 100)?

[Spider-scnu]

Hi, this result of table is average length of predicted solution in testset.

[XX4869]

Thank you for the quick response. But I don't really understand your answer. Can you please elaborate more?

Are you saying the numbers in Table 4 are the average length of predicted solutions, for both with and without heat map respectively (left and right column)? If so, how do I reproduce the numbers in the right column (no heat map)? As I said, I tried setting $W_{ij}=1$ as the initialization as indicated in the paper, but couldn't reproduce the numbers as reported in Table 4.

Any comments would be appreciated, thanks!

[Spider-scnu]

Hi, have you recompiled your project after modify related codes?

[XX4869]

Yes, I am using the CPU version and I believe the bash script (e.g., solve-100.sh) recompiles the code every time I run it. (Correct me if I'm wrong here.)

I also tried the code from your other repository, which doesn't have heat map (initialized with $W_{ij}=1$). As I mentioned before, this one reproduces Table 1 (last row) of your other paper. That is, the performance without heat map on TSP-20, 50, and 100 is similar to that with heat map.

[Spider-scnu]

Hi, how long did your MCTS run? The MCTS also is learning methods. If the running time of MCTS is long enough, nearly optimized solution will be searched.

[XX4869]

I understand. And before opening the issue, I have already tried many different values of Param_T at this line of the code.

I have tried 0.1,0.075,0.025,0.01,0.005,0.001 on TSP-20, 50, and 100--they ran faster and faster, but still they all gave performances within 2% of Concorde, very different from that of Table 4 (but similar to the earlier paper Table 1).

I am also aware that the paper claims Param_T=0.01 (T=10n milliseconds) although it didn't mention if it's GPU version or CPU version. While the earlier paper claims to use Param_T=0.075 (T=75n milliseconds).

Did your Table 4 numbers come from GPU instead of CPU?

[Spider-scnu]

Hi, all experiments were tested in GPU in this paper. The running time of MCTS is longer in another paper.

[XX4869]

Thank you for the confirmation. I think I'll need to try the GPU version as well as setting Param_T to even smaller values in the CPU version to reproduce Table 4.