Ce stage concerne l'application directe de méthodes de machine learning pour la résolution de problèmes d'optimisation combinatoire multi-objectifs. L'objectif est de pouvoir prédire la fréquence d'apparition d'une variable dans les solutions Pareto-optimales, afin d'ensuite utiliser des méthodes d'échantillonnage pour obtenir l'ensemble des solutions Pareto-optimales. L'apprentissage se base sur des techniques d'apprentissage profond spécifiques pour l'apprentissage de graphes, les réseaux neuronaux de graphes (GNN). Les GNNs sont des structures très prometteuses pour accélérer la résolution de problèmes combinatoires, notamment dans le cas d'applications industrielles, où de nombreuses instances de problèmes, avec très peu de variations dans les données, doivent être résolues [1]. Les GNNs permettent de créer un lien entre les instances et les solutions, sans qu'il ne soit nécessaire d'utiliser un solveur, dont le temps d'exécution peut être long sur des instances difficiles. L'idée du projet est d'appliquer les GNNs à la résolution de problèmes combinatoire multi-objectifs, ce qui n'a encore été jamais pratiquement réalisé (1 seule publication en 2023 pour un problème de localisation [2]).
Objectifs du stage :
- Étude approfondie des GNNs : le stagiaire se familiarisera avec les concepts fondamentaux des réseaux de neurones de graphes, en mettant l'accent sur leur capacité à traiter des données structurées comme les graphes, permettant de modéliser de nombreux problèmes d'optimisation combinatoire. Un état de l'art sur l'application des GNNs en optimisation combinatoire sera réalisé.
- Implémentation et entraînement des GNNs : le stagiaire mettra en oeuvre un modèle de GNN adapté à la résolution de problèmes d'optimisation combinatoire multi-objectifs. L'accent sera mis sur l'entraînement du modèle en utilisant des ensembles de données représentatifs, c'est-à-dire des instances résolues de différents problèmes combinatoire multi-objectifs.
- Évaluation des Performances : le stagiaire évaluera les performances du modèle GNN sur différentes instances de problèmes d'optimisation combinatoire multi-objectifs. Les résultats obtenus seront comparés à ceux obtenus par des approches traditionnelles de résolution (exactes et heuristiques).
Lieu : LIP6, Sorbonne Univeristé
Encadrants : Thibaut Lust, Pierre-Henri Wuillemin
Références :
[1] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021.
[2] S. Liu, X. Yan, and Y. Jin. End-to-end pareto set prediction with graph neural networks for multi-objective facility location. In M. Emmerich, A. Deutz, H. Wang, A.V. Kononova, B. Naujoks, K. Li, K. Miettinen, and I. Yevseyeva, editors, Evolutionary Multi-Criterion Optimization, pages 147–161, Cham, 2023. Springer Nature Switzerland.