| Author(s): |
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 |
| Submission Date: |
06.03.2008 |
| Series Title: |
Stochastic Programming E-Print Series
(SPEPS)
|
| 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.
|
|
| Diese Seite taggen:
These
icons lead to social bookmarking systems where you can
create and manage personal bookmarks and discover
bookmakrs of other users.
|
|
| Abstract (eng): |
| 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-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 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.
|
Access Statistics:
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.
|
  | | | | | | | | | | | | | | | | | | | | | May
11 | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Jan
12 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 |
| Monat | May
11 | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Jan
12 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 | | Startseite | 4 | 1 | 2 | | 2 | 2 | | 6 | 3 | 2 | 2 | 2 | 1 | | 3 | 5 | 1 | | | 1 | 6 | | PDF | 28 | 7 | 11 | 3 | 2 | 5 | 3 | 14 | 11 | 18 | 23 | 24 | 19 | 12 | 21 | 14 | 13 | 24 | 16 | 16 | 32 |
Gesamtzahl der Zugriffe seit May 2011: - Startseite – 43 (2.05 pro Monat)
- PDF – 316 (15.05 pro Monat)
|
