Scenario Tree Reduction in Stochastic Programming with Recourse for Hydropower Operations

Published: 2/20/2018

Decision makers in hydropower management are required to schedule releases for the immediate time period to maximize overall benefits. Streamflow forecasts may be utilized in the determination of the releases, however, long-term meteorological forecasts are unreliable due to their stochastic properties. This means that the optimal operation of reservoirs can be considered a risk-based decision-making problem.

Multistage stochastic programming with recourse can be used in modeling to alleviate the uncertainty of streamflows and assist in making release decisions. The streamflows are discretized and then the stochastic programming model uses streamflow scenario trees to represent random streamflow outcomes. This allows the original stochastic model to be transformed into a deterministic equivalent. Scenario tree generation methods include simulation-based methods, optimization methods, and clustering-based methods where the input is taken from historical data.

The simulation-based methods sample the scenarios using the distribution of random variables. This method preserves the observed transition probability, however, poses a challenge in sampling scenario trees from multivariate distributions (due to cross correlation). The moment matching methods match the statistical moments of scenario trees with those of observed samples. This method utilizes optimization algorithms to find the best fit. A comparison of the different methods suggests that the selection be based on the specific problem under consideration. An algorithm developed by Høyland and Wallace minimizes the differences between statistical moments of scenario trees and observed samples. This allows decision-makers to compare the importance of each type of moment and set priorities. Clustering-based methods, an alternative way to construct scenario trees, use the distribution of the random variables by sampling directly from observed samples and finding the representative scenarios by clustering. The generated scenario tree includes the scenarios that represent the clustering centroids of the observed samples. The neural gas method is a machine learning algorithm that uses vector quantization and preserves the structure at all times. This method was used in the subject study due to its superior performance.

Stochastic programming with a recourse model is computationally heavy due to the growth of dimensionality. Scenario tree reduction can be an effective way of decreasing the computational cost because the computational demand of the model is directly related to the size of the scenario tree. Scenario tree reduction causes information loss, so the results may be suboptimal. Numerical experiments were conducted by systematically reducing the scenarios and running a stochastic programming model to determine the objective function and CPU time required. In-sample and out-of-sample tests were also used to evaluate the impact of scenario tree reduction on the objective function of the stochastic model. (The objective of the subject study is to maximize the expected total energy production of the reservoir system.) The quality of the reduced solution was assessed in terms of energy production. Nonlinear programming was used to solve the deterministic equivalents of stochastic programming with a recourse model for hydropower optimization. The tree reduction method proposed in this study is based on the influence of reduction on solution accuracy.

The four steps involved in generating scenario trees with the neural gas method include initialization, new series selection, iteration, and probability of scenario. First, each node in the tree is initialized by selecting an observation record from the historical data. Next, before each iteration, an entire series is randomly selected. The position of the featured vectors is altered to move them toward the selected vector by iterating on node values. The probability of each scenario is calculated according to the number of series that are the minimum distance from the scenario.

The two stages in a multistage stochastic program with a recourse model include the immediate stage and forthcoming stages. Monthly time periods are used to represent the stages in hydropower optimization, with the immediate time period being used to make a unique decision on the release policy based on deterministic streamflow forecasts. Deterministic outcomes of the reservoir ending storage and benefit associated with the release policy are obtained, and since information beyond the immediate time period is uncertain, release outcomes in the forthcoming time periods are stochastic and determined by the corresponding scenarios. A recourse action is taken based on the updated data in the new time period. This allows the decision-makers to avoid consequences caused by the operation strategy. In the subject study, the recourse action is taken by moving the first time period and running the model to the fixed boundary condition.

Several case studies were conducted, and the results show that the neural gas method produces unbiased scenario trees, however, it does not preserve the variances when scenario trees are reduced. It also demonstrated that the diversity loss causes extreme dry and wet scenarios to not be reproduced in the reduced trees. The study found that the highest scenario tree reduction level is 40% for preserving the values of the objective function. At this reduction level, the results show that the mean value of energy production from the reduced solutions is only 0.04% lower than the full-tree solutions. Thus, the goal of reducing computational demand without significantly changing the objective function was met.