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

Autor: Blanchot, Xavier
Přispěvatelé: Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation (EDGE), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux, François Clautiaux
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Optimization and Control [math.OC]. Université de Bordeaux, 2022. English. ⟨NNT : 2022BORD0357⟩
Popis: This thesis addresses large-scale stochastic optimization programs arising from investment problems in power systems. This work has been motivated by the numerical complexity of stochastic investment problems that are solved in prospective studies conducted by RTE (Réseau de Transport d'Electricité), the French transmission system operator. Considering a network, these problems consist of investing on production capacities on the nodes or transmission capacities on the arcs in order to satisfy demands during a discrete time horizon. We model stochastic demands, weather forecasts or operational costs by a finite number of random scenarios. We focus on two particular numerically challenging optimization problems.Firstly, we present an enhanced Benders decomposition algorithm to solve large-scale two-stage linear stochastic programs formulated with a large discrete set of scenarios. Such problems arise in prospective studies performed at RTE but models are currently limited in the number of scenarios to maintain reasonable computing times. The proposed algorithm relies on a partition of the subproblems into separated batches and a modified stopping criterion. This stopping criterion allows to solve only a few subproblems at most iterations. We also present a generic framework to stabilize the proposed algorithm, and show its efficiency on an extensive numerical study. We show, on the tested instances, that our algorithm can be up to 25 times faster than Benders decomposition with level bundle stabilization or 5 times faster than Benders decomposition with in-out stabilization and static cut aggregation.Secondly, we study a stochastic expansion planning problem taking into account a network reliability constraint. This constraint aims at limiting the expected number of nodes and time steps at which the demand is not fully satisfied in an optimal solution. We show that adding such a constraint, involving variables from different scenarios, leads to a bilevel formulation of the problem. We also show that despite the objective functions are the same in both levels, the problem is not equivalent to its high-point relaxation. As the resulting problem is a very large-scale mixed-integer bilevel program, we do not expect classical bilevel algorithms to solve real-life instances. We introduce a heuristic method based on Benders decomposition and on a binary search on the total investment costs to find feasible solutions. We show that the proposed heuristic is able to find feasible solutions on randomly generated instances with up to several million variables and constraints.; 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.
Databáze: OpenAIRE
načítá se...