Length-Lex Open Constraints

Abstract. Open constraints were introduced to model the many industrial appli-cations in which a task can be handled by several resources. Open constraints are unique because the set of variables over which the the constraint is defined is a set-variable. Régin and van Hoeve recently showed how to filter an open GCC constraint when the set variable use a subset-bound domain. This paper considers open constraints in which the set-variables use the richer length-lex domain of Gervet and Van Hentenryck which includes cardinality and lexicographic infor-mation, while enforcing bound-consistency for a variety of important constraints. The paper makes two orthogonal contributions. First, it shows how to derive a fil-tering algorithm for the length-lex open constraint from the cost-based version of the closed version. The key insight is that well chosen weights allow to map the total order of length-lex sets with the total order of set weights. Second, it show