This report summarizes research that I conducted with Hydro Research Foundation (HRF)
support. The general focus was hydropower operations optimization using dynamic programming (DP)
algorithms. More specifically, there were three areas of concern. The first concern was near real-time
operations optimization using a time decomposition algorithm with different representations of
uncertainty. The second concern was the value of forecasts and forecast precision to operations
optimization. The third concern is the reduction of the computational burden of high-dimensional DP
using intelligent sampling of the state space. Idealized reservoir systems based on the Kennebec River in
Maine are used as case studies.
The objective of hydropower operations optimization is to maximize the expected benefit
obtained from a reservoir system from the present time to the end of some planning horizon. In practice
time is often broken into decision stages, so the problem becomes the selection of a sequence of releases
which maximizes the expected benefit, subject to a set of constraints. The problem is challenging because
the future availability of water is uncertain and the benefits and constraints are non-linear in the decision
variable. Stochastic DP (SDP) algorithms are well suited to this type of problem. This research used the
sampling SDP algorithm, which represents uncertain future flows as a range of flow time series scenarios
rather than a Markov process.
The first concern addressed in this report is use of a time decomposition algorithm to optimize
operation of a reservoir with a sub-daily time step. This involves solving nested optimization models,
each with a different planning horizon and time-step, where the longer-term planning models inform the
shorter-term models. This allows for rapid optimization of short-term operations, while efficiently
considering seasonal objectives and constraints. A key consideration is how uncertainty is represented in
each of the nested optimization models. By changing the probability of transitioning from one scenario to
another, it is possible to generate a number of decision trees and the assessment of which is most
advantageous. Three general transition cases were tested: the case which considers no transitions
between scenarios, the case that assumes transitioning to any scenario is equally likely, and the case that
bases the probability of transitioning on the flow forecast for the next period.
Through testing on an idealized single reservoir system, it was discovered that use of forecasts to
estimate transition probabilities is most useful in short-term optimization. In fact, long- and mid-term forecasts provide little improvement over configurations which allow no transitions between scenarios. In contrast, models that assume transition to any scenario is equally likely performed poorly, because they poorly reflect the persistence of flow when computing the long-term future value of water. Thus, it seems a successful algorithm configuration will use forecasts for short-term planning and a reasonable model of the persistence of flow for the long- and medium-term models (i.e. no transitions between scenarios or transitions based on forecasts).
The second research concern is the value improved forecast precision to optimization
performance, and how this might change depending on the planning horizon and time step considered.
For example, does the precision of long-term forecasts significantly affect the performance of the time
decomposition algorithm, or is the precision of short-term forecasts more important. This is examined by
applying the same model configurations previously described, but with varying forecast precision. It was
determined that for summer operations optimization, long- and mid-term forecast precision contributes
very little to the efficient operation of the reservoir. As was discussed above, use of forecasts for long and mid-term planning is of little value, thus it is not surprising that forecast precision for longer-term planning is not important. In contrast, the performance of the algorithm is highly sensitive to the precision of the short-term forecast.
The third research concern is the reduction of the computational burden of high-dimensional DP.
In DP, the state of the system in any time is described by state variables. In reservoir optimization, the
state variable is reservoir storage, so the addition of a reservoir to the system involves the addition of a
state variable, and a new dimension to the state space. This exponentially increases the difficulty of
numerically solving the optimization problem. However, many points in the state-space represent
unreasonable combinations of storages. The proposed Corridor DP algorithm saves computational effort
by focusing the optimization effort on the region of the state space which the system will likely visit. One
challenge of implementing Corridor DP is that cubic spline interpolation can perform poorly when basis
points are irregularly placed. Instead, this research used radial basis function (RBF) interpolation, which
is not constrained by the placement of basis points. Because the Corridor DP optimizes over the entire
state space, not just inside the corridor, a coarse spline is fit to a few points in the extremes of the state
space. An RBF surface models the deviation from the spline in the corridor region.
The Corridor DP algorithm is applied to an idealized four reservoir system. The corridor region
was determined through simulation of the historic operation of the actual system. In numerical trials, an
early implementation of the Corridor DP algorithm achieves a given relative error with about 1/2 the
computational effort of DP with spline interpolation, and only 1/10 the computational effort of DP with linear interpolation. Theoretical results are presented which suggest how the radial basis function
interpolation and corridor selection criteria might be improved in the future.
This report focuses on the research conducted with HRF support. This research has focused on
three concerns. First, the merit of various representations of uncertainty. Second, the value of forecast
precision to the optimization effort. Finally, the reduction of the computational burden of solving highdimensional DP problems. Results addressing each concern are presented, as well as suggestions for
future work,
Before ending this executive summary, I’d like to express my gratitude to the Hydro Research
Foundation for their support over the last three years. In addition to the financial support, they have
provided many industry and government contacts who have proved invaluable as this research has
evolved.
