A Forward Simplex Method for Staircase Linear Programs

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.