Résolution de problèmes d’optimisation stochastique de grande taille : application à des problèmes d’investissement dans les réseaux électriques

Abstract

Cette thèse s'intéresse à la modélisation et la résolution de problèmes d'optimisation stochastique de grande taille provenant de problèmes d'investissements dans les réseaux électriques. Ces travaux ont été motivés par la complexité numérique des problèmes d'investissement stochastiques résolus dans le cadre d'études prospectives menées à RTE (Réseau de Transport d'électricité), le gestionnaire de réseau électrique français. A partir d'un réseau, ces problèmes modélisent des investissement sur des capacités de production sur les noeuds, ou des capacités de transport sur les arcs pour satisfaire des demandes en électricité sur un horizon de temps donné avec des pas de temps discrets. Les demandes en électricité, les prévision météorologiques ou les coûts opérationnels sont aléatoires et modélisés par un ensemble fini de scénarios d'aléas. On s'intéresse à deux problèmes particuliers.Premièrement, nous présentons un algorithme amélioré basé sur une décomposition de Benders pour résoudre de grand problèmes linéaires stochastiques à deux étapes modélisés avec un ensemble fini de scénarios. De tels modèles sont utilisés dans les études prospectives menées à RTE mais les résolutions actuelles sont limitées dans le nombre de scénarios apparaissant dans les modèles pour conserver des temps de calculs raisonnables. L'algorithme proposé est basé sur une partition des sous-problèmes et sur une modification du critère d'arrêt. Le critère d'arrêt proposé permet de ne résoudre qu'un petit sous-ensemble de sous-problèmes à la plupart des itérations de l'algorithme. Nous présentons aussi une méthode générique pour stabiliser notre algorithme, et montrons son efficacité au travers d'une étude numérique étendue. Les résultats montrent que l'algorithme proposé peut être jusqu'à 25 fois plus rapide qu'un algorithme de faisceaux (level bundle) et jusqu'à 5 fois plus rapide qu'un algorithme basé sur la décomposition de Benders avec une stabilisation in-out et une méthode statique d'agrégation de coupes.Deuxièmement, nous étudions un modèle d'expansion de réseau stochastique prenant en compte une contrainte de fiabilité. Cette contrainte à pour but de limiter, en moyenne sur les scénarios d'aléas, le nombre de noeuds et de pas de temps auxquels la demande n'est pas entièrement satisfaite dans une solution du problème. Nous montrons que le fait d'ajouter une telle contrainte, qui prend en compte des variables provenant de différents scénarios dans sa formulation, implique de modéliser le problème comme un problème bi-niveaux. Les fonctions objectifs sont les mêmes dans les deux niveaux du problème. Malgré cette structure particulière, nous montrons que le problème n'est pas équivalent à sa high-point relaxation. Le problème obtenu est un très grand problème bi-niveaux en variables mixtes, et les algorithmes classiques pour résoudre ces problèmes ne sont pas en mesure de résoudre des problèmes de cette taille. Nous présentons une méthode heuristique basée sur une décomposition de Benders et une dichotomie sur les coûts d'investissements pour trouver des solutions réalisables de ce problème. Cette méthode est capable de trouver des solutions réalisables sur des problèmes générés aléatoirement avec plusieurs millions de variables et contraintes.