Le 31/10/2022 par CecileR :
Proposition de stage 2023
« Résolution efficace du problème de dispatch pour améliorer l’outil d’optimisation des Trajectoires d’investissement Long Terme (TiLT) »
Le département OSIRIS est responsable, au sein d’EDF R&D, de développer des outils et méthodes pour la gestion optimale du portefeuille d’actifs d’EDF (centrales de production, contrats clients, logistique gazière). Ces travaux sont particulièrement stratégiques dans le contexte d’évolution des marchés de l’électricité. Ils sont également utiles pour la gestion de risques financiers, pour l’analyse des marchés de l’électricité et pour la prévision de consommation.
Les ingénieurs chercheurs du groupe « portefeuille à long terme et SI d’études » (R31) étudient les nouveaux mix énergétiques sur un horizon long terme (2035-2050) au sein des systèmes électriques mondiaux, et proposent un SI pour les études. Une partie de ces travaux sont réalisés pour les filiales d’EDF à l’international grâce à un outil logiciel d’équilibre offre – demande long terme reposant sur les fondamentaux du système électrique : TiLT (Trajectoires d’investissements Long Terme).
TiLT optimise les investissements sur une période pluriannuelle à l’aide d’une formulation d’optimisation linéaire de grande taille - résolue de manière directe par un solveur du commerce. Le problème d’investissement long terme correspond à un problème de type « two stage » où : 1. l’ensemble des décisions d’investissements constituent les décisions de premier niveau ; ces « premières décisions » structurent le parc de production dont on cherche ensuite ; 2. à minimiser les coûts en fixant des décisions de production optimales (de « second niveau »). La matrice des contraintes de ce type de problèmes présente une structure diagonale par blocs avec variables liantes qu’il est possible de décomposer en utilisant une reformulation de Benders [1]. Cette reformulation consiste à projeter le second niveau dans l’espace des variables de premier niveau ; le second niveau est alors remplacé par un ensemble de contraintes pouvant être générées de manière dynamique. L’efficacité de ce type d’approches nécessite de pouvoir résoudre de manière efficace les sous-problèmes de Benders correspondant au « dispatch » (i.e., optimisation des décisions de production) sur chaque année de la période. Ce n’est pas le cas dans la version actuelle de TiLT, et c’est l’enjeu sur lequel porte ce stage.
Objectif
Ce stage consiste à étudier le problème de dispatch et explorer des méthodes alternatives à la programmation linéaire « frontale » (simplexe ou point intérieur) pour résoudre celui-ci. Pour cela, la/le stagiaire pourra s’appuyer sur des réflexions préliminaires de la R&D - qu’il devra cependant tester et évaluer :
- Dualisation de certaines contraintes pour décomposer le problème de dispatch par journée ou unité de production ;
- Formulation sous forme de problème de flot à coût minimum et utilisation d’un solveur interne à la R&D pour le problème de dispatch annuel ;
- Génération de colonnes éventuellement combinée avec les méthodes de flots précitées ;
- Méthodes de clustering pour diminuer la taille – donc la complexité - des problèmes.
Encadrement
Le stage sera co-encadré par des experts du logiciel TiLT (équipe « portefeuille à long terme et SI d’études ») et des membres de l’équipe « méthodes et outils d’optimisation » - pour les aspects mathématiques et algorithmiques, en particulier sur les différentes reformulations/relaxations/décompositions. Ce stage s’inscrit également dans le lancement de collaborations académiques sur le sujet portant sur l’exploration des dernières avancées sur les décompositions de Benders [2].
Etape 1 : Formaliser les différentes décompositions possibles pour les problèmes de dispatch et valider la possibilité d’utiliser des méthodes alternatives à la programmation linéaire pour les sous-problèmes unitaires obtenus lors de ces décompositions.
Etape 2 : Constituer un ensemble de jeux de données (JDD) réduits mais représentatifs pour le problème de dispatching ainsi que chacun des problèmes obtenus lors de l’Etape 1.
Etape 3 : Tester l’efficacité de résolution des sous-problèmes unitaires et les possibilités d’utilisation des solveurs internes à la R&D du projet « OptimStore » porté par l’équipe méthodes et optimisation (R36), en particulier le solveur MinCostFlow.
Etape 4 : Tester les différentes décompositions pour les problèmes de dispatch ; mettre en valeur les résultats en montrant l’avantage en temps de résolution par rapport à la résolution directe du problème de dispatch par un solveur.
(Optionnel) Etape 5 : Dans l’éventualité où la/le stagiaire aurait obtenu des résultats suffisamment avancés sur les 4 premières étapes elle/il pourrait tester une décomposition de Benders classique sur le problème d’investissement. A noter qu’il est peu probable que cette décomposition soit efficace telle quelle directement, car elle nécessitera par la suite des travaux autour de méthodes avancées pour la décomposition de Benders, qui ne font pas l’objet de ce stage.
Conditions matérielles :
Lieu du stage : EDF Lab Paris-Saclay, 7 Boulevard Gaspard Monge, 91120 Palaiseau ; accessible par transports en commun.
Durée : 6 mois à partir d’avril 2023.
Rémunération : en fonction du niveau d’étude et de la formation préparée.
Connaissances requises : 3ème année d’école d’ingénieur / Master 2 en optimisation.
Profil : mathématiques appliquées (optimisation), informatique (Python/C++) et économie.
Renseignements complémentaires :
Equipe « portefeuille à long terme et SI d’études »
Sébastien LEPAUL, 01.78.19.38.73 / 06.62.37.43.22 sebastien.lepaul@edf.fr
Olivier BEAUDE, olivier.beaude@edf.fr
Equipe « méthodes et outils d’optimisation »
Rodolphe GRISET, rodolphe.griset@edf.fr
Cécile ROTTNER, cecile.rottner@edf.fr
Bibliographie
[1] Benders, J.F. Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4, 238–252 (1962). https://doi.org/10.1007/BF01386316
[2] Conejo, A. Solving Certain Types of Large-Scale Scheduling Problems via Hybrid Decomposition, Conference EURO 2022, ESPOO.
