A sampling-based decomposition algorithm with application to hydrothermal scheduling : cut formation and solution quality

textWe consider a hydrothermal scheduling problem with a mid-term horizon(HTSPM) modeled as a large-scale multistage stochastic program with stochastic monthly inflows of water to each hydro generator. In the HTSPM we seek an operating policy to minimize the sum of present and expected future costs, which include thermal generation costs and load curtailment costs. In addition to various simple bounds, problem constraints involve water balance, demand satisfaction and power interchanges. Sampling-based decomposition algorithms (SBDAs) have been used in the literature to solve HTSPM. SBDAs can be used to approximately solve problem instances with many time stages and with inflows that exhibit interstage dependence. Such dependence requires care in computing valid cuts for the decomposition algorithm. In order to help maintain tractability, we employ an aggregate reservoir representation (ARR). In an ARR all the hydro generators inside a specific region are grouped to effectively form one hydro plant with reservoir storage and generation capacity proportional to the parameters of the hydro plants used to form that aggregate reservoir. The ARR has been used in the literature with energy balance constraints, rather than water balance constraints, coupled with time series forecasts of energy inflows. Instead, we prefer as a model primitive to have the time series model forecast water inflows. This, in turn, requires that we extend existing methods to compute valid cuts for the decomposition method under the resulting form of interstage dependence. We form a sample average approximation of the original problem and then solve this problem by these special-purpose algorithms. And, we assess the quality of the resulting policy for operating the system. In our analysis, we compute a confidence interval on the optimality gap of a policy generated by solving an approximation on a sampled scenario tree. We present computational results on test problems with 24 monthly stages in which the inter-stage dependency of hydro inflows is modeled using a dynamic linear model. We further develop a parallel implementation of an SBDA. We apply SBDA to solve the HTSPM for the Brazilian power system that has 150 hydro generators, 151 thermal generators and 4 regions that each characterize an aggregate reservoir. We create and solve four different HTSPM instances where we change the input parameters with respect to generation capacity, transmission capacity and load in order to analyze the difference in the total expected cost.Mechanical Engineerin