Length-lex bound consistency for knapsack constraints
Justin Yip, Pascal Van Hentenryck · 2009
This paper considers the length-lex domain for set-variables in constraint programming which includes not only membership but also cardinality and lexicographic information. The paper studies how to enforce bound consistency on a knapsack constraint over a set variable in this domain and proposes a bound-consistency algorithm which runs in O(c log n) time with a one-time preprocessing cost O(cn2) when the constraint is posted.