Show simple item record

2008-03-07Buch DOI: 10.18452/8389
Dantzig-Wolfe decomposition for solving multi-stage stochastic capacity-planning problems
dc.contributor.authorSing, Kavinesh J.
dc.contributor.authorPhilpott, Andy B.
dc.contributor.authorWood, R. Kevin
dc.contributor.editorHigle, Julie L.
dc.contributor.editorRömisch, Werner
dc.contributor.editorSen, Surrajeet
dc.date.accessioned2017-06-16T20:17:05Z
dc.date.available2017-06-16T20:17:05Z
dc.date.created2008-03-11
dc.date.issued2008-03-07
dc.date.submitted2008-03-06
dc.identifier.urihttp://edoc.hu-berlin.de/18452/9041
dc.description.abstractWe 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.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectcolumn generationeng
dc.subjectmulti-stage stochastic mixed-integer programeng
dc.subjectbranch-and-priceeng
dc.subjectcapacity expansioneng
dc.subjectDantzig-Wolfe decompositioneng
dc.subject.ddc510 Mathematik
dc.titleDantzig-Wolfe decomposition for solving multi-stage stochastic capacity-planning problems
dc.typebook
dc.identifier.urnurn:nbn:de:kobv:11-10086965
dc.identifier.doihttp://dx.doi.org/10.18452/8389
local.edoc.container-titleStochastic Programming E-Print Series
local.edoc.pages38
local.edoc.type-nameBuch
local.edoc.container-typeseries
local.edoc.container-type-nameSchriftenreihe
local.edoc.container-volume2008
local.edoc.container-issue5
local.edoc.container-erstkatid2936317-2

Show simple item record