Revised simplex algorithm for linear programming on GPUs with CUDA

摘要

The revised simplex algorithm (RSA) is a typical algorithm for solving linear programming problems. Many theoretical modifications have been done to make the algorithm more efficient, but almost all of them were based on single-instruction single-data architecture processors (CPUs), which could not make full use of the inherent parallel characteristics of RSAs. We propose a novel single-instruction multiple-data architecture processor (GPU) based on the RSA in this paper. The intensive matrix manipulations of a traditional RSA are offloaded to the GPU, which helps to make full use of its powerful parallel processing ability. We implemented the GPU-based RSA on compute unified device architecture (CUDA). Numerical experiments on randomly generated linear programs show that the GPU-based RSA can not only find the correct optimal solutions, but can also reach a speed of up to 100 times as fast as that of a CPU-based RSA: it also runs 3 to 11 times as fast as MATLAB.