A primal-dual exterior point algorithm for linear programming problems

Authors

  • Nikolaos Samaras Department of Applied Informatics, University of Macedonia Greece, Thessaloniki, Greece
  • Angelo Sifelaras Department of Applied Informatics, University of Macedonia Greece, Thessaloniki, Greece
  • Charalampos Triantafyllidis Department of Applied Informatics, University of Macedonia Greece, Thessaloniki, Greece

DOI:

https://doi.org/10.2298/YJOR0901123S

Keywords:

Linear optimization, simplex-type algorithms, primal-dual exterior point algorithm, computational study

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.

References

Bazaraa, M.S., Jarvis, J.J., and Sherali H.D., Linear Programming and Network Flows, 3rd ed., John Wiley & Sons, 2005.

Bertsimas, D., and Tsitsiklis, J.N., Introduction to Linear Optimization, Athena Scientific, 1997.

Bland, G.R., “New finite pivoting rules for the Simplex method”, Mathematics of Operations Research, 2 (1977) 103-107.

Dantzig, G.B., Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.

Erling, D., Andersen, and Yinyu, Ye, “Combining interior-point and pivoting algorithms for Linear Programming”, Management Science, 42 (12) (1996) 1719-1731.

Gondzio, J., “Multiple centrality corrections in a primal-dual method for linear programming”, Computational Optimization and Applications, 6 (2) (1996) 137-156.

Paparrizos, K., Samaras, N., and Stephanides, G., “A new efficient primal dual simplex algorithm”, Computers and Operations Research, 30 (2003) 1383-1399.

Paparrizos, K., “Pivoting algorithms generating two paths”, presented in ISMP ’97, Lausanne, EPFL Switzerland, 1997.

Samaras, N., “Computational improvements and efficient implementation of two path pivoting algorithms”, PhD Thesis, Department of Applied Informatics, University of Macedonia, 2001.

Triantafyllidis, Ch., “Comparative computational study on Exterior Point Algorithms”, BSc Thesis, Department of Applied Informatics, University of Macedonia, 2005.

Downloads

Published

2009-03-01

Issue

Vol. 19 No. 1 (2009)

Section

Research Articles

License

Copyright (c) 2009 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.