Le 26/10/2023 par CecileR :
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. L’équipe « méthodes d’optimisation » (R36), dans laquelle sera intégré le stagiaire, est chargée d’appuyer les autres équipes du département en s’assurant que les outils de la R&D bénéficient des dernières avancées méthodologiques. Dans ce cadre, elle appuie l’équipe Portefeuille à long terme et SI d’études » (R31) qui étudie les nouveaux mix énergétiques sur un horizon long terme au sein des systèmes électriques mondiaux.
Les problèmes résolus dans ce cadre correspondent à des problèmes d’optimisation linéaires stochastiques de très grandes tailles à variables mixtes. Ils présentent généralement deux niveaux de décisions : un ensemble des décisions d’investissements constituent les décisions de premier niveau et structurent le parc de production, dont on cherche à valider la capacité à satisfaire la demande et à évaluer le coût dans un futur incertain. La matrice des contraintes de ce type de problème présente une structure diagonale par blocs avec variables liantes qu’il est possible de décomposer en utilisant une décomposition de Benders [1]. Cette décomposition, introduite pour la résolution de grands programmes linéaires, s’appuie sur la dualité forte pour projeter la fonction de coût du second niveau en terme de contraintes portant sur les décisions de premier niveau. Si des résultats intéressants ont été obtenu par la R&D d’EDF en exploitant ce type d’algorithme [2], ils présentent des défauts de convergences nécessitant des techniques avancées de stabilisation pour les rendre efficaces [3] et ont souvent comme point limitant le temps de résolution des sous-problèmes.
Récemment, de nouvelles améliorations de l’algorithme de Benders ont été proposées dans la littérature en exploitant la structure des problèmes traités pour limiter le nombre de résolutions des sous-problèmes et accélérer la convergence. L’algorithme de Benders by batch [4] propose de ne résoudre qu’un faible sous-ensemble de scénarios pour détecter que la solution proposée pour le problème maître ne peut pas être optimale, et si c’est le cas réaliser une mise à jour des décisions de premier niveau. Les algorithmes basés sur des oracles adaptatifs [5] exploitent quant à eux la structure similaire de certains sous-problèmes afin de pouvoir générer des coupes à partir des informations obtenues lors de la résolution des autres sous-problèmes.
L’objectif du stage sera d’étudier ces nouvelles avancées et analyses les possibilités d’application aux problèmes traités dans l’équipe R31 de la R&D. Le stagiaire réalisera les tâches suivantes :
Pour ces travaux le stagiaire pourra s’appuyer sur des travaux précédents de la R&D : modèles épurés et maquette de Benders. Ces travaux seront également réalisés en parallèle d’un autre stage visant à analyser la structure des problèmes rencontrés par l’équipe R31. Des interactions régulières entre ces deux stages seront menées.
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] Griset, R., Bendotti, P., Detienne, B., Porcheron, M., ?en, H., & Vanderbeck, F. (2022). Combining Dantzig-Wolfe and Benders decompositions to solve a large-scale nuclear outage planning problem. European Journal of Operational Research, 298(3), 1067-1083.
[3] Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), 801-817.
[4] Blanchot, X., Clautiaux, F., Detienne, B., Froger, A., & Ruiz, M. (2023). The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs. European Journal of Operational Research, 309(1), 202-216.
[5] Mazzi, N., Grothey, A., McKinnon, K., & Sugishita, N. (2021). Benders decomposition with adaptive oracles for large scale optimization. Mathematical programming computation, 13(4), 683-703.
Conditions matérielles :
Lieu du stage : EDF Lab, 7 Boulevard Gaspard Monge 91120 Palaiseau.
Le site est accessible par transports en commun.
Durée : 6 mois à partir de mars/avril 2023
Rémunération : Les stagiaires sont rémunérés en fonction du niveau d’étude et de la formation préparée.
Connaissances requises : Troisième année d’école d’ingénieur / Master 2 en optimisation.
Profil : Programme linéaire en nombres entiers, algorithmes de décomposition, programmation en python ou C++
Renseignements complémentaires :
Rodolphe GRISET, e-mail: rodolphe.griset@edf.fr
Cécile ROTTNER, e-mail : cecile.rottner@edf.fr
