A Comparison Among Simple Algorithms for Linear Programming

Authors

  • Jair Silva Federal University of Paraná
  • Carla T. L. S. Ghidini School of Applied Sciences, University of Campinas
  • Aurelio R. L. Oliveira Institute of Mathematics, Statistics and Scientific Computing, University of Campinas
  • Marta I. V. Fontova Faculty of Campo Limpo Paulista

DOI:

https://doi.org/10.5540/tema.2018.019.02.305

Keywords:

Linear programming, von Neumann's algorithm, Simple algorithms.

Abstract

This paper presents a comparison between a family of simple algorithms for linear programming and the optimal pair adjustment algorithm. The optimal pair adjustment algorithm improvements the convergence of von Neumann's algorithm which is very attractive because of its simplicity. However, it is not practical to solve linear programming problems to optimality, since its convergence is slow. The family of simple algorithms results from the generalization of the optimal pair adjustment algorithm, including a parameter on the number of chosen columns instead of just a pair of them. Such generalization preserves the simple algorithms nice features. Significant improvements over the optimal pair adjustment algorithm were demonstrated through numerical experiments on a set of linear programming problems.

Downloads

Additional Files

Published

2018-09-12

How to Cite

Silva, J., Ghidini, C. T. L. S., Oliveira, A. R. L., & Fontova, M. I. V. (2018). A Comparison Among Simple Algorithms for Linear Programming. Trends in Computational and Applied Mathematics, 19(2), 305. https://doi.org/10.5540/tema.2018.019.02.305

Issue

Vol. 19 No. 2 (2018)

Section

Original Article

License

Copyright

Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.

Intellectual Property and Terms of Use

The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.

The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.