×

zbMATH — the first resource for mathematics

Encodings of the Sequence constraint. (English) Zbl 1145.68507
Bessi√®re, Christian (ed.), Principles and practice of constraint programming – CP 2007. 13th international conference, CP 2007, Providence, RI, USA, September 23–27, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74969-1/pbk). Lecture Notes in Computer Science 4741, 210-224 (2007).
Summary: The Sequence constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the Sequence constraint, some of which do not hinder propagation. We prove that, down a branch of a search tree, domain consistency can be enforced on the Sequence constraint in just \(O(n ^{2} \log n)\) time. This improves upon the previous bound of \(O(n ^{3})\) for each call down the tree. We also consider a generalization of the Sequence constraint – the Multiple Sequence constraint. Our experiments suggest that, on very large and tight problems, domain consistency algorithms are best. However, on smaller or looser problems, much simpler encodings are better, even though these encodings hinder propagation. When there are multiple Sequence constraints, a more expensive propagator shows promise.
For the entire collection see [Zbl 1142.68007].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI