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

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.