SAT encoding and CSP reduction for interconnected alldiff constraints

Frederic Lardeux, Eric Monfroy, Frederic Saubion, Broderick Crawford, Carlos Castro

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

8 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Título de la publicación alojadaMICAI 2009
Subtítulo de la publicación alojadaAdvances in Artificial Intelligence - 8th Mexican International Conference on Artificial Intelligence, Proceedings
Páginas360-371
Número de páginas12
DOI
EstadoPublicada - 2009
Publicado de forma externa
Evento8th Mexican International Conference on Artificial Intelligence, MICAI 2009 - Guanajuato, México
Duración: 9 nov 200913 nov 2009

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen5845 LNAI
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia8th Mexican International Conference on Artificial Intelligence, MICAI 2009
País/TerritorioMéxico
CiudadGuanajuato
Período9/11/0913/11/09

Huella

Profundice en los temas de investigación de 'SAT encoding and CSP reduction for interconnected alldiff constraints'. En conjunto forman una huella única.

Citar esto