You are here

Domain Consistency with Forbidden Values

TitleDomain Consistency with Forbidden Values
Publication TypeConference Proceedings
Year of Conference2010
AuthorsDeville, Yves, and Van Hentenryck Pascal
Conference Name16th International Conference on Principles and Practice of Constraint Programming (CP 2010)
EditionLNCS, Springer

This paper presents a novel domain-consistency algorithm which does not maintain supports dynamically during propagation, but rather maintain forbidden values. It introduces the optimal NAC4 (negative AC4) algorithm based on this idea. It further shows that maintaining forbidden values dynamically allows the generic algorithm AC5 to achieve domain consistency in time O(ed) for classes of constraints in which the number of supports is O(d^2) but the number of forbidden values is O(d). The paper also shows how forbidden values and supports can be used jointly to achieve domain consistency on logical combinations of constraints and to compute validity as well as entailment of constraints. Experimental results show the benefits of the joint exploitation of supports and forbidden values.

Full text: