Thèse Évolution et Paysages d'Heuristiques d'Ordre pour la Résolution de Problèmes Combinatoires Sous Contraintes H/F - Doctorat.Gouv.Fr

Établissement : Université d'Angers École doctorale : École doctorale Mathématiques et Sciences et Technologies du numérique, de l'Information et de la Communication Laboratoire de recherche : LABORATOIRE D'ETUDE ET DE RECHERCHE EN INFORMATIQUE D'ANGERS Direction de la thèse : Adrien GOEFFON ORCID 0000-0001-9688-0222 Date limite de candidature : 2026-05-30T00:00:00
Cette thèse s'inscrit dans le domaine de la résolution de problèmes combinatoires sous contraintes, un champ central de l'informatique décisionnelle utilisé notamment pour la planification, la satisfaction de contraintes logiques ou l'optimisation. Ces problèmes sont généralement résolus par des méthodes de recherche arborescente dont l'efficacité dépend fortement des heuristiques d'ordre, c'estàdire de la manière dont les variables sont choisies et traitées au cours de la recherche.

Or, le choix de ces heuristiques repose aujourd'hui largement sur des pratiques empiriques, ce qui constitue un frein majeur à l'amélioration des performances des solveurs. L'objectif général de cette thèse est de mieux comprendre, analyser et prédire l'efficacité des heuristiques d'ordre en fonction des caractéristiques des instances traitées.

Dans le cadre du projet ANR EVARISTE, le travail proposé se concentre sur l'étude des ordres de variables pour la résolution de problèmes booléens, en mobilisant le cadre théorique des paysages de fitness. Ce formalisme permet de représenter l'espace des heuristiques et d'associer à chacune une mesure de qualité reflétant ses performances, afin d'en analyser la structure globale.

Le projet de thèse sera réalisé au sein d'un laboratoire de recherche disposant des compétences scientifiques nécessaires et d'un encadrement assuré par des enseignantschercheurs permanents. Le doctorant ou la doctorante bénéficiera de l'intégration à une équipe de recherche active et d'un environnement scientifique stimulant.

Les moyens matériels comprennent l'accès à un poste de travail dédié, aux infrastructures informatiques et aux outils logiciels nécessaires aux expérimentations et analyses. Le financement doctoral couvrira l'ensemble de la durée de la thèse, avec des moyens complémentaires permettant la participation à des conférences, missions scientifiques et actions de valorisation liées au projet de recherche.

La thèse vise à :
- définir et formaliser des espaces représentant les heuristiques d'ordre et des fonctions de fitness pertinentes pour évaluer leur efficacité ;
- analyser les propriétés de ces paysages afin d'identifier des heuristiques performantes, robustes et interprétables, y compris à grande échelle ;
- étudier les liens entre les propriétés des instances de problèmes et celles des heuristiques, dans le but de faire émerger de nouvelles stratégies de résolution, notamment au sein d'approches d'hyperheuristiques.

À terme, ce travail contribuera à une meilleure compréhension théorique des mécanismes de résolution sous contraintes et ouvrira la voie à des méthodes plus systématiques et prédictives pour le choix automatique d'heuristiques dans les solveurs combinatoires.