thesis

Calcul et exploitation de recouvrements acycliques pour la résolution de (V)CSP

Defense date:

Jan. 1, 2007

Edit

Institution:

Aix-Marseille 3

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

This work aims to make efficient structural methods for solving problems represented within the Constraint Satisfaction Problem (CSP) formalism or the Valued CSP one. Even though these techniques offer the best theoretical time complexity bounds, they are often totally inefficient in practice because of the large amount of memory space required and their rigidity in the variable ordering. We define new techniques for computing treedecompositions which allow doing a good tradeoff between the space memory required and the time complexity bound. This tradeoff is extended to the variable ordering heuristic. We propose two new methods which allow using more efficient variable orders thanks to the notion of acyclic coverings which generalizes the treedecomposition. Finally, we define a generic enumerative algorithms for solving CSP framework based on a set of separators, which captures many well known structural methods.

Abstract FR:

L'objectif de ce travail est de rendre opérationnelles les méthodes structurelles de résolution de problèmes représentés dans les formalismes CSP (problème de satisfaction de contraintes) ou CSP valué. Ces techniques offrent les meilleures bornes de complexité en temps, mais se révèlent souvent inefficaces en pratique à cause de l'espace mémoire requis et de leur rigidité dans l'ordre d'affectation des variables. Nous avons défini de nouvelles techniques de calcul de décompositions arborescentes permettant un bon compromis espace/temps. Ensuite, ce compromis est élargi à l'heuristique de choix de variables. Nous proposons deux méthodes qui utilisent des heuristiques efficaces grâce à la notion de recouvrement acyclique qui généralise celle de décomposition arborescente. Enfin, nous avons défini un schéma générique d'algorithmes énumératifs pour la résolution de CSP basé sur un ensemble de séparateurs du problème, qui capture un large éventail des méthodes structurelles connues.