Efficient GPU-based implementations of simplex type algorithms
作者：
Highlights：
• 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.
摘要
•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.
论文关键词：Linear Programming,Simplex type algorithms,Graphical Processing Unit,Parallel Computing,MATLAB
论文评审过程：Available online 22 November 2014.
论文官网地址：https://doi.org/10.1016/j.amc.2014.10.096
