Skip to Main content Skip to Navigation
Theses

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

Abstract : 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.
Complete list of metadatas

Cited literature [432 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/tel-02457731
Contributor : Cyril Terrioux <>
Submitted on : Tuesday, January 28, 2020 - 12:00:41 PM
Last modification on : Monday, March 30, 2020 - 8:45:10 AM
Long-term archiving on: : Wednesday, April 29, 2020 - 2:12:05 PM

File

171220_KANSO_477ifvx988a843exw...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

  • HAL Id : tel-02457731, version 1

Citation

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⟩

Share

Metrics

Record views

108

Files downloads

36