A Comparison Among Simple Algorithms for Linear Programming

Autores

  • Jair Silva UFPR
  • 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

Palavras-chave:

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

Resumo

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

Arquivos adicionais

Publicado

2018-09-12

Como Citar

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

Edição

v. 19 n. 2 (2018)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.