
## 3 The Sequence Constraint

The SEQUENCE constraint was introduced by Beldiceanu and Contejean [4]. It constrains the number of values taken from a given set in any sequence of k variables. It is useful in staff rostering to specify, for example, that every employee has at least 2 days off in any 7 day period. Another application is sequencing cars along a production line (prob001 in CSPLib). It can specify, for example, that at most 1 in 3 cars along the production line has a sun-roof. The SEQUENCE constraint can be defined in terms of a conjunction of AMONG constraints. AMONG(l, u, [X1, . . . , Xk], v) holds iff l ≤ |{i|Xi ∈ v**}| ≤** u. That is, between l and u of the k variables take values in v.

The AMONG constraint can be encoded by channelling into 0/1 variables using Yi ↔
(Xi ∈ v) and l ≤Pk i=1 Yi ≤ u. Since the constraint graph of this encoding is Bergeacyclic, this does not hinder propagation. Consequently, we will simplify notation and consider AMONG (and SEQUENCE) on 0/1 variables and v = {1}. If l = 0, AMONG
is an ATMOST constraint. ATMOST is *monotone* since, given a support, we also have support for any larger assignment [5]. The SEQUENCE constraint is a conjunction of overlapping AMONG constraints. More precisely, SEQUENCE(l, u, k, [X1, . . . , Xn], v) holds iff for 1 ≤ i ≤ n − k + 1, AMONG(l, u, [Xi, . . . , Xi+k−1], v) holds. A sequence like Xi**, . . . , X**i+k−1 is a *window*. It is easy to see that this decomposition hinders propagation. If l = 0, SEQUENCE is an ATMOSTSEQ constraint. Decomposition in this case does not hinder propagation. Enforcing DC on the decomposition of an ATMOSTSEQ constraint is equivalent to enforcing DC on the ATMOSTSEQ constraint [5].

Several filtering algorithms exist for SEQUENCE and related constraints. Regin and Puget proposed a filtering algorithm for the Global Sequencing constraint (GSC) that combines a SEQUENCE and a global cardinality constraint (GCC) [6]. Beldiceanu and Carlsson suggested a greedy filtering algorithm for the CARDPATH constraint that can be used to propagate the SEQUENCE constraint, but this may hinder propagation [7]. Regin decomposed GSC into a set of variable disjoint AMONG and GCC constraints [8].

Again, this hinders propagation. Bessiere *et al.* [5] encoded SEQUENCE using a SLIDE
constraint, and give a domain consistency propagator that runs in O(ndk−1) time. van Hoeve *et al.* [9] proposed two filtering algorithms that establish domain consistency.

The first is based on an encoding into a REGULAR constraint and runs in O(n2 k) time, whilst the second is based on cumulative sums and runs in O(n 3) time down a branch of the search tree. Finally, Brand *et al.* [10] studied a number of different encodings of the SEQUENCE constraint. Their asymptotically fastest encoding is based on separation theory and enforces domain consistency in O(n 2log n) time down the whole branch of a search tree. One of our contributions is to improve on this bound.

## 4 Flow-Based Propagator For The Sequence Constraint

We will convert the SEQUENCE constraint to a flow by means of a linear program
(LP). We shall use SEQUENCE(l, u, 3, [X1, . . . , X6], v) as a running example. We can 3