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

SAT Encoding and CSP Reduction for Interconnected Alldiff Constraints

Abstract :

Constraint satisfaction problems (CSP) or Boolean satisfiability problem (SAT) are two well known paradigm to model and solve combinatorial problems. Modeling and resolution of CSP is often strengthened by global constraints (e.g., Alldiff constraint). This paper highlights two different ways of handling specific structural information: a uniform propagation framework to handle (interleaved) Alldiff constraints with some CSP reduction rules; and a SAT encoding of these rules that preserves the reduction properties of CSP.

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03350614
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : vendredi 18 mars 2022 - 16:00:52
Dernière modification le : lundi 14 novembre 2022 - 02:42:07
Archivage à long terme le : : dimanche 19 juin 2022 - 18:05:08

Fichier

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

Identifiants

Collections

Citation

Frédéric Lardeux, Eric Monfroy, Frédéric Saubion, Broderick Crawford, Carlos Castro. SAT Encoding and CSP Reduction for Interconnected Alldiff Constraints. 8th Mexican International Conference on Artificial Intelligence, MICAI 2009, 2009, Guanajuato, Mexico. pp.360-371, ⟨10.1007/978-3-642-05258-3_32⟩. ⟨hal-03350614⟩

Partager

Métriques

Consultations de la notice

12

Téléchargements de fichiers

8