TSPGPU v1.0 and v2.1


TSPGPU v2.1 is a GPU-accelerated heuristic solver for the symmetric Traveling Salesman Problem with up to 32767 cities, based on iterative hill climbing with 2-opt local search. It supports much larger problem sizes than v1.0 and is probably the fastest available 2-opt 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 requested via email from burtscher@txstate.edu. Sample inputs for the symmetric traveling salesman problem are available from the TSPLIB[1] library here. Note that TSPGPU is protected by this License and that by requesting TSPGPU v2.1 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_GPU21.cu -o TSP_GPU21

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 18512-city database d18512.tsp using 52 climbers (random restarts), enter:

./TSP_GPU21 d18512.tsp 52



TSPGPU v1.0 is a GPU-based heuristic solver for the symmetric Traveling Salesman Problem with up to 110 cities, based on iterative hill climbing with 2-opt local search.

The source code can be downloaded by clicking on TSP_GPU.cu. A description of TSPGPU v1.0 is available here. Sample inputs for the symmetric traveling salesman problem are available from the TSPLIB[1] library here. Note that TSPGPU is protected by this License and that by downloading TSPGPU 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 100-city 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 Random-Restart 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. 348-353. 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. 376-384. Fall 1991.

Official Texas State University Disclaimer