On a class of iterative projection and contraction methods for linear programming

In this paper, based on the idea of a projection and contraction method for a class of linear complementarity problems (Refs. 1 and 2), we develop a class of iterative algorithms for linear programming with linear speed of convergence. The algorithms are used to solve transportation and network problems with up to 10,000 variables. Our experiments indicate that the algorithms are simple, easy to parallelize, and more efficient for some large practical problems.This research was done while the author was visiting the Department of Mathematics at the University of Würzburg, Würzburg, Germany.