This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/116108
Description
Title
GPU accelerated transportation simplex algorithm
Author(s)
Mahajan, Mohit
Issue Date
2022-07-19
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)
Parallel Algorithms, Transportation Problem, Operations Research, Simplex, GPU, CUDA
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.