Dantzig-Wolfe Decomposition for Solving Multistage Stochastic Capacity-Planning Problems
Loading...
Authors
Singh, Kavinesh J.
Philpott, Andy B.
Wood, Kevin
Subjects
facilities/equipment planning: capacity expansion
industries: electric
networks/graphs: applications, stochastic
programming
integer
algorithms
Benders decomposition
applications
stochastic
industries: electric
networks/graphs: applications, stochastic
programming
integer
algorithms
Benders decomposition
applications
stochastic
Advisors
Date of Issue
2009
Date
Publisher
Language
Abstract
We describe a multistage, stochastic, mixed-integer programming model for planning capacity expansion of production facilities. A scenario tree represents uncertainty in the mode; a general mixed-integer program defines the operation submodel at each scenario-tree mode, and capacity expansion decisions link the stages. We apply "variable splitting" to two model variants, and solve those variants using Dantzig-Wolfe decomposition. The Dantzig-Wolf master problem can have a much stronger linear programming relaxation than is possible without variable splitting, over 700% stronger in one case. The master problem solves easily and tends to yield integer soltuions, obviating the need for a full branch-and-price soltuion procedure. For each scenario-tree node, the decomposition defines a subproblem that may be viewed as a single period, deterministic, capacity-planning problem. An effective solution procedure results as long as the subproblems solve efficiently, and the procedure incorporates a good "duals stabilization method." We present computational results for a model to plan the capacity expansion of an electricity distribution network in New Zealand, given uncertain future demand. The largest problem we solve to optimality has six stages and 243 scenarios, and corresponds to a deterministic equivalent with a quarter of a million binary variables.
Type
Article
Description
Operations Research, 57, pp. 1271-1286.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funding
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.