<  Back to the Polytechnique Montréal portal

Méthodes de décomposition pour la planification à moyen terme de la production hydroélectrique sous incertitude

Pierre-Luc Carpentier

Ph.D. thesis (2013)

Open Access document in PolyPublie
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (2MB)
Show abstract
Hide abstract


In this thesis, we consider the midterm production planning problem (MTPP) of hydroelectricity generation under uncertainty. The aim of this problem is to manage a set of interconnected hydroelectric reservoirs over several months. We are particularly interested in high dimensional reservoir systems that are operated by large hydroelectricity producers such as Hydro-Québec. These producers operate a complex production system and must satisfy tight operational constraints in an highly uncertain decision environment. In general, midterm optimization models consider a weekly or monthly time step and rely on a simplified representation of the power system. The main source of complexity of the MTPP is usually related to the representation of uncertainty. Random parameters of the MTPP are usually characterized by a complex probability distribution function which is difficult to represent in numerical optimization models. Over the past decades, several stochastic optimization methods were proposed in the literature for managing hydroelectric reservoirs over the midterm planning horizon. Most of these methods are only applicable on low- or medium-size systems due to the curse of dimensionality. stochastic optimization methods that are based on a scenario tree representation of uncertainty are among the rare approaches that can be used on large hydroelectric reservoir systems. These methods work by replacing the original continuous distribution by a discrete distribution possessing a finite number of possible realizations. The stochastic program to be solved can be reformulated into a deterministic equivalent program whose size is proportional to the system size. The main limitation with this approach is due to the exponential growth of the DEP's size with the branching level of the tree. In practice, the DEP is usually quite large and must be solved using a decomposition method which exploits its special mathematical structure. The aim of this thesis is to develop and evaluate different decomposition methods for solving the MTPP under uncertainty. This thesis is divided in three articles. The first article demonstrates the applicability of the progressive hedging algorithm (PHA), a scenario decomposition method, for managing hydroelectric reservoirs with multiannual storage capacity under highly variable operating conditions in Canada. The PHA is a classical stochastic optimization method designed to solve general multistage stochastic programs defined on a scenario tree. This method works by applying an augmented Lagrangian relaxation on non-anticipativity constraints (NACs) of the stochastic program. At each iteration of the PHA, a sequence of subproblems must be solved. Each subproblem corresponds to a deterministic version of the original stochastic program for a particular scenario in the scenario tree. Linear and a quadratic terms must be included in subproblem's objective functions to penalize any violation of NACs. An important limitation of the PHA is due to the fact that the number of subproblems to be solved and the number of penalty terms increase exponentially with the branching level in the tree. This phenomenon can make the application of the PHA particularly difficult when the scenario tree covers several tens of time periods. Another important limitation of the PHA is caused by the fact that the difficulty level of NACs generally increases as the variability of scenarios increases. Consequently, applying the PHA becomes particularly challenging in hydroclimatic regions that are characterized by a high level of seasonal and interannual variability. These two types of limitations can slow down the algorithm's convergence rate and increase the running time per iteration. Overall, very few researchers applied the PHA on reservoir management problems. The few studies that consider this type of application consider a short-range horizon with a small scenario tree. In this study, we apply the PHA on Hydro-Qu\'ebec's power system over a 92-week planning horizon. Hydrologic uncertainty is represented by a scenario tree containing 6 branching stages and 1,635 nodes. The PHA is especially well-suited for this particular application given that the company already possess a deterministic optimization model to solve the MTPP. In fact, only a few minor modifications are required to transform the current model into a new PHA-based stochastic optimization. The second article presents a new approach which enhances the performance of the PHA for solving general Mstochastic programs. The proposed method works by applying a multiscenario decomposition scheme on the stochastic program. Our heuristic method aims at constructing an optimal partition of the scenario set by minimizing the number of NACs on which an augmented Lagrangean relaxation must be applied. Each subproblem is a stochastic program defined on a group of scenarios. NACs linking scenarios sharing a common group are represented implicitly in subproblems by using a group-node system index instead of the traditional scenario-time index system. Only the NACs that link the different scenario groups are represented explicitly and relaxed. The proposed method is evaluated numerically on an hydroelectric reservoir management problem in Qu\'ebec. The results of this experiment show that our method has several advantages. Firstly, it allows to reduce the running time per iteration of the PHA by reducing the number of penalty terms that are included in the objective function and by reducing the amount of duplicated constraints and variables. In turn, this allows to reduce the running time per iteration of the algorithm. Secondly, it allows to increase the algorithm's convergence rate by reducing the variability of intermediary solutions at duplicated tree nodes. Thirdly, our approach reduces the amount of random-access memory (RAM) required for storing Lagrange multipliers associated with relaxed NACs. The third article presents an extension of the L-Shaped method designed specifically for managing hydroelectric reservoir systems with a high storage capacity. When such systems are considered, the midterm planning horizon usually contains several tens of time periods and conventional decomposition methods such as the PHA can only be used if a low branching level is used. In these situations, the scenario tree typically corresponds to a very coarse representation of the underlying continuous probability distribution. The method proposed in this paper enables to consider a higher branching level than conventional decomposition method enables. To achieve this, we assume that the stochastic process driving random parameters has a memory loss at time period. Because of this assumption, the scenario tree possess a special symmetrical structure at the second stage. We exploit this feature using a two-stage Benders decomposition method. Contrary to most stage-wise decomposition methods that were proposed in previous studies, each decomposition stage covers several consecutive time periods. The proposed method works by constructing a convex and piecewise linear recourse function that represents the expected cost at the second stage in the master problem. The subproblem and the master problem are stochastic program defined on scenario subtrees and can be solved using a conventional decomposition method or directly. We test the proposed method on an hydroelectric power system in Québec over a 104-week planning horizon.


