Watched literals for constraint propagation in MINION

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Citations (Scopus)

Abstract

Efficient constraint propagation is crucial to any constraint solver. We show that watched literals, already a great success in the satisfiability community, can be used to provide highly efficient implementations of constraint propagators. We describe three important aspects of watched literals as we apply them to constraints, and how they are implemented in the MINION constraint solver. We show three successful applications of to constraint propagators: the sum of Boolean variables; GAC for the 'element' constraint; and GAC for the 'table' constraint.

Original languageEnglish
Title of host publicationPRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2006
EditorsF Benhamou
Place of PublicationBerlin
PublisherSpringer
Pages182-197
Number of pages16
ISBN (Print)3-540-46267-8
DOIs
Publication statusPublished - 2006
Event12th International Conference on Principles and Practice of Constraint Programming (CP 2006) - Nantes
Duration: 25 Sept 200629 Sept 2006

Publication series

NameLecture Notes in Computer Science
Volume4204

Conference

Conference12th International Conference on Principles and Practice of Constraint Programming (CP 2006)
CityNantes
Period25/09/0629/09/06

Fingerprint

Dive into the research topics of 'Watched literals for constraint propagation in MINION'. Together they form a unique fingerprint.

Cite this