Geodesic
A Primal-Dual Exterior Point Algorithm for Linear Programming Problems
Yugoslav journal of operations research, Tome 19 (2009) no. 1, p. 123 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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.
Classification : 90C05
Keywords: Linear optimization, simplex-type algorithms, primal-dual exterior point algorithm, computational study. 
@article{YJOR_2009_19_1_a8,
     author = {Nikolaos Samaras and Angelo Sifaleras and Charalampos Triantafyllidis},
     title = {A {Primal-Dual} {Exterior} {Point} {Algorithm} for {Linear} {Programming} {Problems}},
     journal = {Yugoslav journal of operations research},
     pages = {123 },
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2009},
     zbl = {1274.90223},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2009_19_1_a8/}
}
TY  - JOUR
AU  - Nikolaos Samaras
AU  - Angelo Sifaleras
AU  - Charalampos Triantafyllidis
TI  - A Primal-Dual Exterior Point Algorithm for Linear Programming Problems
JO  - Yugoslav journal of operations research
PY  - 2009
SP  - 123 
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2009_19_1_a8/
LA  - en
ID  - YJOR_2009_19_1_a8
ER  - 
%0 Journal Article
%A Nikolaos Samaras
%A Angelo Sifaleras
%A Charalampos Triantafyllidis
%T A Primal-Dual Exterior Point Algorithm for Linear Programming Problems
%J Yugoslav journal of operations research
%D 2009
%P 123 
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2009_19_1_a8/
%G en
%F YJOR_2009_19_1_a8
Nikolaos Samaras; Angelo Sifaleras; Charalampos Triantafyllidis. A Primal-Dual Exterior Point Algorithm for Linear Programming Problems. Yugoslav journal of operations research, Tome 19 (2009) no. 1, p. 123 . http://geodesic.mathdoc.fr/item/YJOR_2009_19_1_a8/