A Family of Linear Programming Algorithms Based on an Algorithm by von Neumann

In this paper, we present a family of algorithms for linear programming based on an algorithm proposed by von Neumann. The von Neumann algorithm is very attractive due to its simplicity but is not practical for solving most linear programs to optimality due to its slow convergence. Our algorithms were developed with the objective of improving the practical convergence of the von Neumann algorithm while maintaining its attractive features. We present results from computational experiments on a set of linear programming problems that show significant improvements over the von Neumann algorithm.

By: João P. M. Gonçalves; Robert H. Storer; Jacek Gondzio

Published in: Optimization Methods and Software, volume 24, (no 3), pages 461-478 in 2009

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .