MDD Propagation for Sequence Constraints

.We study propagation for the sequence constraint in the context of constraint programming based on limited-width MDDs. Our first main contribution is proving that establishing MDD-consistency for sequence is NP-hard. Second, we propose a partial filtering algorithm that relies on a specific decomposition of the constraint and a novel extension of MDD filtering to node domains. Finally, we experimentally evaluate the performance of our proposed filtering algorithm. We show that large savings can be obtained in terms of search tree size and computation time with respect to the current best MDD approach that applies the decomposition of sequence into among constraints. In addition, we show the potential of our MDD propagator with respect to a state-of-the-art domain propagator for sequence, both in terms of search tree size and computation time