Dantzig-Wolfe Decomposition for Solving Multistage Stochastic Capacity-Planning Problems
Singh, Kavinesh J.
Philpott, Andy B.
MetadataShow full item record
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.
Operations Research, 57, pp. 1271-1286.
Rightsdefined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
McMasters, Alan W. (Monterey, California. Naval Postgraduate School, 1972-09-12); NPS55MG72091AThe capacity expansion problem for flow networks, first studied by D. R. Fulkerson, is reexamined. In the case where no free initial capacity is available, it is shown that the optimal expansion takes place on the arcs of ...
Solution of large-scale multicommodity network flow problems via a logarithmic barrier function decomposition Lange, Heinrich (Monterey, California. Naval Postgraduate School, 1988-03);A new algorithm is presented using a logarithmic barrier function decomposition for the solution of the large-scale multicommodity network flow problem. Placing the complicating joint capacity constraints of the multicommodity ...
San Martin, Pablo Alvarez (Monterey California. Naval Postgraduate School, 2007-09);This thesis develops and solves a tri-level optimization model to plan the optimal defense of an infrastructure from intelligent attack. We assume that a "defender" will first use limited defensive resources to protect ...