Dantzig-Wolfe decomposition for solving multi-stage stochastic capacity-planning problems

Abstract

We describe a multi-stage, stochastic, mixed-integer-programming model for planning discrete 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-Wolfemaster 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 scheme.” 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 6 stages and 243 scenarios, and corresponds to adeterministic equivalent with a quarter of a million binary variables.