Le 26/10/2023 par CecileR :
Contexte
Les systèmes électriques insulaires (SEI) dont EDF a la responsabilité (La Réunion, Corse, Guadeloupe, Martinique et Guyane principalement) présentent plusieurs spécificités par rapport aux grands systèmes continentaux :
Par ailleurs ces systèmes connaissent une mutation rapide accompagnant leur transition énergétique.
EDF dispose de deux outils d’optimisation, un utilisé à un horizon court-terme (CT) et l’autre à un horizon moyen et long terme (MT-LT). Ces outils modélisent bien le fonctionnement du système électrique actuel et les aléas auxquels il est soumis, et ont été récemment améliorés pour mieux prendre en compte les nouvelles règles de gestion qui émergent, comme par exemple le respect de la tenue de la fréquence via une contrainte dite d’inertie pour le placement de la production. Ces outils ont été déployés en fin d’année 2020.
OLIVE est la bibliothèque commune aux deux outils qui permet d’optimiser à horizon journalier le placement de la production des parcs insulaires, de manière à satisfaire la demande en puissance électrique, tout en respectant les contraintes de fonctionnement des unités de production (temps minimum de marche et d’arrêt, minima techniques de fonctionnements...). Ce problème d’optimisation est résolu frontalement par un solveur de programmation linéaire à variables mixtes, et les temps de résolution sont parfois importants.
Cela peut ainsi limiter l'utilisation de OASYS, l'outil de gestion MT-LT au sein duquel OLIVE est intégré et souvent appelé.
Le problème résolu par OLIVE s’apparente au Unit Commitment Problem [1], problème classique de la littérature. Toutefois, en raison des spécificités des systèmes insulaires, les instances à résoudre présentent des particularités qui accroissent la difficulté du problème, par exemple des courbes de coûts de production non convexes pour les unités thermiques, mais également des contraintes d’inertie, qui couplent davantage les différentes unités de production entre elles.
Un premier stage réalisé en 2022 a permis d’obtenir une première maquette, basée sur SCIP (C++), implémentant une génération de colonnes, ainsi qu’un Branch&Price, pour une version allégée du problème. Les résultats obtenus lors de ce stage ont ouvert plusieurs perspectives qu’on se propose de traiter au cours du présent stage.
Objectifs du stage
La maquette implémentée permet de tester 2 structures différentes de décomposition. Pour l’une d’elle, le sous-problème issu de la génération de colonne est résolu par PLNE, impliquant des temps de calcul extrêmement longs. Un axe du stage consistera à concevoir et développer un algorithme de programmation dynamique pour résoudre ces sous-problèmes. Par ailleurs, d’autres structures de décomposition [3,5] (par exemple, décomposition temporelle) pourront être explorées en vue d’améliorer la borne inférieure obtenue.
Les premiers résultats ont montré que la génération de colonnes a besoin d’être stabilisée : en effet, sur plusieurs de nos instances, le nombre d’itérations est très grand et on observe des signes de dégénérescence. Plusieurs pistes seront à étudier puis à implémenter pour réduire ce nombre d’itérations : techniques de stabilisation classiques [2], mais aussi techniques dédiées (comme l’agrégation de variables [2]) permettant de casser les symétries du problème, source de dégénérescence.
La convergence du Branch&Price semble ralentie en raison des bornes supérieures calculées par SCIP qui sont de piètre qualité. Une piste prometteuse serait de développer une heuristique primale basée sur la génération de colonnes [4] permettant d’améliorer ces bornes et d’accélérer la résolution. Si les heuristiques développées sont performantes, il pourra être envisagé de les utiliser également comme MipStart dans la résolution actuelle en frontal.
On réfléchira à des stratégies de branchement à la fois sur les variables originales du problème (décisions marche/arrêt, …) et sur les variables étendues issues de la décomposition, de manière à rendre plus efficace le B&P et les heuristiques primales qui y sont adossées.
Le stage donnera lieu à la rédaction d’une note ainsi qu’à des présentations, à SEI et à la R&D.
Conditions matérielles
Lieu du stage : EDF Lab Paris-Saclay (7, Boulevard Gaspard Monge ; 91120 Palaiseau)
Le site est accessible par transports en commun
Durée : 6 mois.
Rémunération : Entre 1100 et 1400 euros selon le niveau d’étude (césure ou stage de fin d’étude)
Profil du stagiaire
Domaines de compétence : Ecole d’ingénieur ou master recherche, niveau master
Profil : recherche opérationnelle, développement informatique
Renseignements complémentaires
Candidature (lettre de motivation et CV) à adresser de préférence directement aux encadrants.
Alex Fauduet
Cécile Rottner
Hugo Gevret
hugo.gevret@edf.fr
Références
[1] van Ackooij, W., Lopez, I. D., Frangioni, A., Lacalandra, F., & Tahanan, M. (2018). Large-scale unit commitment under uncertainty: an updated literature survey. Annals of Operations Research, 271(1), 11-85.
[2] Vanderbeck, F. (2005). Implementing mixed integer column generation. In Column generation (pp. 331-358). Springer, Boston, MA.
[3] Guignard, M., & Kim, S. (1987). Lagrangean decomposition: A model yielding stronger Lagrangean bounds. Mathematical programming, 39(2), 215-228.
[4] Sadykov, R., Vanderbeck, F., Pessoa, A., Tahiri, I., & Uchoa, E. (2019). Primal heuristics for branch and price: The assets of diving methods. INFORMS Journal on Computing, 31(2), 251-267.
[5] Dubost, L., Gonzalez, R., & Lemaréchal, C. (2005). A primal-proximal heuristic applied to the French Unit-commitment problem. Mathematical programming, 104(1), 129-151.