Dans cette thèse, nous considérons le problème de planification à moyen terme (PPMT) de la production hydroélectrique sous incertitude visant la gestion de réservoirs sur un horizon de plusieurs mois. Nous nous intéressons particulièrement aux systèmes de haute dimension composés de dizaines de réservoirs et exploités par les grands producteurs hydroélectriques tels qu'Hydro-Québec. Ces producteurs exploitent des systèmes complexes à hauteur de chute et rendement variables avec des coûts fixes et des délais de démarrage et d'arrêt de groupes. En général, une grande variété de contraintes opérationnelles serrées doivent être satisfaites. Ces systèmes sont habituellement exploités dans un environnement décisionnel hautement incertain. Les modèles d'optimisation à moyen terme de la production considèrent généralement un pas de temps hebdomadaire ou mensuel et reposent sur une représentation simplifiée du système de production. Les courbes de production sont généralement convexes et linéaires par morceaux et les coûts fixe de transaction ou d'arrêt/démarrage sont généralement négligés. La principale source de complexité du PPMT et généralement attribuable à la prise en compte de l'incertitude. Les paramètres aléatoires du PPMT sont généralement caractérisés par une distribution de probabilité multidimensionnelle, continue et asymétrique. Ces caractéristiques sont difficiles à représenter de façon précise dans les modèles d'optimisation. Au cours des dernières décennies, plusieurs méthodes d'optimisation stochastique ont été proposées dans la littérature en gestion de réservoirs. La plupart de ces méthodes sont limitées aux systèmes de dimension modeste en raison de la malédiction de la dimension. Les méthodes basées sur une représentation par arbre de scénarios de l'incertitude comptent parmi les rares approches qui sont applicables aux grands systèmes hydroélectriques. Ces méthodes fonctionnent en remplaçant la distribution continue d'origine par une distribution discrète contenant un nombre fini de réalisations possibles. Ainsi, le programme stochastique à résoudre peut être reformulé en un programme équivalent déterministe dont la taille est proportionnelle à la dimension du système contrôlé. La principale limitation de l'approche par arbre de scénarios est liée à l'augmentation exponentielle de la taille du programme équivalent déterministe avec le niveau de branchement de l'arbre. En pratique, le programme équivalent déterministe doit être résolu par une méthode de décomposition qui exploite sa structure mathématique spéciale. L'objectif de cette thèse consiste à développer et à évaluer différentes méthodes de décomposition permettant de résoudre le PPMT sous incertitude. La thèse est divisée en trois articles. Le premier article démontre l'applicabilité de l'algorithme de progressive hedging (APH), une méthode de décomposition par scénario, pour faire la gestion de réservoirs hydroélectriques multiannuels dans un environnement hautement variable au Canada. L'APH est une méthode classique conçue pour résoudre des programme stochastique multiétape généraux posés sur un arbre de scénarios. Cette méthode fonctionne en appliquant une relaxation Lagrangienne augmentée aux contraintes de non-anticipativité (CNA) du programme stochastique. À chaque itération de l'APH, une série de sous-problèmes doivent être résolus. Chaque sous-problème correspond à une version déterministe du programme stochastique défini sur un scénario particulier de l'arbre. Des termes linéaires et quadratiques sont ajoutés à la fonction objectif des sous-problèmes afin de pénaliser les violations des CNA. Une des principales limitations de l'APH est liée à l'augmentation exponentielle du nombre de sous-problèmes et de termes de pénalité avec le niveau de branchement de l'arbre. Ce phénomène peut rendre l'application de l'APH particulièrement difficile lorsque l'arbre de scénarios considéré contient plusieurs étapes de branchement et couvre un horizon réparti sur des dizaines de périodes. Ces situations surviennent fréquemment lorsque des réservoirs multiannuels sont considérés. Une autre limitation importante de l'APH est causée par l'augmentation du niveau de difficulté des CNA avec la variabilité des scénarios contenus dans l'arbre. Ce phénomène complique l'application de l'APH dans les régions hydroclimatiques caractérisées par une forte variabilité saisonnière et interannuelle. Ces deux types de limitations peuvent ralentir considérablement le taux de convergence et le temps de calcul par itération de l'APH et rendre cette méthode inapplicable en pratique. Dans l'ensemble, très peu de chercheurs ont appliqué l'APH en gestion de réservoirs hydroélectriques. Les rares études portant sur ce type d'application considèrent un horizon de courte portée avec arbre de scénarios de petite taille avec un niveau de variabilité modeste. Dans cette étude, nous appliquons l'APH à la gestion de l'ensemble du parc d'Hydro-Québec sur un horizon de 92 semaines. L'arbre de scénarios considéré contient six étapes de branchement et 1635 noeuds. L'APH est particulièrement bien adaptée pour cette application étant donné du fait que la société d'État dispose actuellement d'un modèle déterministe opérationnel pour faire la planification à moyen terme de la production. En fait, seulement quelques modifications mineures sont nécessaires pour transformer le modèle déterministe actuel en un modèle stochastique basé sur l'APH. Le deuxième article présente une nouvelle approche permettant de réduire le temps de calcul de l'APH lors la résolution de programme stochastique généraux. L'approche proposée fonctionne en appliquant un schéma de décomposition multiscénario au programme stochastique conçu de manière à minimiser le nombre de CNA auxquelles une RLA doit être appliquée. Chaque sous-problème prend la forme d'un programme stochastique défini sur un groupe de scénarios. Les CNA liant les scénarios d'un même groupe sont représentées implicitement dans les sous-problèmes en adoptant une formulation par groupe de scénarios et par noeud plutôt qu'en utilisant le sytème d'indice traditionnel exprimé par période et par scénario. Seulement les CNA liant les différents groupes de scénarios sont représentées explicitement sous forme de contraintes d'égalité linéaires et relaxées. La méthode proposée est évaluée numériquement sur un problème de gestion de réservoirs hydroélectriques au Québec. Les résultats de cette expérience démontrent que notre méthode de partitionnement optimal a plusieurs avantages par rapport au schéma de décomposition par scénario traditionnel. Premièrement, elle permet de diminuer le temps de calcul par itération en réduisant le nombre de termes de pénalité à inclure dans les sous-problèmes et en réduisant le nombre de variables et contraintes dupliquées. Deuxièmement, notre approche permet d'accélérer le taux de convergence de l'algorithme en réduisant la variabilité des solutions intermédiaires obtenues aux noeuds dupliqués. Le troisième article présente une extension de la méthode L-Shaped conçue spécifiquement pour faire la gestion de réservoirs hydroélectriques à haute capacité d'emmagasinnement. Lorsque de tels réservoirs sont considérés, l'horizon à moyen terme couvre typiquement plusieurs dizaines de périodes et les méthodes de décomposition conventionnelles telles que l'APH ne sont applicables que si un faible niveau de branchement est utilisé. Dans ces situations, l'arbre de scénarios considéré correspond généralement à une discrétisation très grossière de la distribution de probabilité continue sous-jacente. La méthode proposée dans cet article permet de considérer un niveau de branchement plus élevé que les méthodes conventionnelles le permettent. Pour atteindre cet objectif, nous posons l'hypothèse selon laquelle le processus stochastique décrivant les paramètres aléatoires subit une perte de mémoire à la fin de la première étape. L'arbre de scénarios résultant de cette hypothèse possède une structure symétrique spéciale à la deuxième étape que nous exploitons en appliquant un schéma de décomposition de Benders à deux étapes. Contrairement à la vaste majorité des méthodes de décomposition par étape proposées dans la littérature, chaque étape de décomposition de notre méthode correspond à plusieurs périodes consécutives. La méthode proposée fonctionne en construisant une fonction de recours convexe et linéaire par morceaux servant à représenter le coût espéré de deuxième étape en fonction de l'état du système à la fin le la première étape dans le problème maître. Le sous-problème et le problème maître sont des programme stochastique définis sur un sous-arbre et peuvent être résolus directement ou par une méthodes de décomposition conventionnelles. Nous démontrons l'efficacité de notre méthode en l'appliquant sur une version réduite du parc de production québécois sur un horizon de 104 semaines.
Department: Department of Mathematics and Industrial Engineering
Program: Mathématiques de l'ingénieur
Academic/Research Directors: Michel Gendreau, Fabian Bastin
PolyPublie URL: https://publications.polymtl.ca/1314/
Institution: École Polytechnique de Montréal
Date Deposited: 14 Apr 2014 11:12
Last Modified: 10 Nov 2022 13:18
Cite in APA 7: Carpentier, P.-L. (2013). Méthodes de décomposition pour la planification à moyen terme de la production hydroélectrique sous incertitude [Ph.D. thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/1314/


Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item