2012/07/07 by George Katsirelos, Katsirelos, George, Nina Narodytska +3
Computer Science · #Advanced Database Systems and Queries #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #cs.AI
paper · pdf · doi:10.48550/arxiv.1207.1811
Longer version of paper accepted at CP 2012
arxiv created 2012/07/07 · openalex publication_date 2012/07/07 · arxiv updated 2015/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the SeqBin constraint. This meta-constraint subsumes a number of important global constraints like Change, Smooth and IncreasingNValue. 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.