CS5399 B Thesis Defense Presentation
Title: A MASSIVELY PARALLEL OPTIMAL TSP SOLVER FOR SMALL PROBLEM SIZES
Presenter: Benila Jerald
Advisor: Dr. Martin Burtscher
Date/Time: Friday, July 1st @ 10:00 a.m.
Location: https://txstate.zoom.us/my/martin.burtscher (no password required)
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 an exhaustive search algorithm for up to 7 cities and a branch and bound algorithm for larger 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 times and 15 times faster than CONCORDE and LKH, respectively.
Deadline: July 2, 2022, midnight