TSP_{GPU} v1.0 and v2.2
TSP_{GPU} v2.2 is a GPUaccelerated heuristic solver for the symmetric Traveling Salesman Problem with up to 32767 cities,
based on iterative hill climbing with 2opt local search. It supports much larger problem sizes than v1.0 and is probably the fastest
available 2opt implementation. With 240 climbers, it reaches 60 billion moves per second on a K40 GPU for problem sizes above 10000 cities.
The source code can be downloaded by clicking on TSP_GPU22.cu. A description of TSP_{GPU} v2.2 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 this License
and that by downloading TSP_{GPU} v2.2 you agree to the terms and conditions set forth in this license.
The source code can be compiled into an executable called TSP_GPU as follows:
nvcc O3 arch=sm_35 use_fast_math TSP_GPU22.cu o TSP_GPU22
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_GPU22 d18512.tsp 52
TSP_{GPU} v1.0 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_GPU.cu. A description of TSP_{GPU} v1.0 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 this License and that by downloading TSP_{GPU} v1.0 you agree to the terms and conditions set forth in this license.
The source code can be compiled into an executable called TSP_GPU as follows:
nvcc O3 arch=sm_20 TSP_GPU.cu o TSP_GPU
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_GPU 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]
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. "TSPLIBA Traveling Salesman Problem Library." ORSA Journal on Computing, Vol. 3, No. 4, pp. 376384. Fall 1991.
