{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97805"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97805","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"GPU accelerated Hungarian algorithm for traveling salesman problem","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.","abstract_html":"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 &lt; 30. Further work can be directed at theoretical and computational analysis to test the efficiency of our approach for larger problem instances.","abstract_has_math":false,"creators":["Kaushik, Varsha Ravi Prakash"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Nagi, Rakesh"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T20:33:32Z","date_published":"2017-08-10T20:33:32Z","updated_at":"2026-07-22T22:24:34Z","subjects":["Compute Unified Device Architecture (CUDA)","Linear assignment problem","Traveling salesman problem","Reformulation Linearization Technique (RLT)"],"languages":["en"],"rights":["Copyright 2017 Varsha Ravi Prakash Kaushik"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97805","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nagi, Rakesh"]},{"key":"dc:creator","label":"Author","values":["Kaushik, Varsha Ravi Prakash"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T20:33:32Z","2019-08-11T09:15:32Z","2017-04-28","2017-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Compute Unified Device Architecture (CUDA)","Linear assignment problem","Traveling salesman problem","Reformulation Linearization Technique (RLT)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Varsha Ravi Prakash Kaushik"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97805"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-05-01","The student, Varsha Ravi Prakash Kaushik, accepted the attached license on 2017-04-28 at 14:19.","The student, Varsha Ravi Prakash Kaushik, submitted this Thesis for approval on 2017-04-28 at 14:27.","This Thesis was approved for publication on 2017-04-28 at 14:50.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11137 on 2017-08-10 at 15:07:21","Made available in DSpace on 2017-08-10T20:33:32Z (GMT). No. of bitstreams: 2 KAUSHIK-THESIS-2017.pdf: 527459 bytes, checksum: 2b5a087d143fa9ffdfd2a6425f2e85cd (MD5) LICENSE.txt: 4224 bytes, checksum: 85ff39bf54c9a5f3b1c87d2984023eb3 (MD5) Previous issue date: 2017-04-28","Embargo set by: Colleen Fallaw for item 102858 Lift date: 2019-08-10T21:27:21Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 102858 on 2019-08-11T09:15:32Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["GPU accelerated Hungarian algorithm for traveling salesman problem"]}]}],"canonical_facts":{"dc:contributor":["Nagi, Rakesh"],"dc:creator":["Kaushik, Varsha Ravi Prakash"],"dc:date":["2017-08-10T20:33:32Z","2019-08-11T09:15:32Z","2017-04-28","2017-05"],"dc:description":["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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-05-01","The student, Varsha Ravi Prakash Kaushik, accepted the attached license on 2017-04-28 at 14:19.","The student, Varsha Ravi Prakash Kaushik, submitted this Thesis for approval on 2017-04-28 at 14:27.","This Thesis was approved for publication on 2017-04-28 at 14:50.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11137 on 2017-08-10 at 15:07:21","Made available in DSpace on 2017-08-10T20:33:32Z (GMT). No. of bitstreams: 2 KAUSHIK-THESIS-2017.pdf: 527459 bytes, checksum: 2b5a087d143fa9ffdfd2a6425f2e85cd (MD5) LICENSE.txt: 4224 bytes, checksum: 85ff39bf54c9a5f3b1c87d2984023eb3 (MD5) Previous issue date: 2017-04-28","Embargo set by: Colleen Fallaw for item 102858 Lift date: 2019-08-10T21:27:21Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 102858 on 2019-08-11T09:15:32Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97805"],"dc:language":["en"],"dc:rights":["Copyright 2017 Varsha Ravi Prakash Kaushik"],"dc:subject":["Compute Unified Device Architecture (CUDA)","Linear assignment problem","Traveling salesman problem","Reformulation Linearization Technique (RLT)"],"dc:title":["GPU accelerated Hungarian algorithm for traveling salesman problem"],"dc:type":["text"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:34Z"}