| Abstract | With water in short supply and utility deregulation imminent, the problem of long-term scheduling on a hydroelectric power system has become increasingly important.
Many of the algorithms developed for this large-scale multistage stochastic problem have relied on the dynamic programming algorithm; and so have suffered from the 'curse of dimensionality.' The current fashion is to use a Benders decomposition type algorithm. These have proven successful for the linear or piecewise linear problem, but due to the costs involved, a nonlinear model is more realistic.
Here, we present a new algorithm for the nonlinear (convex) multistage stochastic programming problem (MSP); one that is reasonable for the large-scale (e.g. hydro scheduling) problem and is easily parallelizable.
Development of the algorithm draws on many areas of optimization theory including: duality theory, saddle points, subgradients, scenario trees, Fenchel conjugacy, dynamic programming and splitting methods for monotone operators.
The algorithm is based on an application of Spingarn's operator splitting method to the saddle point problem associated with the MSP. The splitting method imposes a decomposability which results in two main subproblems to be solved at each iteration. One is reformulated as an unconstrained linear-quadratic dynamic programming problem and is solved via a linear feedback loop solution extended to the scenario tree structure. The other subproblem is separable into sub-subproblems for each decision state. In the specialization to the hydropower setting, the main sub-subproblem is solved utilizing properties of the Fenchel conjugate function.
The algorithm is employed for a test problem developed from data provided by the Pacific Gas and Electric Co. consisting of the equivalent of 176 powerhouses and 174 controlled spillways on 94 reservoirs for a 24 month planning horizon. This results in an optimization problem in 165,200 control variables (water release) and 44,368 state variables (water storage). |