The simplex method of linear programming using LU decomposition

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The simplex method of linear programming using LU decomposition

Full text

Pdf (409 KB)

Source

Communications of the ACM archive
Volume 12 , Issue 5 (May 1969) table of contents

Pages: 266 - 268

Year of Publication: 1969

ISSN:0001-0782

Authors

Richard H. Bartels	Stanford Univ., CA
Gene H. Golub	Stanford Univ., CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 38, Downloads (12 Months): 170, Citation Count: 8

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/362946.362974 What is a DOI?

ABSTRACT

Standard computer implementations of Dantzig's simplex method for linear programming are based upon forming the inverse of the basic matrix and updating the inverse after every step of the method. These implementations have bad round-off error properties. This paper gives the theoretical background for an implementation which is based upon the LU decomposition, computed with row interchanges, of the basic matrix. The implementation is slow, but has good round-off error behavior. The implementation appears as CACM Algorithm 350.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Richard H. Bartels , Gene H. Golub, Numerical Analysis: Stable numerical methods for obtaining the Chebyshev solution to an overdetermined system of equations, Communications of the ACM, v.11 n.6, p.401-406, June 1968 [doi>10.1145/363347.363364]
	2	DANTZIG, G.B. Linear Programming and Extensions. Princeton U. Press, Princeton, N.J., 1963.
	3	HADLEY, G. Linear Programming. Addison-Wesley, Reading, Mass., 1962.
	4	James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994
	5	BARTELS, RICHARD H. A numerical investigation of the simplex method. Tech. Rep. No. CS 104, Comput. Sci. Dep., Stanford U., Stanford, Calif., July 1968.

CITED BY 8

	Michael D. Chang , Chou-Hong J. Chen , Michael Engquist, An improved primal simplex variant for pure processing networks, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.64-78, March 1989
	R. D. Armstrong , D. S. Kung, A dual method for discrete Chebychev curve fitting, Proceedings of the 1978 annual conference, p.946-953, January 1978
	William Welch , Andrew Witkin, Variational surface modeling, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.157-166, July 1992
	William W. White, A Status Report on Computing Algorithms for Mathematical Programming, ACM Computing Surveys (CSUR), v.5 n.3, p.135-166, Sept. 1973
	Kazutaka Murakami , Hyong S. Kim, Optimal capacity and flow assignment for self-healing ATM networks based on line and end-to-end restoration, IEEE/ACM Transactions on Networking (TON), v.6 n.2, p.207-221, April 1998
	Woo-Je Kim , Sungmook Lim , Seung-yong Doh , Soondal Park , Jaegeun Ahn, Numerical aspects in developing LP softwares, LPAKO and LPABO, Journal of Computational and Applied Mathematics, v.152 n.1-2, p.217-228, 1 March 2003
	Artur świętanowski, A New Steepest Edge Approximation for the Simplex Methodfor Linear Programming, Computational Optimization and Applications, v.10 n.3, p.271-281, July 1998
	Austin Parker , V. S. Subrahmanian , John Grant, A Logical Formulation of Probabilistic Spatial Databases, IEEE Transactions on Knowledge and Data Engineering, v.19 n.11, p.1541-1556, November 2007