Parallel 2-Opt Local Search on GPU

To accelerate the solution for large scale traveling
salesman problems (TSP), a parallel 2-opt local search algorithm
with simple implementation based on Graphics Processing Unit
(GPU) is presented and tested in this paper. The parallel scheme is
based on technique of data decomposition by dynamically assigning
multiple K processors on the integral tour to treat K edges’ 2-opt
local optimization simultaneously on independent sub-tours, where
K can be user-defined or have a function relationship with input size
N. We implement this algorithm with doubly linked list on GPU.
The implementation only requires O(N) memory. We compare this
parallel 2-opt local optimization against sequential exhaustive 2-opt
search along integral tour on TSP instances from TSPLIB with more
than 10000 cities.

Authors:

• Wen-Bao Qiao
• Jean-Charles Créput

Keywords:

• Doubly linked list
• parallel 2-opt
• tour division
• GPU.

References:

[1] R. D. Lawrence, G. S. Almasi, and H. E. Rushmeier, “A scalable parallel
algorithm for self-organizing maps with applications to sparse data mining
problems,” Data Mining and Knowledge Discovery, vol. 3, no. 2, pp.
171–195, 1999.
[2] S. A. Mulder and D. C. Wunsch, “Million city traveling salesman problem
solution by divide and conquer clustering with adaptive resonance neural
networks,” Neural Networks, vol. 16, no. 5, pp. 827–832, 2003.
[3] D. S. Johnson and L. A. McGeoch, “The traveling salesman problem:
A case study in local optimization,” Local search in combinatorial
optimization, vol. 1, pp. 215–310, 1997.
[4] “Experimental analysis of heuristics for the stsp,” in The traveling
salesman problem and its variations. Springer, 2007, pp. 369–443.
[5] M. Verhoeven, E. H. Aarts, and P. Swinkels, “A parallel 2-opt algorithm
for the traveling salesman problem,” Future Generation Computer
Systems, vol. 11, no. 2, pp. 175–182, 1995.
[6] T. Van Luong, N. Melab, and E.-G. Talbi, “Gpu computing for parallel
local search metaheuristic algorithms,” IEEE Transactions on Computers,
vol. 62, no. 1, pp. 173–185, 2013.
[7] K. Rocki and R. Suda, “Accelerating 2-opt and 3-opt local search using
gpu in the travelling salesman problem,” in High Performance Computing
and Simulation (HPCS), 2012 International Conference on. IEEE, 2012,
pp. 489–495.
[8] C. CUDA, “Programming guide: Cuda toolkit documentation.”