Description du sujet de thèse

L'objectif de l'optimisation combinatoire est d'explorer un espace fini d'éléments et de trouver celui qui optimise un critère donné. Pour la résolution de problèmes d’optimisation combinatoire, les approches exactes ont la capacité de trouver la solution optimale tout en prouvant qu'aucune meilleure solution ne peut exister. Elle s’appuie pour cela sur des méthodes de recherche arborescente permettant une exploration efficace de l’espace de recherche.
Pour la résolution de problèmes combinatoires de grande taille, la conception de méthodes d’apprentissage pour déterminer des heuristiques de branchement dans les méthodes de recherche arborescente constitue un domaine de recherche important dans l’objectif de converger vers une solution en un temps raisonnable.
La programmation par contraintes est un paradigme généraliste de résolution de problèmes combinatoires, mais elle est grandement dépendante des choix effectués lors des branchements du solveur. La finalité de cette thèse est d’améliorer l’obtention d’heuristiques de branchement génériques au sein de solveur par contraintes. Les pistes envisagées portent sur l’apprentissage par renforcement intégré à des solveurs génériques ou combiné avec des méthodes de Monte-Carlo ainsi que sur l’intégration de Graph Neural Networks pour construire efficacement des solutions réalisables.

Contexte de travail

Cette thèse se déroulera en cotutelle entre l'INSA de Toulouse (France) en Polytechnique Montréal (Québec, Canada). Les équipes de recherche impliquées sont : groupe CORAIL (Polytechnique Montréal), équipes ROC et RIS (LAAS-CNRS). Des séjours en alternance entre les deux établissements seront précisés dans la convention de cotutelle.

Le poste se situe dans un secteur relevant de la protection du potentiel scientifique et technique (PPST), et nécessite donc, conformément à la réglementation, que votre arrivée soit autorisée par l'autorité compétente du MESR.