Length-Lex Open Constraints.pdf.pdf' (199.01 kB)

Download file# Length-Lex Open Constraints

journal contribution

posted on 01.10.2008, 00:00 by Gregoire Dooms, Luc Mercier, Pascal van Hentenryck, Willem-Jan Van HoeveWillem-Jan Van Hoeve, Laurent MichelOpen 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.