10.1184/R1/6707045.v1 Willem-Jan Van Hoeve Willem-Jan Van Hoeve Gilles Pesant Gilles Pesant Louis-Martin Rousseau Louis-Martin Rousseau Ashish Sabharwal Ashish Sabharwal New Filtering Algorithms for Combinations of Among Constraints Carnegie Mellon University 1978 sequence constraint domain consistency polynomial time filtering car sequencing regular 1978-12-01 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/New_Filtering_Algorithms_for_Combinations_of_Among_Constraints/6707045 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