Le 16/10/2024 par Rodolphe Griset :
« Nouvelles approches génériques pour l’obtention de solutions en exploitant une méthode de génération de colonnes »
Descriptif :
L’équipe Méthodes et Optimisation de la R&D d’EDF développe un ensemble d’outils et d’algorithmes permettant d’améliorer l’organisation opérationnelle du groupe EDF. Dans le cadre de ces activités, cette équipe a développé au fil du temps un ensemble de briques logicielles implémentant des méthodes d’optimisation génériques. Parmi ces méthodes, la génération de colonnes, permettant une génération dynamique des variables associées à un problème [1], a connu de grands succès dans le monde industriel et fait l’objet de nombreux stages au sein de la R&D. Cependant, cette méthode avancée demande un investissement important pour son implémentation et de nombreux réglages pour être performante face aux solveurs commerciaux. De plus, elle est la plu s efficace lorsqu’elle est appliquée à des problèmes linéaires en nombres entiers et combinée avec une heuristique primale adaptée à cette méthode.
Pour surmonter ces difficultés et rendre ces méthodes plus accessibles sur des problèmes industriels, la R&D a lancé, depuis 2023, l’internalisation d’une bibliothèque de génération de colonnes en se basant sur la bibliothèque open-source ColumnGenerationSolver. Cette bibliothèque possède des heuristiques génériques basées sur des méthodes arborescentes gloutonnes ou intégrant une diversification qui ont montré de bons résultats dans la littérature [2] et assurent l’obtention d’une solution réalisable au problème initial. Dans le cadre de ce stage, nous proposons d’explorer de nouvelles approches génériques pour obtenir des solutions primales. Ces approches se basent sur d’autres algorithmes de recherche arborescente ou sur des généralisations d’approches développ ées pour des applications spécifiques. Les nouvelles approches seront testées sur des problèmes de la littérature scientifique ainsi que sur les problèmes industriels d’optimisation des plannings d’arrêts des unités de production d’EDF.
Objectif
Le stagiaire commencera par prendre en main la bibliothèque de génération de colonnes et par l’implémentation d’un ensemble de problèmes de la littérature au sein de celle-ci. Il s’intéressera ensuite à de potentielles nouvelles approches génériques pour l’obtention de solutions primales qui seront testées sur des instances épurées correspondant aux problèmes traités par EDF.
Ce stage sera co-encadré entre EDF et Artelys.
Références
[1] Desrosiers, J., & Lübbecke, M. E. (2005). A primer in column generation. In Column generation (pp. 1-32). Boston, MA: Springer US.
[2] 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.
Conditions matérielles :
Lieu du stage : EDF R&D ; 7, Boulevard Gaspard Monge ; 91120 Palaiseau. Le site est accessible par transports en commun. Durée : 6 mois. Rémunération : selon école et niveau.
Niveau : niveau M2
Profil : Master recherche opérationnelle (Programmation linéaire en nombres entiers, algorithmes de décompositions)
Programmation C++
Date de début : Mars-Avril 2025
Durée : 6 mois
Renseignements complémentaires :
Rodolphe Griset E-mail: rodolphe.griset@edf.fr
Alex Fauduet E-mail: Alex.fauduet@edf.fr
