TSP_{GPU} v1.1 and v2.3
TSP_{GPU} v2.3 is a GPUaccelerated heuristic solver for the symmetric Traveling Salesman Problem that is based on
iterative hill climbing with 2opt local search. It supports much larger problem sizes than v1.1 and is probably one of the fastest
available 2opt implementation. With 1000 climbers, it reaches over 350 billion moves per second on a Titan V GPU for problem sizes
above 1000 cities.
The source code can be downloaded by clicking on TSP_GPU23.cu. A description of TSP_{GPU} v2.3 is available
here. Sample inputs for the symmetric traveling salesman problem are
available from the TSPLIB^{[1]} library here.
Note that TSP_{GPU} is protected by the license included in the beginning of the code.
The source code can be compiled into an executable called TSP_GPU as follows:
nvcc O3 arch=sm_35 use_fast_math TSP_GPU23.cu o TSP_GPU23
The executable approximately solves the traveling salesman problem represented by the input TSPLIB database using x
climbers. The minimal found tour length is printed to the standard output.
To solve the TSPLIB 18512city database d18512.tsp using 52 climbers (random restarts), enter:
./TSP_GPU23 d18512.tsp 52
TSP_{GPU} v1.1 is a GPUbased heuristic solver for the symmetric Traveling Salesman Problem with up to 110 cities, based on iterative hill climbing with 2opt local search.
The source code can be downloaded by clicking on TSP_GPU11.cu. A description of TSP_{GPU} v1.1 is available here. Sample inputs for the symmetric traveling salesman problem are available from the TSPLIB^{[1]} library here. Note that TSP_{GPU} is protected by the license included in the beginning of the code.
The source code can be compiled into an executable called TSP_GPU as follows:
nvcc O3 arch=sm_35 TSP_GPU11.cu o TSP_GPU11
The executable approximately solves the traveling salesman problem represented by the input TSPLIB database using x climbers. The minimal tour and its cost are printed to the standard output.
To solve the TSPLIB 100city database kroA100.tsp using 100,000 climbers, enter:
./TSP_GPU11 kroA100.tsp 100000
Publications
M. A. O'Neil and M. Burtscher. "Rethinking the Parallelization of RandomRestart Hill Climbing." Eighth Workshop on General Purpose Processing Using GPUs. San Francisco, CA. February 2015. [pdf] [slides] [video]
M. A. O'Neil, D. Tamir, and M. Burtscher. "A Parallel GPU Version of the Traveling Salesman Problem." The 2011 International Conference on Parallel and Distributed Processing Techniques and Applications, pp. 348353. Las Vegas, NV. July 2011. [pdf] [pptx]
References
[1] Reinelt, G. "TSPLIB  A Traveling Salesman Problem Library." ORSA Journal on Computing, Vol. 3, No. 4, pp. 376384. Fall 1991.
This work has been supported in part by the National Science Foundation, by Texas State University, and by equipment donations from Nvidia Corporation.
