Please use this identifier to cite or link to this item:
Title: A primal-dual exterior point algorithm for linear programming problems
Authors: Samaras, Nikolaos
Sifaleras, Angelo
Triantafyllidis, Charalampos P.
Type: Article
Subjects: FRASCATI::Natural sciences::Mathematics::Applied Mathematics
FRASCATI::Natural sciences::Computer and information sciences
Keywords: Linear optimization
Simplex-type algorithms
Primal-dual exterior point algorithm
Computational study
Issue Date: 2009
Source: Yugoslav Journal of Operations Research
Volume: 19
Issue: 1
First Page: 123
Last Page: 132
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.
ISSN: 0354-0243
Other Identifiers: 10.2298/YJOR0901123S
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
A_primal_-_dual_exterior_point_algorithm_for_linear_programming_problems.pdf354,43 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.