Stage EDF R&D - Programmation mathématique pour l'optimisation moyen-terme des vallées hydrauliques
Forum 'Stages' - Sujet créé le 2023-10-26 par Cécile Rottner
Contexte
L’optimisation des réservoirs hydrauliques est un des problèmes à fort enjeu pour EDF. En effet, près de 50 % de l’énergie renouvelable produite en France provient des centrales hydrauliques. L’optimisation des réservoirs hydrauliques est faite à plusieurs horizons de temps et permet de gérer efficacement la production hydraulique pour satisfaire la demande à moindre coût face à un avenir incertain.
Historiquement, pour l’horizon moyen terme, ce problème est résolu par un outil développé à la R&D, se basant sur une programmation dynamique stochastique où les problèmes de transition sont modélisés et résolus par programmation linéaire (continue ou en nombres entiers). Récemment, la R&D a développé une bibliothèque permettant de résoudre plus efficacement ces problèmes de transition, qui peuvent se modéliser comme des problèmes de flot à coût minimum (aussi appelés min-cost flow ou MCF). Un algorithme en temps polynomial est déployé et permet de modéliser une bonne partie des cas rencontrés pour un gain de temps de calcul considérable. Cependant, cette modélisation en flot ne permet pas d’encapsuler certaines contraintes continues ou entières. Pour répondre à ce problème, une autre bibliothèque, appelée « SolHyd », a été développée. SolHyd permet de prendre en compte les contraintes continues en les dualisant et en utilisant une méthode de faisceaux pour résoudre le problème d’optimisation résultant. Cette bibliothèque propose aussi une méthode de Branch and Bound pour prendre en compte les variables discrètes.
Un premier stage a permis de confirmer l’efficacité de ce schéma et montre des résultats prometteurs, notamment via des heuristiques duales permettant d’éviter un trop grand nombre d’itérations coûteuses dans les faisceaux. Néanmoins, des marges d’amélioration et d’adaptation de cet algorithme existent encore : stratégie de branchement, heuristiques primales, extension des heuristiques duales, travail sur la formulation et proposition d’éventuelles coupes…
Objectif
L'objectif du stage est de pouvoir passer à l’échelle avec cette méthode sur les instances les plus difficiles. Le stagiaire sera amené à améliorer l’algorithme pour répondre aux exigences opérationnelles en temps de calcul, en travaillant sur les 3 niveaux de l’algorithme : B&B, méthode des faisceaux, problème de flot à coût minimum.
Les pistes identifiées à ce jour sont les suivantes :
- Heuristiques primales efficaces notamment en présence de contraintes discrètes (« minimum technique ») qui peuvent rendre difficile l’obtention d’une solution faisable
- Extension des heuristiques duales aux contraintes dites de « gradients » (variation de débit limitée d’un pas de temps à l’autre)
- En complément, travail sur la formulation du problème et mise au point de coupes pour améliorer la qualité de la relaxation linéaire qui permettrait d’envisager une résolution frontale (par simplexe ou point intérieur) des relaxations linéaires
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 : de 1100 à 1400€ environ par mois, en fonction du 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.
Sandie BALAGUER
Cécile ROTTNER