Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
Communication dans un congrès

From Set Constraint Models to SAT Instances

Abstract : On the one hand, Constraint Satisfaction Problems(CSP) are a declarative and expressive approach for modelingproblems. On the other hand, propositional satisfiability problem(SAT) solvers can handle huge SAT instances up to millions ofvariables and clauses. In this article, we present an approach fortaking advantage of both CSP modeling and SAT solving. Ourtechnique consists in expressively modeling set constraint prob-lems as CSPs that are automatically treated by some reductionrules to remove values that do not participate in any solution.These reduced CSPs are then encoded into ”good” SAT instancesthat can be solved by standard SAT solvers. We illustrate ourtechnique on the Sports Tournament Scheduling problem, andwe show that we obtain competitive results compared to an ad-hoc solver. Our technique is simpler, more expressive, and lesserror-prone than direct SAT modeling. The SAT instances thatwe automatically generate are rather small and can efficientlybe solved up to huge instances. Moreover, the reduction phaseenables to push back the limits and treat even larger problems.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-02709491
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : mercredi 13 octobre 2021 - 11:17:18
Dernière modification le : lundi 14 novembre 2022 - 02:42:07
Archivage à long terme le : : vendredi 14 janvier 2022 - 18:47:02

Fichier

PID4450039.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02709491, version 1
  • OKINA : ua15345

Citation

Frédéric Lardeux, Eric Monfroy. From Set Constraint Models to SAT Instances. 28th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2016, San Jose, United States. ⟨hal-02709491⟩

Partager

Métriques

Consultations de la notice

28

Téléchargements de fichiers

28