GPU-accelerated transportation simplex algorithm

Mohit Mahajan, Rakesh Nagi

Research output: Contribution to journalArticlepeer-review

Abstract

Transportation Problem (TP) is a popular linear program 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 large-scale TPs in near real-time. The Transportation Simplex Algorithm (TSA) is a traditional method to solve TP to optimality. However, TSA is unsuitable for these new applications because of its long run time. The evolution of accelerated computing using Graphics Processing Units (GPUs) has recently attracted some interest in solving optimization problems. In this paper, we develop a GPU-accelerated TSA for large-dimensions. The underlying parallelism in the iterative steps of TSA has been uncovered and exploited. The results show that the accelerated algorithm performs up to 8 times faster on average compared to the known sequential algorithm and up to 4 times faster on average compared to the state-of-the-art commercial Linear Programming solver.

Original languageEnglish (US)
Article number104790
JournalJournal of Parallel and Distributed Computing
Volume184
DOIs
StatePublished - Feb 2024

Keywords

  • GPU accelerated algorithm
  • Linear programming
  • Transportation problem

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'GPU-accelerated transportation simplex algorithm'. Together they form a unique fingerprint.

Cite this