Open Contractible Global Constraints

1 Introduction

The classic CSP model of constraint satisfaction [Dechter, 2003; Rossi et al., 2006] has a fixed static collection of variables over which a solution must be found. However, in many problems it is natural for the presence of some variables to be contingent on the value of other variables. This is true of configuration problems and scheduling problems that involve process-dependent activities [Bart´ak, 2003]. More generally, for difficult problems the intertwining of problem construction and problem solving provides a way to manage the complexity of a problem, and thus new variables and constraints may arise after solving has begun. Programming languages supporting constraint programming generally have the flexibility to add variables and constraints during the execution of a model.

However, global constraints do not have this flexibility: all variables must be available at the time the constraint is imposed, so variables cannot simply be added when they become available. The collection of variables they constrain is closed, rather than open. This can leave the filtering effect of the global constraint until too late in the execution, resulting in a large search space.

∗NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.

Recent work has focused on supporting open versions of global constraints. Bart´ak [Bart´ak, 2003] first formulated this issue and described a generic implementation technique to make open versions for the class of monotonic global constraints. But this technique is inefficient, and he also provided a specific implementation of the open ALLDIFFERENT constraint by modifying R´egin's algorithm [R´egin, 1994] for the closed ALLDIFFERENT.

A notion of Open CSP was investigated in [Faltings and Macho-Gonzalez, 2005]. In that work the set of variables is closed but the domains are open, that is, extra values can be added to variable domains.

Later work [van Hoeve and R´egin, 2006] addressed the problem when the variables that might be added to a constraint are specified in advance and a set variable describes the set of variables that will participate in the constraint. In this formulation, it becomes possible to filter the set variable in addition to the individual variables. [van Hoeve and R´egin, 2006] also gives an implementation the global cardinality constraint GCC and of multiple open GCC constraints over disjoint variables. Another work [Maher, 2009] allows only the number of variables to be constrained. However, in this paper we address Bart´ak's model of open constraints.

A major difficulty in implementing open constraints is that a propagator for a closed constraint may be unsound for the corresponding open constraint. That is, the propagator may make an inference that turns out to be unjustified once the sequence of variables is extended. In this paper we focus on the issue of identifying constraints for which a closed propagator is sound as an open propagator. It turns out that these constraints have a simple characterization, which we call contractibility, and which allows us to easily determine whether a constraint is contractible or not. This characterization is also convenient for finding the tightest contractible approximation of an uncontractible constraint. We illustrate our results with a wide variety of global constraints.

For contractible constraints we can, in theory, implement an open constraint by interleaving the propagator for the closed constraint and variable extension. But this does not ensure that propagators for closed contractible constraints can be cleanly and easily modified to implement open constraints.

We examine specific propagator algorithms for several closed constraints and demonstrate that they are easily adapted to implement the corresponding open constraint.

After some preliminaries in Section 2 we introduce contractibility in Section 3. We show that it characterizes those constraints for which closed propagators remain sound when the constraint is open, and develop an algebra for constructing contractible constraints. We characterize contractibility in language-theoretic terms in Section 4, and use that characterization to identify contractible constraints and tight approximations of uncontractible constraints. In Section 5 we describe modified algorithms for several open contractible constraints.

2 Background

The reader is assumed to have a basic knowledge of constraint programming, CSPs, global constraints, and filtering, as might be found in [Dechter, 2003; Rossi et al., 2006; Beldiceanu et al., 2005].

For the purposes of this paper, a global constraint is a relation over a sequence of variables. Other arguments of a constraint are considered parameters and are assumed to be fixed before execution. While some global constraints (such as ALLDIFFERENT and GCC) are more naturally represented as relations over an unordered collection of variables, we will find it convenient to ignore this abstraction: for some constraints (such as SEQUENCE) a sequence of variables is necessary, and uniformity over all constraints will simplify our treatment of the issues. A sequence of variables will be denoted by ⃗X or [X1, . . . ,Xn].

We make no a priori restriction on the variables that may participate in the sequence except that, in common with most work on global constraints, we assume that no variable appears more than once in a single constraint.

There are some specific global constraints that we define for completeness. These and other global constraints are discussed more completely in [Beldiceanu et al., 2005] and the references therein. The constraint ALLDIFFERENT([X1, . . . ,Xn]) [R´egin, 1994] states that the variables X1, . . . ,Xn take distinct values. The global cardinality constraint GCC(⃗v, ⃗l, ⃗u, [X1, . . . ,Xn]) [R´egin, 1996] states that, for every i, the value vi occurs between li and ui times in the list of variables. The constraint REGULAR(A, [X1, . . . ,Xn]) [Pesant, 2004] states that the value of the list of variables, when considered as a word, is accepted by the automaton A. Similarly, the constraint CFG(G, [X1, . . . ,Xn]) [Quimper and Walsh, 2006; Sellmann, 2006] states that the value of the list of variables, when considered as a word, is generated by the context-free grammar G.

The constraint SEQUENCE(l, u, k, [X1, . . . ,Xn], ⃗v) [Beldiceanu and Contejean, 1994] states that any consecutive sequence of k variables Xj, . . . ,Xj+k-1 contains between l and u occurrences of values from ⃗v. The constraint SLIDINGSUM(l, u, k, [X1, . . . ,Xn]) [Beldiceanu and Carlsson, 2001] states that the sum of any consecutive sequence of k variables lies between l and u. The constraint CONTIGUITY([X1, . . . ,Xn]) [Maher, 2002] states that the variables Xi take values from {0, 1} and the variables taking the value 1 are consecutive. The lexicographical ordering constraint [X1, . . . ,Xn] ≤lex [Z1, . . . ,Zn] [Frisch et al., 2002] states that the sequence of X variables is lexicographically less than or equal to the sequence of Z variables, where we assume some ordering on the underlying values. The precedence constraint s ≺⃗X t [Law and Lee, 2004] states that if t appears in the sequence ⃗X then s appears at a lower index.

Each variable X has a static type which defines a set of values T(X) which it may take. In addition, generally, each variable has an associated set S ⊆ T(X) of values, called its domain. We will view this simultaneously as: a function D : V ars → 2V alues where D(X) = S, a unary relation D(X) which is satisfied only when the value of X is some s ∈ S, and the pointwise extension of D to sequences of variables.

3 Contractible constraints

We want to extend a constraint C([X1, . . . ,Xn]) with an extra variable Y to C([X1, . . . ,Xn, Y ]). We would like to do filtering on the smaller constraint without knowing whether it will be extended to Y , or further. When we can do this, we have a kind of monotonicity property of C.

Definition 1 We say a constraint C([X1, . . . ,Xn]) is contractible if, there is a number m such that for all n ≥ m we have

The least such m is called the contractibility threshold 1 .

Thus C is contractible iff every solution of C([X1, . . . ,Xn, Y ]), when restricted to X1, . . . ,Xn where m ≤ n, is a solution of C([X1, . . . ,Xn]). The property is akin to the "optimal substructure" property that is a pre-requisite for the use of dynamic programming in optimization problems [Cormen et al., 2001] which requires that optimal solutions of a problem also solve subproblems optimally. Here it is only satisfiability, and not optimality, that is involved.

It follows that any sound form of filtering (such as arc consistency or bounds consistency) on a contractible constraint C([X1, . . . ,Xk]) is safe in the sense that any values deleted from domains in that process could also be deleted while filtering on C([X1, . . . , Xn]) for any n ≥ k.

Proposition 1 Let C be a contractible constraint. Suppose a sound filtering algorithm for C([X1, . . . ,Xn]) reduces the domain D for ⃗X to D′ . Then

Furthermore, if this property holds for all sound filterings then C must be contractible.

1 In most cases the contractibility threshold is 0, and we will not consider constraints with a higher threshold in this paper.

Consequently, for contractible constraints, filtering does not need to be undone if the list is lengthened. That is, algorithms for filtering a closed contractible constraint are valid also for the corresponding open constraint.

Conversely, any constraint that is not contractible might need to undo the effects of filtering if the list is lengthened. If σ is a solution of C([X1, . . . ,Xn, Y ]), but not of C([X1, . . . ,Xn]) then propagation on C([X1, . . . ,Xn]) might eliminate σ. For example, a constraint ∑i Xi = 5 would propagate X1 = 5 if the sequence ⃗X contains just one variable, thus eliminating solutions such as X1 = 2, X2 = 3. When the second variable is added, all propagation that is a consequence of the inference X1 = 5 must be undone.

The second part of this proposition shows that contractibility exactly characterizes the guarantee that closed filtering is safe for open constraints. That is, it is exactly the contractible constraints for which it is always sound to interleave closed filtering and addition of new variables.

The notion of contractibility is a variation of Bart´ak's monotonicity [Bart´ak, 2003] where we do not explicitly discuss variable domains. Before proceeding, we make this claim precise. We formulate Bart´ak's monotonicity as follows.

Definition 2 Let D be a domain. We say a constraint C is monotonic wrt D if, for any pair of disjoint sequences of variables ⃗X and ⃗Y

Contractibility differs frommonotonicity in that the definition is based entirely on the constraint, independent of the domains of variables. Hence it is not tied to domain-based reasoning; it is equally compatible with the more general framework of [Maher, 2003]. On the other hand, monotonicity is more flexible in reasoning about constraints that are only "partly contractible". The close relationship between monotonicity and contractibility is clear.

Proposition 2 If C is contractible then for any domain D, C is monotonic wrt D. Conversely, if C is monotonic wrt every domain D then C is contractible.

The SLIDEj meta-constraint [Bessi`ere et al., 2008] can be used to define several constraints on a sequence of variables. We use a variant of SLIDEj that starts applying the constraint at the pth position, rather than the first. SLIDEpj (C, ⃗X) holds iff C(Xij+p, . . . , Xij+p+k-1) holds for i = 0, 1, . . . , ⌊ n-p-k+1 j ⌋. SLIDEj is equal to SLIDE1j . SLIDE is equal to SLIDE1.

Constraints defined directly with SLIDEpj are contractible.

Proposition 3 Any constraint C defined by the SLIDEpj metaconstraint as C( ⃗X) ↔ SLIDEpj (C′ , ⃗X) is contractible.

Since the SEQUENCE and SLIDINGSUM constraints can each be defined as SLIDE(C′ , ⃗X), for appropriate constraint C ′ , it follows that they are both contractible.

For constraints where the order of variables is unimportant we can define a meta-constraint analogous to SLIDE, which we will call SPLASH. Like SLIDE, it takes a fixed arity constraint C′ and a sequence of variables ⃗X as arguments. Let C ′ have arity k, and ⃗X have length n, and let Sk( ⃗X) = {[Xi1 , . . . ,Xik ] | ij < ij+1 for j = 1, ..., k - 1}. Then we define SPLASH(C′ , ⃗X) ↔ ∧⃗ Y ∈Sk( ⃗X) C′ ( ⃗Y ). SPLASH(C′ , ⃗X) applies C′ to every subsequence of ⃗X of length k. For example, we can define ALLDIFFERENT( ⃗X) as SPLASH(̸=, ⃗X) and INTERDISTANCE( ⃗X) as SPLASH(C′ , ⃗X) where C′ (Z1, Z2) ↔ |Z1 - Z2| ≥ p. Thus, by the following proposition, ALLDIFFERENT and INTERDISTANCE are contractible.

Proposition 4 Any constraint C defined by the SPLASH meta-constraint as C( ⃗X) ↔ SPLASH(C′ , ⃗X) is contractible.

A constraint C of fixed arity k, when applied to a sequence of variables ⃗X, is assumed to be applied only to the initial segment X1, . . . ,Xk, or not at all if ⃗X is shorter than k. With this definition, C is contractible.

Once we have some contractible constraints, there are many ways to build other contractible constraints, as the following proposition demonstrates.

Proposition 5 Let C1( ⃗X) and C2( ⃗X) be contractible constraints on the same sequence of variables. Let C(X1, . . . ,Xk) be a constraint of fixed arity. Then

• C is contractible
• C1 ∧C2 is contractible
• C1 ∨C2 is contractible
• ∃Xi C1 is contractible
• ∀Xi C1 is contractible

In general, the negation or implication of contractible constraints is not contractible.

The previous results give us an algebra for constructing complex contractible constraints, and can be used to demonstrate that some existing constraints are contractible. For example, CONTIGUITY is implemented in [Maher, 2002] essentially as ∃⃗L, ⃗R SLIDE2 3 (C′ , [L1, X1, R1, L2, . . . , Xn, Rn]), where C′ has arity 7. Similarly, ( ⃗X ≤lex ⃗Y ) is encoded in [Bessi`ere et al., 2008] essentially as ∃ ⃗B SLIDE3(C′ , [B1,X1, Y1,B2, . . . ,Xn, Yn]) where C′ has arity 4. By the previous propositions, CONTIGUITY and ≤lex are contractible. Similarly, we can define a weak version of GCC where there are no lower bounds GCC(⃗v, ⃗0, ⃗u, [X1, . . . ,Xn]) as ∧vi∈⃗v SPLASH(C′ i , ⃗X), where C′ i has arity ui +1 and states that not all its arguments are equal to vi. By the previous propositions, this weak form of GCC is contractible.

