This Small Business Innovation Research (SBIR) Phase I project will investigate the feasibility of developing a practical parallel implementation of the simplex algorithm for linear programming. As the demand to solve larger and more complex decision-making problems in all sectors of the economy increases, so does the demand for a parallel simplex algorithm for on-line and time-critical operations. Yet, parallel versions of this algorithm are currently unable to outperform appropriate serial codes for industrially-relevant problems that involve sparse large-scale matrices. The proposed research will explore a finer-grain parallelization than previously attempted for the simplex algorithm. As a result, the proposed implementation of the simplex algorithm will harness recent advances in graphics processing units (GPUs), while being capable of benefiting from any future serial algorithmic advances in the context of this algorithm. In addition to callable libraries and stand-alone executables, the implementation will be offered through cloud-enabled commercial services.
The parallelization of the simplex algorithm has remained a major challenge in scientific computing. The proposed research will involve a systematic investigation of different combinations of factorization and pricing algorithms with regard to their performance on modern GPUs. If successful, the proposed work will result in an enabling technology for decision making in diverse areas across science and engineering and commerce. Linear programming is used extensively in applications ranging from data mining to airline scheduling, cancer therapy, engineering design, financial decision making, and logistics. As a result, the proposed work presents an unique opportunity to improve the competitiveness of the nation's commercial infrastructure.
The primary objective of this SBIR Phase I project was to investigate the possibility of capitalizing on Graphics Processing Units for the development of a practical parallel implementation for the simplex algorithm for sparse linear programming. Research on the parallelization of the simplex algorithm was first and most actively considered in the 1990s, when it was concluded that the available hardware was unable to provide the desired performance requirements for sparse large-scale problems. The parallelization of this algorithm has remained a major challenge in scientific computing to this date. The project involved a systematic investigation of different algorithmic steps of this algorithm with regard to their performance on modern Graphics Processing Units. The results from this project suggest that the development of a hybrid GPU-CPU implementation of the simplex algorithm for sparse linear programming is likely to yield a considerable improvement in performance relative to current CPU implementations of this algorithm. The simplex algorithm for linear programming is the workhorse of algorithms that are used extensively in applications ranging from data mining to airline scheduling, cancer therapy, engineering design, financial decision making, and logistics. The results of this project suggest an avenue for improving the competitiveness of the nation's commercial infrastructure.
