The SeqBin constraint revisited
Résumé
We revisit the SEQBIN constraint [1]. This meta-constraint subsumes a number of important global constraints like CHANGE [2], SMOOTH [3] and INCREASINGNVALUE [4]. We show that the previously proposed filtering algorithm for SEQBIN has two drawbacks even under strong restrictions: it does not detect bounds disentailment and it is not idempotent. We identify the cause for these problems, and propose a new propagator that overcomes both issues. Our algorithm is based on a connection to the problem of finding a path of a given cost in a restricted n-partite graph. Our propagator enforces domain consistency in O(nd2) and, for special cases of SEQBIN that include CHANGE, SMOOTH and INCREASINGNVALUE in O(nd) time.
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...