However, it is notable that the REGULAR constraint is not contractible, despite the implementation in terms of SLIDE outlined in [Bessi`ere et al., 2008].

Example 1 Let A be an automaton that accepts the language a + b2 . Then REGULAR(A, [X1]) → X1 = a but REGULAR(A, [X1, Y ]) → X1 = b. Thus REGULAR is not contractible.

The discrepancy arises because REGULAR is not constructed from the operations in the above propositions. Essentially, the implementation defines

where the 3-ary constraint Transition expresses the state transitions of A, Start defines the start state(s) and Final defines the final state(s). It is the constraint on the final variable Qn that leads to uncontractibility; the remainder is expressible within the algebra.

4 Characterizing Contractibility

We can characterize when global constraints, such as REGULAR, are contractible by viewing the solutions of a global constraint as a formal language.

By insisting that variables in a constraint form a sequence we are able to view global constraints as defining a formal language. Each constraint C( ⃗X) defines the language LC = {σ(X1 . . .Xn) | σ is a solution of C([X1, . . . ,Xn])} which is the set of solutions of C, considered as words. Let P(L) = {w | ∃u wu ∈ L} denote the set of prefixes of a language L, called the prefix-closure of L. We say L is prefix-closed if P (L) = L.

We can now make a simple observation that provides a useful characterization of contractible constraints. If A defines a prefix-closed language then REGULAR(A, ⃗X) is contractible. This claim holds more generally.

Proposition 6 Let C( ⃗X) be a constraint over a sequence of variables. Then C is contractible iff LC is prefix-closed.

This result applies to constraints based on formal languages, such as REGULAR and CFG, but it also applies to constraints that are formulated differently. Thus, for example, the solutions of SEQUENCE and SLIDINGSUM are prefixclosed. Conversely, we see that constraining the final variable in a sequence, as in Final(Qn), is not contractible.

We can use this characterization both to determine whether a constraint is contractible or not, and as the basis for approximations of uncontractible constraints. We explore these possibilities in the following subsections.

4.1 Classifying Constraints

It is not within the scope of this paper to determine the contractibility of every global constraint. Nevertheless, we can outline and demonstrate some principles that make it easy, in most cases, to classify a global constraint as contractible or not.

In general, constraints based on counting with a lower bound (or equality) are not contractible. We can see this by noting that any non-trivial lower bound on the number of things in a sequence (or satisfied by a sequence) may be violated by a prefix of the sequence. This was already touched upon in [Bart´ak, 2003], where the SUM constraint ∑ni=1 Xi = N was shown to be non-monotonic, but the argument holds for a wide range of constraints.

For example, PEAK counts the number of peaks in a sequence, but a prefix of the sequence may have fewer peaks. Similarly, STRETCH places lower bounds on the span of stretches, so that 1122 might be a solution, while 112 is not. By a similar argument, constraints identifying properties of an extreme element in a sequence, such as HIGHESTPEAK, are not contractible. On the other hand NOPEAK is contractible since, to the extent that there is counting, there is no lower bound - only an upper bound of 0.

We can generalize and formalize these observations. A function f is a non-decreasing accumulation function if it maps sequences of values to values such that, for every sequence ⃗X and value Y , f([X1, . . . ,Xn, Y ]) ≥ f([X1, . . . ,Xn]). Among such functions are counting the number of elements in a sequence with a fixed property, identifying the highest peaks, and summing (some) non-negative elements of a sequence. Note that summing possibly negative elements of a sequence is not non-decreasing. The first part of the following proposition is an almost direct consequence of the definitions of contractible and non-decreasing accumulation function.

Proposition 7 Let C be a global constraint.

• Suppose C can be expressed as f( ⃗X) ≤ Z. Then C is contractible iff f is a non-decreasing accumulation function.
• Suppose C can be expressed as f( ⃗X) ≥ Z. Then C is contractible iff f is a non-increasing accumulation function.
• Suppose C can be expressed as f( ⃗X) = Z. Then C is contractible iff f is a constant function.

Thus the constraint ∑ni=1 Xi = N is not contractible, even when the Xi's are constrained to be non-negative. Similarly, ∑ni=1 Xi ≥ N is not contractible while, under the restriction on the Xi's ∑ni=1 Xi ≤ N is contractible. This result can be used to establish that PEAK, and HIGHESTPEAK are not contractible and that NOPEAK is contractible, but it also applies to many other counting and summing constraints in [Beldiceanu et al., 2005].

Notice that in constraints like SEQUENCE and SLIDINGSUM the use of a lower bound in the description of the constraint C′ to which SLIDE is applied does not prevent contractibility. Each lower bound applies only to a small part of the sequence. However, the RELAXEDSLIDINGSUM constraint, which weakens the SLIDINGSUM constraint by putting bounds on the number of times the C′ constraint is satisfied, is not contractible, because counting is an accumulation function that is not non-increasing and the lower bound applies to the entire sequence.

Some constraints can be recognised as contractible, based only on their informal semantics. For example, DIFFN and DISJUNCTIVE enforce that objects represented by the variables are non-overlapping. Clearly, if ⃗XY forms a nonoverlapping set, then so does ⃗X alone. Thus contractibility follows directly from Definition 1. Similarly, CUMULATIVE, BINPACKING and DISJOINT are contractible.

For other constraints, their informal semantics lead easily to counterexamples to contractibility. Constraints that involve computing the mean/average, median, mode, standard deviation, etc of the sequence are not contractible. This is easily recognised since these statistics are not, in general, preserved after eliminating part of the sample set, and hence are not prefix-closed. Alternatively, we could recognise that these functions are not non-increasing, nor non-decreasing and apply Proposition 7.

The idea of contractibility is not useful for all global constraints. For example, it appears irrelevant to cyclic constraints like the cyclic REGULAR, cyclic SEQUENCE and cyclic STRETCH constraints. In these constraints the sequence of variables is representing a cycle or circular list and there is no natural end at which to add variables. Thus it is not surprising that these constraints are not contractible.

There is sometimes a fine line between contractible and uncontractible constraints. For example, while ≤lex is contractible, <lex is not. To see the latter, observe that 111 <lex 112, but the corresponding prefixes are not strictly smaller - they are equal. If the precedence constraint s ≺⃗X t also required that t appear in ⃗X then the constraint is no longer contractible (because rst satisfies this constraint, but rs does not). Finally, notice that the SEQUENCE constraint is contractible, but it has the form SLIDE(C′ , ⃗X) where C′ is essentially a fixed-arity AMONG constraint; however, the (variablearity) AMONG constraint is not contractible.

4.2 Approximating Constraints

One approach to implementing uncontractible constraints is to employ a contractible approximation of the constraint as an open constraint, and then replace it with the original constraint once the sequence of variables is closed [Bart´ak, 2003]. The approximation must include all solutions of the original constraint, to ensure that no solutions of that constraint are lost during filtering of the approximation. Propositions 6 and 7 can be used to identify the tightest such approximation.

By Proposition 6, the tightest approximation of a constraint is its prefix-closure. This is a convenient characterization for language-based constraints. It is not difficult to show that the the prefix-closure of an automaton can be obtained by considering all states on a path between the start state and a final state in the automaton to be final states. Thus, for a REGULAR constraint, the tightest approximation is also a REGULAR constraint which can be obtained from the original simply by slightly modifying which states are final. Contextfree grammars also have a straightforward construction of the prefix-closure. For CFG constraints also, the tightest approximation is also a CFG constraint.

As discussed in [Bart´ak, 2003], a constraint ∑ni=1 Xi = N where the Xi's must be non-negative is not monotonic but is approximated by the constraint ∑ni=1 Xi ≤ N. Using Proposition 7 we can recognise this as the tightest contractible approximation. Similarly, for a counting constraint such as PEAK( ⃗X,N), which states that there are exactly N peaks in ⃗X, the tightest contractible approximation states that N is an upper bound on the number of peaks. The tightest approximation of the GCC is the weak form of GCC discussed in Section 3. In all these cases, since counting is a non-decreasing accumulation function, the tightest contractible approximation is to eliminate the lower bounds. In HIGHESTPEAK( ⃗X,Z), the height of the highest peak is a non-decreasing accumulation function and so the tightest approximation states that Z is an upper bound on the height of the highest peak.

On the other hand, for some constraints where the accumulation function is neither non-increasing nor non-decreasing there appear to be no non-trivial approximations. For example, consider a constraint AVERAGE( ⃗X,M) stating that M is the mean/average of the values of ⃗X. Given a fixed M, any sequence of values can be a prefix of a sequence with mean M. Hence the tightest contractible approximation of AVERAGE is the constraint that accepts any sequence, that is, the constraint true. For such a constraint there is no propagation until the constraint is closed.

In [Maher, 2009] these results are carried through to the design of propagators for open GCC, REGULAR and CFG.

5 Propagator Algorithms

It is perhaps unsurprising that implementations of closed contractible constraints often can easily be adapted to provide a direct implementation of the corresponding open constraint. As observed earlier, contractible constraints can use filtering algorithms designed for closed constraints also for the corresponding open constraint. Bart´ak's generic implementation technique [Bart´ak, 2003] exploits this fact for monotonic constraints by replacing the closed implementation of C([X1, . . . ,Xn]) with the closed implementation of C([X1, . . . ,Xn, Y ]) when the sequence is extended. However, it is preferable to preserve the existing state of C and extend it slightly to account for the presence of the new variable, if this is possible. Such an implementation, which provides a direct implementation of the open constraint, avoids duplication of work. In this case, the main issue in implementing an open version of a contractible constraint is handling the extension of the sequence of variables; more precisely, the important invariants of the implementation must be preserved or recovered after a variable is added. In this section we describe the changes needed to make open several contractible constraints.

Constraints defined using only SLIDE, SPLASH, conjunction and existential quantification, such as CONTIGUITY and ≤lex, can be implemented by the corresponding decomposition. In that case, the implementation can handle the sequence extension simply by asserting a copy or copies of the constraint C′ appropriate to the extension.

The lexicographical ordering constraint ⃗X ≤lex ⃗Y is implemented in [Frisch et al., 2002] by keeping track of (a) the lowest index i where Xi and Yi are not both ground and equal, and (b) the lowest index i where Xi >lex Yi. For each property, if there is no satisfying index an infinite value is used. The extension of the sequences with new variables will not affect the validity of these indices, since the new variable is either inserted after a finite index or before an infinite index. The implementation of the precedence constraint s ≺⃗X t [Law and Lee, 2004] uses a similar method, and is similarly easily adapted.

The flow-based implementation of the SEQUENCE constraint [Maher et al., 2008] keeps a feasible flow in a flow graph to represent the current state of the constraint. Suppose the width of a window is k. When a variable is added, the flow graph must be updated by adding two nodes (representing the new window) and 5 arcs (including one representing the new variable), redirecting k - 1 arcs (to arrive at the final node instead of the previously-final node; these arcs represent the existing variables that appear in the new window), and changing the capacity of one arc (the outflow from the previously-final node). The feasible flow of the original graph can be extended to these additions in constant time, using the fact that a solution σ to SEQUENCE([X1, . . . ,Xn]) can be extended to a solution of SEQUENCE([X1, . . . ,Xn, Y ]) by defining σ(Y ) = σ(Xn-k+1).

The shortest path implementation of SEQUENCE, denoted by CD in [Brand et al., 2007], uses a potential function (for an incremental shortest path algorithm [Cotton and Maler, 2006]) on a weighted graph to represent the current state of the constraint. When a variable is added, a node and four arcs are added to the graph and it is necessary to provide the potential of the new node. We can choose this potential to be π(Xn) + π(Xn-k+1) - π(Xn-k), using the fact above.

6 Conclusions

We have characterized the constraints for which the extension of the sequence of variables does not affect the soundness of propagation, both in logical and language-theoretic terms. We also identified an algebra for constructing contractible constraints. These results were used both to easily classify constraints as contractible or not, and to identify the tightest contractible approximation of constraints. We also showed how open versions of SEQUENCE, and lexicographic and precedence constraints can be implemented. It is noteworthy that these algorithms are the first described for open constraints over a sequence of variables, rather than a set of variables as in ALLDIFFERENT and GCC.