GPU accelerated transportation simplex algorithm

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Mahajan, Mohit

Contributors dc:contributor

• Nagi, Rakesh

• Parallel Algorithms
• Transportation Problem
• Operations Research
• Simplex
• GPU
• CUDA

Statement dc:rights

• Copyright 2022 Mohit Mahajan

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/116108

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F116108