Back to search

University of Washington

A splitting algorithm for multistage stochastic programming with application to hydropower scheduling

Abstract

dc:description.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).

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Salinger, David H., 1961-

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Copyright is held by the individual authors.
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Other
b40461889
38588439
Thesis 45989

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Salinger, David H., 1961-. A splitting algorithm for multistage stochastic programming with application to hydropower scheduling. 1997. http://hdl.handle.net/1773/6749