Nested Benders decomposition and dynamic programming for reservoir optimisation

This paper presents a computational comparison of nested Benders decomposit ion and dynamic programming (DP) for stochastic optimisation problems arisi ng from the optimisation of hydro-electric generation from hydraulically li nked reservoirs. The examples considered have between 3 and 17 reservoirs, two weather states, three runoff patterns and five periods. The examples ar e solved exactly by the: simplex method and nested Benders decomposition an d solved approximately by discrete dynamic programming (DP). A full version of DP is used for examples with 3 and 4 reservoirs, and a decomposition me thod is used for all examples. The full DP results are within 1% of optimal and the DP decomposition results are within 3.2% of optimal. Timings are g iven for serial and parallel versions of the algorithms. An analysis is giv en of how the different methods scale with the number of periods, reservoir s, weather states and runoff patterns, and also how applicable they are to more general problems.