### 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(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.

Original language | English |
---|---|

Title of host publication | Principles and Practice of Constraint Programming - CP 2007 - 13th International Conference, CP 2007, Proceedings |

Pages | 210-224 |

Number of pages | 15 |

Publication status | Published - 1 Dec 2007 |

Externally published | Yes |

Event | International Conference on Principles and Practice of Constraint Programming 2007 - Providence, United States of America Duration: 23 Sep 2007 → 27 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

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4741 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | International Conference on Principles and Practice of Constraint Programming 2007 |
---|---|

Abbreviated title | CP 2007 |

Country | United States of America |

City | Providence |

Period | 23/09/07 → 27/09/07 |

Internet address |

## Cite this

*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).