Approximations using GPUs for Large Traveling Salesman Problems

Abstract

The purpose of this project is to use clever computational techniques to implement Metropolis Hastings algorithms on a GPU. To example the problem, we solve the traveling salesman problem using simulated annealing. The heart of implementing Metropolis Hastings on a GPU is to use the GPU to make hundreds of thousands of samples at each step, while checking and updating the objective and loss function in a purely parallel manner. Instead of basing updates on the best sample of a particular set of draws we simply take the last sample that was a success. This allows the update step to be made purely in parallel, with the only wait time being the write of the first success in a block.