Abstract
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.
Similar content being viewed by others
References
He, B.,A Saddle-Point Algorithm for Linear Programming, Nanjing Daxue Xuebao, Shuxue Banniankan, Vol. 6, pp. 41–48, 1989.
He, B.,A Projection and Contraction Method for a Class of Linear Complementarity Problems and Its Application in Convex Quadratic Programming, Applied Mathematics and Optimization, Vol. 25, pp. 247–262, 1992.
Mangasarian, O. L.,Solution of Symmetric Linear Complementarity Problems by Iterative Methods, Journal of Optimization Theory and Applications, Vol. 22, pp. 465–485, 1979.
Dantzig, G. B.,Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1963.
Blum, E., andOettli, W.,Mathematische Optimierung, Springer-Verlag, Berlin, Germany, 1975.
Uzawa, H.,Iterative Methods for Concave Programming, Studies in Linear and Nonlinear Programming, Edited by K. J. Arrow et. al., Stanford University Press, Stanford, California, pp. 154–165, 1958.
He, B., andStoer, J.,Solution of Projection Problems over Polytopes, Numerische Mathematik, Vol. 61, pp. 73–90, 1992.
Korpelevich, G. M.,The Extragradient Method for Finding Saddle Points and Other Problems, Ekonomika i Matematicheskie Metody, Vol. 22, pp. 747–756, 1976.
Author information
Authors and Affiliations
Additional information
Communicated by R. Bulirsch
This research was done while the author was visiting the Department of Mathematics at the University of Würzburg, Würzburg, Germany.
Rights and permissions
About this article
Cite this article
He, B.S. On a class of iterative projection and contraction methods for linear programming. J Optim Theory Appl 78, 247–266 (1993). https://doi.org/10.1007/BF00939669
Issue Date:
DOI: https://doi.org/10.1007/BF00939669