Watched literals for constraint propagation in MINION

Ian P. Gent; Christopher Anthony Jefferson; Ian Miguel

doi:10.1007/11889205_15

Watched literals for constraint propagation in MINION

Ian P. Gent, Christopher Anthony Jefferson, Ian Miguel

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	English
Title of host publication	PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2006
Editors	F Benhamou
Place of Publication	Berlin
Publisher	Springer
Pages	182-197
Number of pages	16
ISBN (Print)	3-540-46267-8
DOIs	https://doi.org/10.1007/11889205_15
Publication status	Published - 2006
Event	12th International Conference on Principles and Practice of Constraint Programming (CP 2006) - Nantes Duration: 25 Sept 2006 → 29 Sept 2006

Publication series

Name	Lecture Notes in Computer Science
Volume	4204

Conference

Conference	12th International Conference on Principles and Practice of Constraint Programming (CP 2006)
City	Nantes
Period	25/09/06 → 29/09/06

Access to Document

10.1007/11889205_15

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A. (PI), Gent, I. P. (CoI), Leonhardt, U. (CoI), Mackenzie, A. (CoI), Miguel, I. J. (CoI), Quick, M. (CoI) & Ruskuc, N. (CoI)
EPSRC
1/09/05 → 31/08/10
Project: Standard

Cite this

@inproceedings{e3539d7f4bb941849d4ea521b6f63325,

title = "Watched literals for constraint propagation in MINION",

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.",

author = "Gent, {Ian P.} and Jefferson, {Christopher Anthony} and Ian Miguel",

year = "2006",

doi = "10.1007/11889205_15",

language = "English",

isbn = "3-540-46267-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "182--197",

editor = "F Benhamou",

booktitle = "PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2006",

address = "Netherlands",

note = "12th International Conference on Principles and Practice of Constraint Programming (CP 2006) ; Conference date: 25-09-2006 Through 29-09-2006",

}

Gent, IP , Jefferson, CA & Miguel, I 2006, Watched literals for constraint propagation in MINION. in F Benhamou (ed.), PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2006. Lecture Notes in Computer Science, vol. 4204, Springer, Berlin, pp. 182-197, 12th International Conference on Principles and Practice of Constraint Programming (CP 2006), Nantes, 25/09/06. https://doi.org/10.1007/11889205_15

TY - GEN

T1 - Watched literals for constraint propagation in MINION

AU - Gent, Ian P.

AU - Jefferson, Christopher Anthony

AU - Miguel, Ian

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

U2 - 10.1007/11889205_15

DO - 10.1007/11889205_15

M3 - Conference contribution

SN - 3-540-46267-8

T3 - Lecture Notes in Computer Science

SP - 182

EP - 197

BT - PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2006

A2 - Benhamou, F

PB - Springer

CY - Berlin

T2 - 12th International Conference on Principles and Practice of Constraint Programming (CP 2006)

Y2 - 25 September 2006 through 29 September 2006

ER -

Watched literals for constraint propagation in MINION

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this