Loading...
Please wait, while we are loading the content...
Similar Documents
Length-Lex Open Constraints
| Content Provider | Semantic Scholar |
|---|---|
| Author | Dooms, Grégoire Mercier, Luc Hentenryck, Pascal Van Hoeve, Willem Jan Van Michel, Laurent |
| Copyright Year | 2007 |
| Abstract | 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.brown.edu/~gdooms/paper/openlenlex.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
