|edoc-Server der Humboldt-Universität zu Berlin|
Kavinesh J. Sing, Mighty River Power|
Andy B. Philpott, University of Auckland
R. Kevin Wood, Naval Postgraduate School
|Title:||Dantzig-Wolfe decomposition for solving multi-stage stochastic capacity-planning problems|
|Date of Acceptance:||07.03.2008|
Stochastic Programming E-Print Series |
|Editors:||Julie L. Higle; Werner Römisch; Surrajeet Sen|
|Complete Preprint:||pdf (urn:nbn:de:kobv:11-10086965)|
|Keywords (eng):||column generation, multi-stage stochastic mixed-integer program, branch-and-price, capacity expansion, Dantzig-Wolfe decomposition|
|Submitted in:||Operations Research|
|Metadata export: To export the complete metadata set as Endote or Bibtex format please click to the appropriate link.||Endnote Bibtex|
|print on demand: If you click on this icon you can order a print copy of this publication.|
|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 deﬁnes 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 deﬁnes 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 a deterministic equivalent with a quarter of a million binary variables.|
These data concerning access statistics for individual documents
have been compiled using the webserver log files aggregated by AWSTATS.
They refer to a monthly access count to the full text documents as well as to the entry page.
As for format versions of a document which consist of multiple files (such as HTML) the highest monthly access number to one of the files (chapters) is shown respectivly.
To see the detailled access numbers please move the mouse pointer over the single bars of the digaram.
Gesamtzahl der Zugriffe seit Jul 2011: