GPU accelerated transportation simplex algorithm

Mahajan, Mohit

Permalink

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

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.

Graduation Semester

2022-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2022 Mohit Mahajan

Owning Collections