Nested Benders decomposition and dynamic programming
for reservoir optimization
T.W. Archibald,
C.S. Buchanan
K.I.M. McKinnon
and
L.C. Thomas
Technical Report MS 96-001 and BS 96/2
Abstract
This paper presents a computational comparison of nested Benders
decomposition and dynamic programming (DP) for stochastic optimization
problems arising from the optimization of hydro-electric generation
from hydraulically linked reservoirs. The following assumptions are
made: the amount of electricity produced by a generator is a concave
piecewise linear function of the volume taken from the feeder
reservoir and is independent of the volume in the feeder reservoir;
the reward for generation is a concave piecewise linear function of
total generation; the final value is a separable concave piecewise
linear function of residual volume. These assumptions allow the
problem to be formulated as a linear programming problem. The
examples considered have between 3 and 17 reservoirs, two weather
states, three runoff patterns and five periods. The examples are
solved exactly by the simplex method and nested Benders decomposition
and solved approximately by discrete DP. A full version of DP is used
for the 3 and 4 reservoir cases, and a decomposition method is used
for all examples. The full DP results are within 1% of the optimal
and the DP decomposition results are within 3.2% of the optimal.
Timings are given for serial and parallel versions of the algorithms.
An analysis is given of how the different methods scale with the
number of periods, reservoirs, weather states and runoff patterns, and
also how applicable they are to more general problems.
Key words:
Dynamic programming, Benders decomposition, stochastic optimization,
hydro-electric, reservoir operation.
Text of report
Postscript
MS 96-001.ps
(276KB)
Compressed postscript
MS 96-001.ps.Z
(131KB)
G-Zipped postscript
MS 96-001.ps.gz
(101KB)
History:
Submitted to Operations Research, Nov 1996.
Related Publications:
Technical Report
MS 96-018.