IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v31y1985i6p664-679.html
   My bibliography  Save this article

A Forward Simplex Method for Staircase Linear Programs

Author

Listed:
  • 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)

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.

Suggested Citation

  • Jay E. Aronson & Thomas E. Morton & Gerald L. Thompson, 1985. "A Forward Simplex Method for Staircase Linear Programs," Management Science, INFORMS, vol. 31(6), pages 664-679, June.
    • Handle: RePEc:inm:ormnsc:v:31:y:1985:i:6:p:664-679
    DOI: 10.1287/mnsc.31.6.664
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.31.6.664
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.31.6.664?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jonathan D. Stanley & Awanti P. Sethi, 1990. "Solving production smoothing problems with a nonlinear candidate constraint method," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(4), pages 579-586, August.
    2. Suresh Chand & Vernon Ning Hsu & Suresh Sethi, 2002. "Forecast, Solution, and Rolling Horizons in Operations Management Problems: A Classified Bibliography," Manufacturing & Service Operations Management, INFORMS, vol. 4(1), pages 25-43, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:31:y:1985:i:6:p:664-679. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.