Evolution d'arbres de recherche et d’heuristiques d'ordre pour les problèmes sous contraintes – EVARISTE

Dans le contexte de la résolution de problème combinatoires sous contraintes, le projet EVARISTE propose une nouvelle approche pour optimiser les stratégies d’exploration de solutions utilisées par les méthodes de résolution exactes. Ces méthodes reposent en général sur la construction d’un arbre de prises de décisions consistant à construire progressivement une solution, satisfaisant les diverses contraintes du problème et optimisant un objectif éventuel. En s’appuyant sur l’algorithmique évolutionnaire et l’analyse des paysages de recherche, l’objectif est de faire émerger des heuristiques d’ordres sur les variables de décision du problème et de choix de leurs valeurs plus efficaces pour l’exploration arborescente classique de l’espace des solutions. Il s’agit donc de transposer la question de la résolution de problèmes combinatoires dans l’espace initial des solutions vers une exploration de l’espace des heuristiques avec des métriques appropriées, induisant la découverte de nouvelles stratégies pour les solveurs. Le problème sous-jacent de recherche d’un ordre optimal sera mis en lien direct avec un problème d’optimisation complexe (problème de géométrie des distance) qui servira ainsi de pivot à notre démarche. Enfin, la méthodologie suivie vise, au travers des outils d’analyse et des propriétés identifiées, la proposition d’une approche explicative alternative des solveurs de contraintes, souvent utilisés en mode boite noire.