A new efficient primal dual simplex algorithm

A new efficient primal dual simplex algorithm

0.00 Avg rating0 Votes
Article ID: iaor20042314
Country: United Kingdom
Volume: 30
Issue: 9
Start Page Number: 1383
End Page Number: 1399
Publication Date: Aug 2003
Journal: Computers and Operations Research
Authors: , , ,
Keywords: duality
Abstract:

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 and 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 on randomly generated problems of size 1200 × 1200 and density 2.5%.

Reviews

Required fields are marked *. Your email address will not be published.