Séminaire de Thomas Pontoizeau

Le célèbre problème de graphes Maximum Independent Set fait l'objet de nombreuses méthodes exactes ou approchées de résolution. En termes de jeu, il peut se formuler comme un jeu séquentiel à un joueur, ce qui ouvre la porte à l'utilisation de méthodes d'apprentissage par imitation : une recherche Monte Carlo joue le rôle d'expert, et un réseau de neurones de graphes (GNN) apprend à reproduire ses décisions. Après une introduction aux GNN, je présenterai un framework fondé sur ce mécanisme d'imitation learning pour apprendre à résoudre ce problème, les leviers qui ont permis de guider efficacement l'apprentissage, et comment cette approche a pu révéler la structure de l'espace des solutions. Enfin, je proposerai un tour d'horizon des approches modernes utilisant les GNN pour l'optimisation combinatoire sur les graphes.