Implementations about traditional baselines

[piupiupiuu]

Thanks for sharing the work. I wonder where I can find the implementation of those traditional insertion methods (e.g., farthest insertion)? I found an implementation of those methods in https://github.com/chaitjo/learning-tsp/tree/master, but they cannot complete within a short time as reported in the DIMES paper (6s for all 10000 TSP).

[q-rz]

Hello @piupiupiuu ,

Thank you for your interest in our work!

As far as I remember, we probably modified AM's implementation of these heuristics to support parallelism and ran them on a server with a large number of CPU cores. Unfortunately, I don't have access to that server now, so I am unable to provide you with our previous scripts.

Please feel free to let me know if you have any questions.

Thank you,

Ruizhong

[piupiupiuu]

Thanks for your reply!

Could you remember whether those heuristics were rewritten in c++? AM’s implementation already includes parallelism across different instances , and TSP-10000 contains 16 instances only. For a single TSP-10000 instance, it takes a very long running time.

[q-rz]

Thanks for following up!

I did write some C++ code in this project. Unfortunately, I don't quite remember now whether I wrote C++ code for these heuristics, as that was over three years ago.

AM's implementation uses NumPy, so you may first try translating NumPy into PyTorch to run the heuristics on a GPU, which should speed them up quite a bit. If they are still too slow, you may then try C++ LibTorch.

Sorry for the inconvenience. Please feel free to let me know if you have any questions.