Thèse de Loïc Blet


Sujet :
Intégration de techniques de décomposition (hyper)arborescentes dans un cadre générique hybride pour la résolution de problèmes de satisfaction de contraintes.

Date de soutenance : 30/09/2015

Encadrant : Christine Solnon
Co-encadrant : Samba Ndojh Ndiaye

Résumé :

Les problèmes de satisfaction de contraintes (CSP) sont des problèmes combinatoires NP-complets. Ces problèmes peuvent être résolus par deux grandes familles d'approches :
- la recherche arborescente, qui développe un arbre de recherche et, à chaque noeud de l'arbre, vérifie la consistance locale afin de (tenter de) réduire la combinatoire ;
- la recherche locale, qui explore l'espace de recherche de façon incomplète en modifiant itérativement et localement une combinaison initiale.
Un algorithme générique hybride combinant ces deux approches a été proposé dans [PV04]. L'idée est de structurer l'espace de recherche en graphe et non en arbre, chaque noeud correspondant à une instanciation partielle localement consistante. Cet algorithme est paramétré et peut être instancié en différentes approches de résolution telles que la recherche arborescente et la recherche locale, mais aussi en des approches intermédiaires permettant d'explorer l'espace de recherche de façon résolument novatrice.
Nous proposons d'étudier les possibilités d'intégration de techniques de décomposition de CSP dans cet algorithme générique. En effet, les décompositions (hyper)arborescentes exploitent la
structure du CSP afin de garantir les meilleures bornes de complexité théorique grâce à un ordre d'affectation prenant en compte l'indépendance entre parties du CSP et à l'enregistrement de (no)goods pour éviter un grand nombre de redondances. Ces techniques ont permis d'améliorer les performances pratiques des algorithmes basés sur une recherche arborescente.
Un premier objectif du stage est de proposer un cadre d'intégration de ces techniques dans l'algorithme générique de [PV04], combinant toutes les approches de décompositions et l'enregistrement des (no)goods. Un second objectif est d'étudier les bornes de complexité théorique garanties en fonction du paramétrage choisi. Un troisième objectif est de proposer de nouvelles intanciations de cet algorithme générique, correspondant notamment à de nouvelles heuristiques de choix de variables et de retour en arrière, utilisant des techniques de décomposition pour accélérer la résolution de CSP structurés. L'efficacité de ces nouvelles instanciations sera évaluée expérimentalement sur des instances structurées telles que celles des problèmes d'affectation de fréquences.