SAT Encoding and CSP Reduction for Interconnected Alldiff Constraints

TitreSAT Encoding and CSP Reduction for Interconnected Alldiff Constraints
Type de publicationCommunication
TypeCommunication avec actes dans un congrès
Année2009
LangueAnglais
Date du colloque2009/01/01
Titre du colloque8th Mexican International Conference on Artificial Intelligence, MICAI 2009
Titre des actes ou de la revueAdvances in Artificial Intelligence
Volume5845
Pagination360 - 371
AuteurLardeux, Frédéric , Monfroy, Eric, Saubion, Frédéric , Crawford, Broderick, Castro, Carlos
PaysMexique
EditeurSpringer
VilleGuanajuato
ISBN978-3-642-05257-6 / 978-3-642-05258-3
Mots-clésArtificial Intelligence (incl. Robotics), Computer Imaging, Vision, Pattern Recognition and Graphics, Data Mining and Knowledge Discovery, image processing and computer vision, pattern recognition, Simulation and Modeling
Résumé en anglais

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.

Notes

Date du colloque : 11/2009

URL de la noticehttp://okina.univ-angers.fr/publications/ua4479
DOI10.1007/978-3-642-05258-3_32
Lien vers le document en ligne

http://dx.doi.org/10.1007/978-3-642-05258-3_32