{"id":{"repo_id":"tdl","oai_identifier":"oai:tdl-ir.tdl.org:10877/16100"},"canonical_url":"https://search.dev.ndltd.org/etd/tdl/oai:tdl-ir.tdl.org:10877/16100","repository":{"repo_id":"tdl","name":"Texas Digital Library","base_url":"https://tdl-ir.tdl.org/server/oai/request"},"display":{"title":"A Massively Parallel Exact TSP Solver for Small Problem Sizes","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Jerald Xavier, Benila Virgin"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Burtscher, Martin","Metsis, Vangelis","Yang, Kecheng"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-07-27T21:19:06Z","subjects":["GPU","TSP","traveling salesperson problem"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["Jerald Xavier, B. V. (2022). A massively parallel exact TSP solver for small problem sizes [Master's thesis, Texas State University]."],"render_values":[{"text":"Jerald Xavier, B. V. (2022). A massively parallel exact TSP solver for small problem sizes [Master's thesis, Texas State University].","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10877/16100","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Burtscher, Martin","Metsis, Vangelis","Yang, Kecheng"]},{"key":"dc:creator","label":"Author","values":["Jerald Xavier, Benila Virgin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-08-31T18:11:08Z","2026-02-27T15:06:10Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-08-31T18:11:08Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-08"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["GPU","TSP","traveling salesperson problem"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["Jerald Xavier, B. V. (2022). A massively parallel exact TSP solver for small problem sizes [Master's thesis, Texas State University].","https://hdl.handle.net/10877/16100"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10877/16100"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["A Massively Parallel Exact TSP Solver for Small Problem Sizes"]}]}],"canonical_facts":{"dc:contributor":["Burtscher, Martin","Metsis, Vangelis","Yang, Kecheng"],"dc:creator":["Jerald Xavier, Benila Virgin"],"dc:date.accessioned":["2022-08-31T18:11:08Z","2026-02-27T15:06:10Z"],"dc:date.available":["2022-08-31T18:11:08Z"],"dc:date.issued":["2022-08"],"dc:description.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."],"dc:identifier":["Jerald Xavier, B. V. (2022). A massively parallel exact TSP solver for small problem sizes [Master's thesis, Texas State University].","https://hdl.handle.net/10877/16100"],"dc:identifier.uri":["https://hdl.handle.net/10877/16100"],"dc:language":["en"],"dc:subject":["GPU","TSP","traveling salesperson problem"],"dc:title":["A Massively Parallel Exact TSP Solver for Small Problem Sizes"],"dc:type":["Thesis"]},"updated_at":"2026-07-27T21:19:06Z"}