Several combinatorial problems, such as car sequencing and rostering, feature
sequence constraints, restricting the number of occurrences of certain values in
every subsequence of a given length.We present three new filtering algorithms for the
sequence constraint, including the first that establishes domain consistency in polynomial
time. The filtering algorithms have complementary strengths: One borrows
ideas from dynamic programming; another reformulates it as a regular constraint;
the last is customized. The last two algorithms establish domain consistency, and the
customized one does so in polynomial time. We provide experimental results that
demonstrate the practical usefulness of each. We also show that the customized algorithm
applies naturally to a generalized version of the sequence constraint that
allows subsequences of varied lengths. The significant computational advantage of
using a single generalized sequence constraint over a semantically equivalent collection
of among or sequence constraints is demonstrated empirically