Etude des Mécanismes de Transformation de Modèles CSP/SAT

TitreEtude des Mécanismes de Transformation de Modèles CSP/SAT
TypeThèse de doctorat
AuteursVasconcellos Claudia
DirecteursLardeux Frédéric, Barichard Vincent, Lesaint David, de Giorgis Ricardo Soto, Piette Cédric, Vareilles Elise
Année2020
URLhttps://dune.univ-angers.fr/fichiers/16010061/202014831/fichier/14831F.pdf
Mots-clésCSP vers SAT, Encodage Hybride, Encodage SAT, Problème de Satisfaction de Contraintes, SAT
Résumé

La plupart des problèmes combinatoires peuvent être formulés comme des CSP (Constraint Satisfaction Problems). Un CSP est défini par des variables et des contraintes entre ces variables. Résoudre un CSP consiste à trouver une affectation des variables qui satisfasse les contraintes. L’une des principales forces des CSP est la déclarativité : les variables peuvent être de plusieurs types ainsi que les contraintes. D’un autre côté, le problème de satisfiabilité en logique propositionnelle (SAT) est réduit, en terme de déclarativité, à des variables booléennes et des formules propositionnelles. Cependant, les solveurs SAT sont maintenant capables de manipuler d’énormes instances.
Il semble donc intéressant de 1) coder les CSP en SAT afin de bénéficier de l’expressivité et de la déclarativité des CSP et de la puissance des solveurs SAT, et 2) introduire plus de sémantique du problème initial dans SAT.
Cette thèse analyse les encodages CSP vers SAT afin de mieux comprendre les facteurs clés qui déterminent leurs caractéristiques ainsi que leur impact sur la résolution. Une première étude analyse l’impact des variables venant du modèle CSP sur l’heuristique de branchement des solveurs SAT. Une étude sur la manière de transférer de l’information sémantique du modèle CSP au modèle SAT est aussi réalisée. Un travail est aussi réalisé sur l’intégration dans le modèle SAT d’un propagateur CSP pour l’addition. Pour finir, nous proposons l’encodage Abacus, un nouvel encodage SAT qui établit un bon compromis entre la taille des instances générées et l’efficacité de la résolution.
Résumé en anglais

Most of combinatorial problems can be formulated as a CSP (Constraint Satisfaction Problem). A CSP is defined by its variables and the constraints between these variables. Solving a CSP means to find an instantiation of variables such that all constraints in the model are satisfied. CSP is known for being declarative: it has different types of variables, so as constraints. On the other hand, the propositional satisfiability problem (SAT) is restricted to Boolean variables and propositional formulas. Nevertheless, SAT solvers are well-known for their power to handle huge instances. Then, it seems worth it to: 1) encoding CSP into SAT to take advantage of CSP expressiveness and SAT efficiency, and 2) add more CSP semantics into SAT. This thesis studies the CSP to SAT encodings to understand the factors that determine their characteristics and their impact in the SAT solving. A first study evaluates the impact of CSP decision variables in the SAT branching during solving, and how this semantic information can be transferred from CSP model to the SAT instance. A second study evaluates a CSP propagator for the addition in a SAT(CNF) formula. Finally, we propose the Abacus encoding, a new hybrid encoding that provides a good trade-off between the instance size and the resolution effectiveness.
Langue de rédactionFrançais
Diplôme

Thèse de doctorat
Date de soutenance2020-12-15
EditeurUniversité d'Angers
Place PublishedAngers
Libellé UFR

Collège doctoral
personnalisé5

Ecole doctorale Mathématiques et Sciences et Technologies de l'Information et de la Communication
personnalisé6

Laboratoire d'Etude et de Recherche en Informatique d'Angers
personnalisé7

Informatique