A Forward Simplex Method for Staircase Linear Programs

Jay E. Aronson, Thomas E. Morton and Gerald L. Thompson
Additional contact information
Jay E. Aronson: School of Engineering and Applied Science, Southern Methodist University, Dallas, Texas 75275
Thomas E. Morton: Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213
Gerald L. Thompson: Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213

Management Science, 1985, vol. 31, issue 6, 664-679

Abstract: Modelling planning problems that extend over many time periods as linear programs leads to a special structure called a "staircase" or "dynamic" linear program. In this special structure, the nonzero coefficients of the linear program appear in blocks along the "main diagonal" of the coefficient matrix. Such problems are commonly found in economic planning, structural design, agricultural planning, dynamic traffic assignment, production planning, and scheduling models. Forward algorithms provide an approach to solving these dynamic problems by solving successively longer finite horizon subproblems, terminating when a stopping rule can be invoked (or a decision horizon found). Such algorithms are available for a large number of specific models. Here we discuss the implementation and testing of a forward algorithm for solving general dynamic (staircase) linear programs. Tests reported indicate that the solution time is linear in the number of periods of the staircase problem, as compared to a quadratic or cubic relationship for standard linear programming codes. Computational decision horizons are often found, and are responsible for the good performance of the algorithm.

Keywords: programming: linear; algorithms; programming: large scale systems; staircase linear programs; forward method (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.31.6.664 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:31:y:1985:i:6:p:664-679

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().