Length-Lex Open Constraints

Open constraints were introduced to model the many industrial applications 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. Regin 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 information, while enforcing bound-consistency for a variety of important constraints. The paper makes two orthogonal contributions. First, it shows how to derive a filtering 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 shows how to derive a filtering algorithm for a length-lex open constraint from the filtering algorithm of the subset-bound open constraint. This technique is entirely generic and adds a factor n in complexity to the subset-bound open constraints. The key underlying insight is to recognize that a length-lex interval can be represented as the union of O(n) subset-bound intervals and their cardinalities. This result also allows to systematically lift filtering algorithms from subset-bound intervals to length-lex intervals.