{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/116108"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/116108","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"GPU accelerated transportation simplex algorithm","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","abstract_has_math":false,"creators":["Mahajan, Mohit"],"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":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-07-22T22:24:55Z","subjects":["Parallel Algorithms","Transportation Problem","Operations Research","Simplex","GPU","CUDA"],"languages":["en","eng"],"rights":["Copyright 2022 Mohit Mahajan"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/116108","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":["Mahajan, Mohit"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-08","2022-07-19"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"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":["Parallel Algorithms","Transportation Problem","Operations Research","Simplex","GPU","CUDA"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 Mohit Mahajan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/116108"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","The student, Mohit Mahajan, accepted the attached license on 2022-07-14 at 17:01.","The student, Mohit Mahajan, submitted this Thesis for approval on 2022-07-14 at 17:08.","This Thesis was approved for publication on 2022-07-19 at 13:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18320 on 2022-11-15 at 21:40:27","Transportation Problem (TP) is a popular mathematical model for optimally matching several supply centers to several demand centers at the smallest transportation cost. Recent disruptions in the physical supply chains and the growth of internet marketplaces such as ride-sharing, doorstep delivery, and expedited shipping have engendered a need for efficient algorithms to solve fundamental TP in near real-time. The traditional ways to solve TP are unsuitable for some of these systems because their run-time causes latency issues. The evolution of accelerated computing using Graphics Processing Units (GPUs) has recently attracted some interest in solving optimization problems. In this research, an attempt has been made to solve TP in an accelerated way using a GPU. The Transportation Simplex Algorithm (TSA) is one of the efficient ways to solve the TP. A detailed study has been conducted to expose the underlying parallelism in the iterative steps of TSA. The parallel design proposed improves runtime through simultaneously executing multiple independent iterations. The results show that the accelerated algorithm performs up to 5 times faster on an average compared to the known sequential algorithm and up to 3 times faster on an average compared to the state-of-the-art commercial Linear Programming solver."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["GPU accelerated transportation simplex algorithm"]}]}],"canonical_facts":{"dc:contributor":["Nagi, Rakesh"],"dc:creator":["Mahajan, Mohit"],"dc:date":["2022-08","2022-07-19"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","The student, Mohit Mahajan, accepted the attached license on 2022-07-14 at 17:01.","The student, Mohit Mahajan, submitted this Thesis for approval on 2022-07-14 at 17:08.","This Thesis was approved for publication on 2022-07-19 at 13:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18320 on 2022-11-15 at 21:40:27","Transportation Problem (TP) is a popular mathematical model for optimally matching several supply centers to several demand centers at the smallest transportation cost. Recent disruptions in the physical supply chains and the growth of internet marketplaces such as ride-sharing, doorstep delivery, and expedited shipping have engendered a need for efficient algorithms to solve fundamental TP in near real-time. The traditional ways to solve TP are unsuitable for some of these systems because their run-time causes latency issues. The evolution of accelerated computing using Graphics Processing Units (GPUs) has recently attracted some interest in solving optimization problems. In this research, an attempt has been made to solve TP in an accelerated way using a GPU. The Transportation Simplex Algorithm (TSA) is one of the efficient ways to solve the TP. A detailed study has been conducted to expose the underlying parallelism in the iterative steps of TSA. The parallel design proposed improves runtime through simultaneously executing multiple independent iterations. The results show that the accelerated algorithm performs up to 5 times faster on an average compared to the known sequential algorithm and up to 3 times faster on an average compared to the state-of-the-art commercial Linear Programming solver."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/116108"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Mohit Mahajan"],"dc:subject":["Parallel Algorithms","Transportation Problem","Operations Research","Simplex","GPU","CUDA"],"dc:title":["GPU accelerated transportation simplex algorithm"],"dc:type":["text","Thesis"],"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:55Z"}