GPU accelerated Hungarian algorithm for traveling salesman problem

Kaushik, Varsha Ravi Prakash

Permalink

https://hdl.handle.net/2142/97805 Copy

Description

Title

GPU accelerated Hungarian algorithm for traveling salesman problem

Author(s)

Kaushik, Varsha Ravi Prakash

Issue Date

2017-04-28

Director of Research (if dissertation) or Advisor (if thesis)

Nagi, Rakesh

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Compute Unified Device Architecture (CUDA)
• Linear assignment problem
• Traveling salesman problem
• Reformulation Linearization Technique (RLT)

Abstract

In this thesis, we present a model of the Traveling Salesman Problem (TSP) cast in a quadratic assignment problem framework with linearized objective function and constraints. This is referred to as Reformulation Linearization Technique at Level 2 (or RLT2). We apply dual ascent procedure for obtaining lower bounds that employs Linear Assignment Problem (LAP) solver recently developed by Date(2016). The solver is a parallelized Hungarian Algorithm that uses Compute Unified Device Architecture (CUDA) enabled NVIDIA Graphics Processing Units (GPU) as the parallel programming architecture. The aim of this thesis is to make use of a modified version of the Dual Ascent-LAP solver to solve the TSP. Though this procedure is computational expensive, the bounds obtained are tight and our experimental results confirm that the gap is within 2% for most problems. However, due to limitations in computational resources, we could only test problem sizes N < 30. Further work can be directed at theoretical and computational analysis to test the efficiency of our approach for larger problem instances.

Graduation Semester

2017-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/97805

Copyright and License Information

Copyright 2017 Varsha Ravi Prakash Kaushik

Owning Collections