A Bidirectional Simplex Algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Bidirectional Simplex Algorithm

Full text

Pdf (749 KB)

Source

Journal of the ACM (JACM) archive
Volume 15 , Issue 2 (April 1968) table of contents

Pages: 221 - 235

Year of Publication: 1968

ISSN:0004-5411

Authors

A. Orden	Institute for Computer Research, University of Chicago, Chicago, Illinois
V. Nalbandian	Esso Mathematics and Systems, Inc., Florham Park, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 26, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/321450.321455 What is a DOI?

ABSTRACT

A simplex type algorithm is presented which deals uniformly with (a) ordinary linear programming problems, (b) problems with upper bounded variables, and (c) problems with convex piecewise linear objective functions, e.g., absolute value terms. Problems of types (b) and (c) can be solved by suitable transformations into ordinary linear programming forms, but are handled by the unified algorithm without such transformations. Comparative computer runs indicate that direct solution by the unified algorithm is considerably more efficient than conversion into ordinary linear programming form followed by use of a regular simplex routine. Computer tests also show that the algorithm offers a worthwhile alternative to the use of artificial variables as a starting procedure for ordinary linear programming problems.

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	DANTZlG, G. B. Linear Programming and Extensions. Princeton U. Press, Princeton, N. J., 1963, pp. 370-376, 482-486.
	2	GOLDSTEIN, E .G . A certain class of nonlinear extremum problems. Soviet Math.--Translalions of Dokl. Akad. Nauk SSSR 1, 4 (1960), 863-866.
	3	CLASEN, R. Linear programming routine ISMFOR. SHARE Distribution Agency, No. 1379, 1962.
	4	SMITH, D. M., AND HAYS, W.O. Computational efficiency in product form LI codes. In Graves, R. L., and Wolfe, P. (Eds.), Recent Advances in Mathematical Programming, Me- Graw-Hill, New York, 1963, pp. 211-218.
	5	MILLER, C .E . The simplex method for loctd separable programming. In Graves, It. L., and Wolfe, P. (Eds.), Recent Advances inn Mathematical Programming. McGraw-Hill, New York, 1963, pp. 89-102.