Large scale parallel iterated local search algorithm for solving traveling salesman problem
Kamil Rocki, Reiji Suda · IEEE International Conference on High Performance Computing, Data, and Analytics · 2012
In this paper, we present a parallel implementation of a solution for the Traveling Salesman Problem (TSP). TSP is a classical problem in computer science. For a given number of cities N, find the shortest path that visits all N cities exactly once. This problem is classified as NP-hard. We show an effective way of parallelizing Iterative Local Search using inter-thread and inter-process communication. Our speedup when solving different instances of TSPLIB ranged from 524 to 5810 times using 256 nodes of 2 CPUs (3072 cores) using the TSUBAME 2.0 supercomputer.