The aim of this paper is to present a new simplex-type algorithm for the Linear Programming Problem. The Primal-Dual method is a Simplex-type pivoting algorithm that generates two paths in order to converge to the optimal solution. | Yugoslav Journal of Operations Research Vol 19 (2009), Number 1, 123-132 DOI: A PRIMAL-DUAL EXTERIOR POINT ALGORITHM FOR LINEAR PROGRAMMING PROBLEMS Nikolaos SAMARAS Angelo SIFELARAS Charalampos TRIANTAFYLLIDIS Department of Applied Informatics, University of Macedonia Greece, Thessaloniki samaras,sifalera,mai0629@ Received: December 2007 / Accepted: June 2009 Abstract: The aim of this paper is to present a new simplex type algorithm for the Linear Programming Problem. The Primal - Dual method is a Simplex - type pivoting algorithm that generates two paths in order to converge to the optimal solution. The first path is primal feasible while the second one is dual feasible for the original problem. Specifically, we use a three-phase-implementation. The first two phases construct the required primal and dual feasible solutions, using the Primal Simplex algorithm. Finally, in the third phase the Primal - Dual algorithm is applied. Moreover, a computational study has been carried out, using randomly generated sparse optimal linear problems, to compare its computational efficiency with the Primal Simplex algorithm and also with MATLAB’s Interior Point Method implementation. The algorithm appears to be very promising since it clearly shows its superiority to the Primal Simplex algorithm as well as its robustness over the IPM algorithm. Keywords: Linear optimization, simplex-type algorithms, primal-dual exterior point algorithm, computational study. 1. INTRODUCTION Linear Programming (LP) is perhaps the most important and best-studied optimization problem. A lot of real world problems can be formulated as linear problems [1], [2] and [4]. The simplex algorithm developed by Dantzig, starts with a primal 124 N. Samaras, A. Sifaleras, C. Triantafyllidis / A Primal Dual Exterior Point feasible basis and uses pivot operations in order to preserve the feasibility of the basis and guarantee monotonicity of the objective value. Many pivot rules .
