Efficient GPU-based implementations of simplex type algorithms

• We propose two efficient GPU-based implementations of simplex type algorithms.
• We computationally compare our GPU-based implementations with MATLAB’s solver.
• A maximum speedup of 181 is reported for the Exterior Point Simplex Algorithm on randomly generated LPs.
• A maximum speedup of 58 is reported for the Revised Simplex Algorithm on randomly generated LPs.
• An average speedup of 2.30 is reported for the primal–dual exterior point algorithm on benchmark LPs.

Recent hardware advances have made it possible to solve large scale Linear Programming problems in a short amount of time. Graphical Processing Units (GPUs) have gained a lot of popularity and have been applied to linear programming algorithms. In this paper, we propose two efficient GPU-based implementations of the Revised Simplex Algorithm and a Primal–Dual Exterior Point Simplex Algorithm. Both parallel algorithms have been implemented in MATLAB using MATLAB’s Parallel Computing Toolbox. Computational results on randomly generated optimal sparse and dense linear programming problems and on a set of benchmark problems (netlib, kennington, Mészáros) are also presented. The results show that the proposed GPU implementations outperform MATLAB’s interior point method.