constraint satisfaction problems are combinatorial NP-complete problems. These problems can be solved by two kinds of methods :
- tree search, which constructs a search tree and at each tree node checks the local consistency to (try to) reduce the number of possibles combinations ;
- local search, which explores the search space in an incomplete manner, modifying iteratively and localy an initial combination.
A hybrid generic algorithm combining these two methods has been proposed in [PV04]. The idea is to structure the search space as a graph and not as a tree, each node reprensenting a partial consistant instanciation. This algorithm is parametrized and can be instanciated in different solvers such as tree search and local search but also as intermediary solvers allowing to explore the search space in a new way.

We propose to study the possibilities of integrating CSP decomposition techniques in this generic algorithm. (Hyper)tree CSP decompositions exploit the CSP structure to provide better complexity bounds thanks to the affectation heuristic, which keeps track of the independent sub-problems of the CSP and thus saving (no)goods to avoid redundancy. These techniques allowed for better experimental results of algorithms based on a treee search.
Firstly we want to have a framework which integrates decomposition techniques in the generic algorithm of [PV04], combining all methods of decomposition and (no)good recording. Then, we want to study complexity bounds according to different parametrization. Finally, we want to propose new instanciations of this generic algorithm using decomposition techniques to speed up the resolution of structured CSPs.
Efficiency of these new instanciations will be evaluated experimentally on structured instances such frequency allocation problems.