Résolution des problèmes (W)CSP et #CSP par approches structurelles : Calcul et exploitation dynamique de décompositions arborescentes - Aix-Marseille Université Accéder directement au contenu
Thèse Année : 2017

Solving (W)CSP and #CSP problems by structural approaches : computation and dynamic exploitation of tree decompositions

Résolution des problèmes (W)CSP et #CSP par approches structurelles : Calcul et exploitation dynamique de décompositions arborescentes

Résumé

The importance of CSP, WCSP and #CSP problems is reflected by the considerable amount of theoretical and practical work of which they are subject in artificial intelligence and far beyond. Their difficulty is such that they belong respectively to the NP-complete, NP-hard and #P-complete classes. Hence, the methods that are able to solve efficiently their instances have a complexity in exponential time. The research works of this thesis focus on the solving methods exploiting the notion of tree-decomposition. These methods have aroused a keen interest from the scientific community because they are able to solve some classes of instances in polynomial time. Nevertheless, in practice, they have not shown yet their full efficiency given the quality of the used decomposition that takes only into account a purely structural criterion, its width. First, we propose a new generic framework for computing decompositions which has the virtue of computing decompositions that capture more relevant parameters in the context of solving than the width. Then, we propose a dynamic exploitation of the decomposition during the solving for (W)CSP problems. The modification of the decomposition during the solving aims to adapt the decomposition to the nature of the instance. Finally, we propose a new counting algorithm that exploits the decomposition in a different way than standard methods in order to avoid unnecessary computations. All the contributions have been evaluated and validated experimentally.
L'importance des problèmes CSP, WCSP et #CSP est reflétée par la part considérable des travaux, théoriques et pratiques, dont ils font l'objet en intelligence artificielle et bien au-delà. Leur difficulté est telle qu'ils appartiennent respectivement aux classes NP-complet, NP-difficile et #P-complet. Aussi, les méthodes qui permettent de résoudre efficacement leurs instances ont une complexité en temps exponentielle. Les travaux de recherche de cette thèse se focalisent sur les méthodes de résolution exploitant la notion de décomposition arborescente. Ces méthodes ont suscité un vif intérêt de la part de la communauté scientifique du fait qu'elles soient capables de résoudre en temps polynomial certaines classes d'instances. Cependant, en pratique, elles n’ont pas encore montré toute leur efficacité vu la qualité de la décomposition employée ne prenant en compte qu'un critère purement structurel, sa largeur. Premièrement, nous proposons un nouveau cadre général de calcul de décompositions qui a la vertu de calculer des décompositions qui capturent des paramètres plus pertinents à l'égard de la résolution que la seule largeur de la décomposition. Ensuite, nous proposons une exploitation dynamique de la décomposition pendant la résolution pour les problèmes (W)CSP. Le changement de la décomposition pendant la résolution vise à adapter la décomposition selon la nature de l’instance. Finalement, nous proposons un nouvel algorithme de comptage qui exploite la décomposition d'une façon différente de celle des méthodes standards afin d'éviter des calculs inutiles. L'ensemble des contributions ont été évaluées et validées expérimentalement.
Fichier principal
Vignette du fichier
171220_KANSO_477ifvx988a843exwlhr304ge_TH.pdf (3.33 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

tel-02457731 , version 1 (28-01-2020)

Licence

Paternité - Pas d'utilisation commerciale - Pas de modification

Identifiants

  • HAL Id : tel-02457731 , version 1

Citer

Hélène Kanso. Résolution des problèmes (W)CSP et #CSP par approches structurelles : Calcul et exploitation dynamique de décompositions arborescentes. Intelligence artificielle [cs.AI]. Aix Marseille Universitè, 2017. Français. ⟨NNT : 2017AIXM0655⟩. ⟨tel-02457731⟩
116 Consultations
265 Téléchargements

Partager

Gmail Facebook X LinkedIn More