Abstract
This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or ‘staircase’, structure. The present paper looks at ‘inversion’ routines within the simplex method, particularly those for sparse triangular factorization of a basis by Gaussian elimination and for solution of triangular linear systems. The succeeding paper examines ‘pricing’ routines. Both papers describe extensive (though preliminary) computational experience, and can point to some quite promising results.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
T. Aonuma, “A two-level algorithm for two-stage linear programs”,Journal of the Operations Research Society of Japan 21 (1978) 171–187.
R.H. Bartels, “A stabilization of the simplex method”,Numerische Mathematik 16 (1971) 414–434.
R.H. Bartels and G.H. Golub, “The simplex method of linear programming usingLU decomposition”,Communications of the ACM 12 (1969) 266–268.
M. Benichou et al., “The efficient solution of large-scale linear programming problems—Some algorithmic techniques and computational results”,Mathematical Programming 13 (1977) 280–322.
J. Bisschop and A. Meeraus, “Matrix augmentation and structure preservation in linearly constrained control problems”,Mathematical Programming 18 (1980) 7–15.
R.H. Cobb and J. Cord, “Decomposition approaches for solving linked problems”, in: H.W. Kuhn, ed.,Proceedings of the Princeton symposium on mathematical programming (Princeton University Press, Princeton, NJ, 1970) pp. 37–49.
G.B. Dantzig, “Programming of interdependent activities, II: mathematical model”,Econometrica 17 (1949) 200–211.
G.B. Dantzig, “Upper bounds, secondary constraints and block triangularity in linear programming”,Econometrica 23 (1955) 174–183.
G.B. Dantzig, “Optimal solution of a dynamic Leontief model with substitution”,Econometrica 23 (1955) 295–302.
G.B. Dantzig, “Compact basis triangularization for the simplex method”, in: R.L. Graves and P. Wolfe, eds.,Recent advances in mathematical programming (McGraw-Hill, New York, 1963) pp. 125–132.
G.B. Dantzig, “Solving staircase linear programs by a nested block-angular method”, Technical Report 73-1, Department of Operations Research, Stanford University, Stanford, CA (1973).
G.B. Dantzig and P. Wolfe, “Decomposition principle for linear programs”,Operations Research 8 (1960) 101–111.
I.S. Duff, “On the number of nonzeroes added when Gaussian elimination is performed on sparse random matrices”,Mathematics of Computation 28 (1974) 219–230.
I.S. Duff, “Practical comparisons of codes for the solution of sparse linear systems”, in: I.S. Duff and G.W. Stewart, eds.,Sparse matrix proceedings 1978 (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1979) pp. 107–134.
I.S. Duff and J.K. Reid, “A comparison of sparsity orderings for obtaining a pivotal sequence in Gaussian elimination”,Journal of the Institute of Mathematics and its Applications 14 (1974) 281–291.
J.J.H. Forrest and J.A. Tomlin, “Updated triangular factors of the basis to maintain sparsity in the product form simplex method”,Mathematical Programming 2 (1972) 263–278.
R. Fourer, “Sparse Gaussian elimination of staircase linear systems”, Technical Report SOL 79-17, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA (1979).
R. Fourer, “Solving staircase linear programs by the simplex method, 1: inversion”, Technical Report SOL 79-18, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA (1979); reprinted in: G.B. Dantzig, M.A.H. Dempster and M.J. Kallio eds.,Large-scale linear programming 1 (International Institute for Applied Systems Analysis, Laxenburg, 1981) pp. 179–259.
R. Fourer, “Staircase matrices”, Technical Report, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1980).
R. Fourer, “Solving staircase linear programs by the simplex method, 2: pricing”,Mathematical Programming 24 (1982) to appear.
D.M. Gay, “On combining the schemes of Reid and Saunders for sparse LP bases”, in: I.S. Duff and G.W. Stewart, eds.,Sparse matrix proceedings 1978 (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1979) pp. 313–334.
C.W. Gear et al., “Numerical computation: its nature and research directions”,SIGNUM Newsletter (Association for Computing Machinery, New York, 1979).
C.R. Glassey, “Dynamic linear programs for production scheduling”,Operations Research 19 (1971) 45–56.
C.R. Glassey, “Nested decomposition and multi-stage linear programs”,Management Science 20 (1973) 282–292.
D. Goldfarb, “On the Bartels—Golub decomposition for linear programming bases”,Mathematical Programming 13 (1977) 292–292.
R.C. Grinold, “Steepest ascent for large-scale linear programs”,SIAM Review 14 (1972) 447–464.
A.R.G. Heesterman and J. Sandee, “Special simplex algorithm for linked problems”,Management Science 11 (1965) 420–428.
E. Hellerman and D. Rarick, “Reinversion with the preassigned pivot procedure”,Mathematical Programming 1 (1971) 195–216.
E. Hellerman and D.C. Rarick, “The partitioned preassigned pivot procedure (P4)”, in: D.J. Rose and R.A. Willoughby, eds.,Sparse matrices and their applications (Plenum Press, New York, 1972) pp. 67–76.
J.K. Ho, “Optimal design of multi-stage structures: a nested decomposition approach”,Computers and Structures 5 (1975) 249–255.
J.K. Ho, “Nested decomposition of a dynamic energy model”,Management Science 23 (1977) 1022–1026.
J.K. Ho, “A successive linear optimization approach to the dynamic traffic assignment problem”,Transportation Science 14 (1980) 295–305.
J.K. Ho and E. Loute, “A comparative study of two methods for staircase linear programs”,ACM Transactions on Mathematical Software 6 (1980) 17–30.
J.K. Ho and E. Loute, “A set of staircase linear programming test problems”,Mathematical Programming 20 (1981) 245–250.
J.K. Ho and A.S. Manne, “Nested decomposition for dynamic models”,Mathematical Programming 6 (1974) 121–140.
“IBM OS FORTRAN IV (H extended) compiler programmer's guide”, No. SC28-6852, International Business Machines Corporation (New York, 1974).
R. Johnson and T. Johnston, “PROGLOOK user's guide”, User Note 33, SLAC Computing Services, Stanford Linear Accelerator Center, Stanford, CA (1976).
O.B.G. Madsen, “Solution of LP-problems with staircase structure”, Research Report 26, The Institute of Mathematical Statistics, Lyngby (1977).
A.S. Manne, “U.S. options for a transition from oil and gas to synthetic fuels”, Discussion Paper 26D, Public Policy Program, Kennedy School of Government, Harvard University, Cambridge, MA (1975).
H.M. Markowitz, “The elimination form of the inverse and its application to linear programming”,Management Science 3 (1957) 255–269.
R.E. Marsten and F. Shepardson, “A double basis simplex method for linear programs with complicating variables”, Technical Report 531, Department of Management Information Systems, University of Arizona, Tucson, AZ (1978).
D.K. Merchant and G.L. Nemhauser, “A model and an algorithm for the dynamic traffic assignment problems”,Transportation Science 12 (1978) 183–199.
“MPS III mathematical programming system: user manual”, Ketron Inc., Arlington, VA (1975).
B.A. Murtagh and M.A. Saunders, “MINOS: a large-scale nonlinear programming system (for problems with linear constraints): user's guide”, Technical Report SOL 77-9, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA (1977).
W. Orchard-Hays,Advanced linear-programming computing techniques (McGraw-Hill, New York, 1968).
S.C. Parikh, “A welfare equilibrium model (WEM) of energy supply, energy demand, and economic growth”, Technical Report SOL 79-3, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA (1979).
A.F. Perold, “Fundamentals of a continuous time simplex method”, Technical Report SOL 78-26, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA (1978).
A.F. Perold and G.B. Dantzig, “A basis factorization method for block triangular linear programs”, in: I.S. Duff and G.W. Stewart, eds.,Sparse matrix proceedings 1978 (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1979) pp. 283–312.
A. Propoi and V. Krivonozhko, “The simplex method for dynamic linear programs”, Report RR-78-14, International Institute for Applied Systems Analysis, Laxenburg (1978).
J.K. Reid, “A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases”, Report CSS 20, Computer Science and Systems Division, A.E.R.E., Harwell (1975).
J.K. Reid, “Fortran subroutines for handling sparse linear programming bases”, Report AERE-R8269, Computer Science and Systems Division, A.E.R.E., Harwell (1976).
R. Saigal, “Block-triangularization of multi-stage linear programs”, Report ORC 66-9, Operations Research Center, University of California, Berkeley, CA (1966).
M.A. Saunders, “The complexity ofLU updating in the simplex method”, in: R.S. Anderssen and R.P. Brent, eds.,The complexity of computational problem solving (Queensland University Press, Brisbane, Qld., 1975) pp. 214–230.
M.A. Saunders, “A fast, stable implementation of the simplex method using Bartels—Golub updating”, in: J.R. Bunch and D.J. Rose, eds.,Sparse matrix computations (Academic Press, New York, 1976) pp. 213–226.
M.A. Saunders, “MINOS system manual”, Technical Report SOL 77-31, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA (1977).
W. Swart, C. Smith and T. Holderby, “Expansion planning for a large dairy farm”, in: H.M. Salkin and J. Saha, eds.,Studies in linear programming (American Elsevier, New York, 1975) pp. 163–182.
I. Vinson, “Triplex user's guide”, User Note 99, SLAC Computing Services, Stanford Linear Accelerator Center, Stanford, CA (1978).
R.D. Wollmer, “A substitute inverse for the basis of a staircase structure linear program”,Mathematics of Operations Research 2 (1977) 230–239.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Fourer, R. Solving staircase linear programs by the simplex method, 1: Inversion. Mathematical Programming 23, 274–313 (1982). https://doi.org/10.1007/BF01583795
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01583795