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


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 (276KB)
Compressed postscript MS (131KB)
G-Zipped postscript MS (101KB)
History: Submitted to Operations Research, Nov 1996.
Related Publications: Technical Report MS 96-018.