GPU-accelerated transportation simplex algorithm

doi:10.1016/j.jpdc.2023.104790

GPU-accelerated transportation simplex algorithm

2024-02-01

0

PRE

AI

DOI：10.1016/j.jpdc.2023.104790

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

GPU accelerated algorithm

Linear programming

Transportation problem

GPU-accelerated transportation simplex algorithm

Abstract

Journal

Organization

Cited Papers