A Nested-Decomposition Approach for Solving Staircase-Structured Linear Programs

摘要

The algorithm solves a T-period staircase-structured linear program by applying a compact basis-inverse scheme for the Simplex Method in conjunction with a choice mechanism which uses the dual of the Nested Decomposition Principle of Manne and Ho to determine the incoming basic column. A sequence of one-period problems is solved in which, typically, information is provided to period t from previous and subsequent periods in the form of surrogate columns and modified right-hand side, and surrogate rows and modified cost coefficients, respectively. (Author)