 Nested Decomposition and Multi-Stage Linear ProgramsC. Roger Glassey
Management Science, 1973, vol. 20, issue 3, 282-292 Abstract: A multi-stage linear program is defined with linking variables that connect consecutive stages. Optimality conditions for the composite problem are partitioned into local and linking conditions. When the Dantzig-Wolfe decomposition scheme is applied with the first stage as the master, the subproblem is also a MLP with one' less stage. The same decomposition is then applied to the subproblem, giving rise to a nested decomposition scheme, in which each stage acts as a master for the following stage and a subproblem for the preceding. Optimizing a single stage problem results in satisfying the "local" optimality conditions. A very general rule is given for selecting the next subproblem to optimize, and finite convergence to a solution satisfying all linking conditions is demonstrated. Procedures for extracting the optimal primal solution at the end of the main algorithm and for initialization are given. Particular rules for selecting the next subproblem and for generating additional proposal vectors are discussed. Finally, it is shown how a variety of problems may be restructured as multi-stage linear programs to which this algorithm may be applied, and some computational experience is reported. Date: 1973 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:20:y:1973:i:3:p:282-292 Access Statistics for this article More articles in Management Science from INFORMS Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.