Parallel 2-Opt Local Search on GPU

Authors: Wen-Bao Qiao, Jean-Charles Créput

Abstract:

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.

Keywords: Doubly linked list, parallel 2-opt, tour division, GPU.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1129646

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.”