Dantzig-Wolfe Decomposition for Solving Multistage Stochastic Capacity-Planning Problems

Kavinesh J. Singh (), Andy B. Philpott () and R. Kevin Wood ()
Additional contact information
Kavinesh J. Singh: Mighty River Power Limited, Auckland, New Zealand
Andy B. Philpott: Department of Engineering Science, University of Auckland, Auckland, New Zealand
R. Kevin Wood: Operations Research Department, Naval Postgraduate School, Monterey, California 93943

Operations Research, 2009, vol. 57, issue 5, 1271-1286

Abstract: We describe a multistage, stochastic, mixed-integer programming model for planning capacity expansion of production facilities. A scenario tree represents uncertainty in the model; a general mixed-integer program defines the operational submodel at each scenario-tree node, 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-Wolfe 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 solutions, obviating the need for a full branch-and-price solution 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.

Keywords: facilities/equipment planning; capacity expansion; industries; electric; networks/graphs; applications; stochastic; programming; integer; algorithms; Benders decomposition; applications; stochastic (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0678 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:57:y:2009:i:5:p:1271-1286

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().