Open AccessA Comparison Among Simple Algorithms for Linear Programming
Author(s) -
Jair A. L. Silva,
Carla T. L. S. Ghidini,
Aurélio Ribeiro Leite de Oliveira,
Marta Ines Velazco Fontova
Publication year - 2018
Publication title -
tema
Language(s) - English
Resource type - Journals
eISSN - 2179-8451
pISSN - 1677-1966
DOI - 10.5540/tema.2018.019.02.305
Subject(s) - simple (philosophy) , generalization , algorithm , linear programming , convergence (economics) , mathematics , simple algorithm , mathematical optimization , set (abstract data type) , criss cross algorithm , linear fractional programming , computer science , mathematical analysis , philosophy , physics , epistemology , economics , thermodynamics , programming language , economic growth
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.