A Massively Parallel Exact TSP Solver for Small Problem Sizes

Date

2022-08

Authors

Jerald Xavier, Benila Virgin

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

The Traveling Salesman Problem (TSP) is a combinatorial optimization problem tasked with finding the shortest tour for visiting a set of cities such that each city is visited exactly once, and the tour ends in the starting city. This problem has gained attention among researchers because it is easy to describe yet difficult to solve. TSP has numerous important real-life applications, but its NP-hardness makes it difficult to find an optimal solution even for relatively small problem sizes. The literature describes many heuristic algorithms that solve the problem approximately but only few exact algorithms. The TSP solver implemented in this study is a GPU-accelerated exact solver for small problem sizes. The goal is to exploit the computing capabilities of modern GPUs for finding an optimal solution using simple algorithms. The algorithms used are exhaustive search for up to 7 cities and branch and bound for problems up to 30 cities. The branch and bound algorithm performs an irregular traversal of the search tree, making it challenging to parallelize efficiently, especially for massively parallel GPUs. I implemented the algorithm in CUDA and tested it on GPUs with different compute capabilities. My solver is exact and very fast. It outperforms the CONCORDE and LKH solvers for problems with up to 15 cities. On a 13-city instance, my solver is 36 and 15 times faster than CONCORDE and LKH, respectively.

Description

Keywords

GPU, TSP

Citation

Jerald Xavier, B. V. (2022). <i>A massively parallel exact TSP solver for small problem sizes</i> (Unpublished thesis). Texas State University, San Marcos, Texas.

Rights

Rights Holder

Rights License

Rights URI