Algorithm design in discrete constraint optimization under limited resources / Conception par apprentissage d’algorithmes d’optimisation discrète sous contraintes de ressources de calcul limitées

• Directeurs de thèse : Simon de Givry (MIAT, INRAE), Samir Loudni (IMT Atlantique, Nantes), Charles Prud’homme (IMT Atlantique, Nantes)
• Début de thèse : 1er Octobre 2025
• École doctorale : IMT Atlantique
• Établissement : IMT Atlantique
• Financement : ANR GMLaS

Résumé : La Programmation Par Contraintes (PPC) est une discipline de l’Intelligence Artificielle qui vise à proposer des langages de modélisation mathématique permettant d’exprimer des problèmes combinatoires et offrant des algorithmes génériques pour les résoudre. Deux solveurs open-source, choco en Java et toulbar2 en C++, intègrent une collection d’algorithmes collectés depuis plus de vingt ans. La ligne de commande de toulbar2 contient une cinquantaine de paramètres et il existe bien d’autres réglages internes contrôlant le pré-traitement des instances, les algorithmes de recherche et leurs heuristiques. Il en va de même pour le solveur choco. L’amélioration des performances de ces solveurs par un meilleur réglage de leurs paramètres est une clé importante pour la réduction de leur consommation énergétique et leur potentiel embarquabilité.

L’objectif de la thèse est d’étudier de nouvelles stratégies de sélection et de combinaison d’algorithmes capables de traiter des jeux d’instances très hétérogènes en respectant des limites sur les ressources disponibles. Ces limites portent sur le temps de calcul et/ou la mémoire disponible pour effectuer le calcul. Il s’agit alors d’étudier, à limites fixées, qu’elles sont les combinaisons d’algorithmes qui permettent de traiter au mieux un problème d’optimisation discrète quelconque. La thèse commencera par faire un état des lieux des algorithmes disponibles, leurs paramètres, leurs complexités théoriques et pratiques (via des techniques de profiling) pour définir les briques algorithmiques élémentaires et les paramètres pertinents sur lesquelles il sera possible de tester un processus évolutionnaire visant à sélectionner et contrôler une combinaison d’algorithmes adaptés aux instances visées. L’originalité de l’approche sera de prendre en compte dans ce processus les limites imposées en temps et en espace.