Dantzig-Wolfe Decomposition for Solving Multi-Stage Stochastic Capacity-Planning Problems
Abstract
We describe a general multi-stage stochastic integer-programming model for planning discrete capacity expansion of production facilities. A scenario tree represents uncertainty in the model. Variable splitting leads to two forms of this model: the first allows multiple expansions of each facility over the planning horizon while the second allows at most one. Dantzig-Wolfe decomposition of either split-variable model results in a binary master problem that solves easily, as its linear-programming relaxation tends to yield integer solutions. For each scenario-tree node, the decomposition defines a subproblem that may be viewed as a single-period, deterministic capacity-expansion problem. An effective solution procedure results as long as the subproblems solve efficiently, and the procedure incorporates a good "duals stabilization scheme". We present computational results for a model to plan the capacity expansion of a real-world electricity distribution network given uncertain future demand. The largest problem we solve to optimality has 6 stages and 243 scenarios corresponding to a deterministic equivalent with a quarter of a million binary variables.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 13, 2005
- Accession Number
- ADA487429
Entities
People
- Andy B. Philpott
- Kavinesh J. Singh
- R. Kevin Wood
Organizations
- Naval Postgraduate School