Bound Consistency for Binary Length-Lex Set Constraints

Pascal Van Hentenryck, Justin Yip, Carmen Gervet, Gregoire Dooms

The length-lex representation has been recently proposed for representing sets in Constraint Satisfaction Problems. The length-lex representation directly captures cardinality information, provides a total ordering for sets, and allows bound consistency on unary constraints to be enforced in time O(c log c), where c is the cardinality of the set. However, no algorithms were given to enforce bound consistency on binary constraints. This paper addresses this open issue. It presents algorithms to enforce bound consistency on disjointness and cardinality constraints in time O(c^3). Moreover, it presents a generic bound-consistency algorithm for any binary constraint S which requires O(c^2) calls to a feasibility subroutine for S.

Subjects: 15.2 Constraint Satisfaction; 15.7 Search

Submitted: Apr 14, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.