TSPGPU v1.1 and v2.3

TSPGPU v2.3 is a GPU-accelerated heuristic solver for the symmetric Traveling Salesman Problem that is based on iterative hill climbing with 2-opt local search. It supports much larger problem sizes than v1.1 and is probably one of the fastest available 2-opt 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 TSPGPU v2.3 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 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 18512-city database d18512.tsp using 52 climbers (random restarts), enter:

./TSP_GPU23 d18512.tsp 52


TSPGPU v1.1 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_GPU11.cu. A description of TSPGPU v1.1 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 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 100-city 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 Random-Restart 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. 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.

This work has been supported in part by the National Science Foundation, by Texas State University, and by equipment donations from Nvidia Corporation.

Official Texas State University Disclaimer