EVARISTE - Évolution d’arbres de recherche et d’heuristiques d’ordre pour les problèmes sous contraintes

Coordinateur : Adrien Goëffon, Université d’Angers

Partenaire : Bilel Derbel, Université de Lille, CRIStAL

Équipe : BONUS du Groupe Thématique : OPTIMA

Dates : 2025 - 2029

Résumé :

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’u ordre optimal sera mis en lien direct avec un problème d’optimisation complexe (problème de géométrie des distances ) 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.

Abstract :

The EVARISTE project proposes a new approach to optimize solution exploration strategies used by exact resolution methods dedicated to solve combinatorial constraint satisfaction problems. These methods generally rely on building a decision tree that gradually constructs a solution, satisfying the various constraints of the problem and potentially optimizing optimizing an objective. By using concepts and methodologies from evolutionary algorithms and fitness landscapes analysis, the goal is to develop more effective order heuristics for the decision variables of the problem and the selection of their values for classical tree-based exploration of the solution space. This involves shifting the focus from solving combinatorial problems int the initial search space to exploring the space of heuristics with appropriate metrics, leading to the discovery of new strategies for solvers. The fundamental challenge of determining an optimal sequence will be intricately connected to a challenging optimization issue known as the ’distance geometry problem’, which will play a central role in our approach.
Ultimately, this work seeks to provide an alternative and explanatory approach to constraint solvers, which are frequently treated as black-box systems, using analytical tools and identified characteristics.