Optimization Online


Managing Hydroelectric Reservoirs over an Extended Planning Horizon using a Benders Decomposition Algorithm Exploiting a Memory Loss Approximation

Pierre-Luc Carpentier (plcarpentier***at***gmail.com)
Michel Gendreau (michel.gendreau***at***cirrelt.ca)
Fabian Bastin (bastin***at***iro.umontreal.ca)

Abstract: Conventional scenario tree (CST)-based decomposition methods (CSTDMs) (e.g. progressive hedging, nested Benders) are widely used for managing hydroelectric reservoirs over the mid-term horizon (2-60 months). To use these methods, no modeling approximation needs to be made about time-correlation effects (TCEs) influencing random parameters (RPs) at t=1,...,T. Therefore, CSTDMs are powerful methods for handling multi-lag stochastic processes. When T is large (T >= 20), CSTDMs can potentially handle high-order TCEs (lag >= 10). However, this is usually unnecessary in practice and, unfortunately, the computational requirement (time, memory) of CSTDMs grow exponentially with the branching level (BL) used. In general, spatially-correlated and continuously-distributed RPs must usually be discretized very coarsely (1-7 branching stages, 1-3 outcomes per stage). In this paper, we propose a new Benders decomposition method which is well-suited when T is large. We partition the horizon in two stages. We simplify high-order TCEs at the second stage by assuming that RPs have a memory loss at the end of the first stage. Consequently, only one recourse function must be constructed, cuts can be shared and RPs can be represented using a much smaller number of nodes than if a CST was used. The low memory requirement and fast convergence rate of our algorithm enables to describe RPs using a large number of scenarios.

Keywords: Hydroelectricity, power generation, stochastic Programming, scenario tree, Benders decomposition, L-Shaped Method

Category 1: Stochastic Programming

Category 2: Applications -- OR and Management Sciences


Download: [Postscript][PDF]

Entry Submitted: 07/07/2013
Entry Accepted: 07/08/2013
Entry Last Modified: 11/14/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society