Encodings of the SEQUENCE constraint

Sebastian Brand, Nina Narodytska, Claude Guy Quimper, Peter Stuckey, Toby Walsh

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

31 Citations (Scopus)

Abstract

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(n2 log n) time. This improves upon the previous bound of O(n3) 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.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - CP 2007 - 13th International Conference, CP 2007, Proceedings
Pages210-224
Number of pages15
Publication statusPublished - 1 Dec 2007
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2007 - Providence, United States of America
Duration: 23 Sep 200727 Sep 2007
Conference number: 13th
http://archive.a4cp.org/cp2007/Welcome.html
https://link.springer.com/book/10.1007%2F978-3-540-74970-7 (Conference Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4741 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2007
Abbreviated titleCP 2007
CountryUnited States of America
CityProvidence
Period23/09/0727/09/07
Internet address

Cite this

Brand, S., Narodytska, N., Quimper, C. G., Stuckey, P., & Walsh, T. (2007). Encodings of the SEQUENCE constraint. In Principles and Practice of Constraint Programming - CP 2007 - 13th International Conference, CP 2007, Proceedings (pp. 210-224). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4741 LNCS).