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

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 dec...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 2009-09, Vol.57 (5), p.1271-1286
Main Authors: Singh, Kavinesh J, Philpott, Andy B, Wood, R. Kevin
Format: Article
Language:English
Subjects:
Algorithms
Analysis
applications
Applied sciences
Benders decomposition
Capacity costs
capacity expansion
Decomposition
Determinism
electric
Electricity distribution
Exact sciences and technology
facilities/equipment planning
industries
integer
Integer programming
Integers
Integrated logistic support
Inventory control, production control. Distribution
Linear programming
Mathematical programming
Mathematical vectors
networks/graphs
Operating costs
Operational research and scientific management
Operational research. Management science
Optimal solutions
Planning
Plant roots
Production capacity
Production planning
programming
stochastic
Stochastic models
Stochastic programming
Studies
Vertices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.1080.0678