Skip to Main content Skip to Navigation

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 metadata

Cited literature [432 references]  Display  Hide  Download
Contributor : Cyril Terrioux Connect in order to contact the contributor
Submitted on : Tuesday, January 28, 2020 - 12:00:41 PM
Last modification on : Thursday, July 14, 2022 - 4:11:23 AM
Long-term archiving on: : Wednesday, April 29, 2020 - 2:12:05 PM


Files produced by the author(s)


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


  • HAL Id : tel-02457731, version 1


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⟩



Record views


Files downloads