A new efficient primal dual simplex algorithm

摘要

The purpose of this paper is to present a revised primal dual simplex algorithm (RPDSA) for linear programming problems. RPDSA has interesting theoretical properties. The advantages of the new algorithm are the simplicity of implementation, low computational overhead and surprisingly good computational performance. The algorithm can be combined with interior point methods to move from an interior point to a basic optimal solution. The new algorithm always proved to be more efficient than the classical simplex algorithm on our test problems. Numerical experiments on randomly generated sparse linear problems are presented to verify the practical value of RPDSA. The results are very promising. In particular, they reveal that RPDSA is up to 146 times faster in terms of number of iterations and 94 times faster in terms of CPU time than the original simplex algorithm (SA) on randomly generated problems of size 1200 x 1200 and density 2.5%.