The Range and Roots Constraints: Specifying Counting and Occurrence Problems

1 Introduction

Global constraints are central to the success of constraint programming. Global constraints allow users to specify patterns that occur in many problems, and to exploit efficient and effective propagation algorithms for pruning the search space. Two common types of global constraints are counting and occurrence constraints. Occurrence constraints place restrictions on the occurrences of particular values. For instance, we may wish to ensure that no value used by one set of variables occurs in a second set. Counting constraints, on the other hand, restrict the number of values or variables meeting some condition. For example, we may want to limit the number of distinct values assigned to a set of variables. Many different counting and occurrences constraints have been proposed to help model a wide range of problems, especially those involving resources (see, for example, [R´egin, 1994; Beldiceanu and Contejean, 1994; R´egin, 1996; Beldiceanu, 2001; Beldiceanu et al., 2004b]).

We will show that many such constraints can be specified using a simple declarative language. This specification language is executable. It decomposes these constraints into some simple primitives for which there are polynomial propagation algorithms. In some cases, we show that this decomposition does not hinder propagation. In other cases, achieving generalized arc-consistency is NP-hard and decomposition is one method to obtain a polynomial propagation algorithm. In the remaining cases, we show that the decomposition hinders propagation, and there exists some specialized and polynomial propagation algorithm. As not all global constraints are implemented and integrated into every solver, our language may still be attractive in this case. We provide a generic means for propagating counting and occurrence constraints in the absence of a specialized algorithm. Our experiments demonstrate that this is an efficient and effective way to reason about counting and occurrence constraints in practice.

∗Brahim Hnich is currently supported by Science Foundation Ireland under Grant No. 00/PI.1/C075.

2 Formal Background

A constraint satisfaction problem consists of a set of variables, each with a finite domain of values, and a set of constraints specifying allowed combinations of values for subsets of variables. We use capital letters for variables (e.g. X, Y and S), and lower case for values (e.g. d and di). We write D(X) for the domain of a variable X. A solution is an assignment of values to the variables satisfying the constraints. A variable is ground when it is assigned a value. We consider both integer and set variables. A constraint can be defined on only integer, or only set variables, or on both. A set variable S can be represented by its lower bound lb(S) which contains the definite elements and an upper bound ub(S) which contains the definite and potential elements. Each set variable is equivalent to a sequence of 0/1 variables representing the characteristic function. A variable in such a sequence is 1 iff the corresponding element is in the set.

Given a constraint C, a bound support on C is a tuple that assigns to each integer variable a value between its minimum and maximum, and to each set variable a set between its lower and upper bounds which satisfies C. An hybrid support on C is a tuple that assigns to each integer variable a value in its domain, and to each set variable a set between its lower and upper bounds which satisfies C. If C involves only integer variables, a hybrid support is a support. A constraint C is bound consistent (BC) iff for each integer variable Xi, its minimum and maximum values belong to a bound support, and for each set variable Sj, the values in ub(Sj) belong to Sj in at least one bound support and the values in lb(Sj) belong to Sj in all bound supports. A constraint C is hybrid consistent (HC) iff for each integer variable Xi, every value in D(Xi) belongs to an hybrid support, and for each set variable Sj, the values in ub(Sj) belong to Sj in at least one hybrid support, and the values in lb(Sj) belong to Sj in all hybrid supports. A constraint C involving only integer variables is generalized arc consistent (GAC) iff for each variable Xi, every value in D(Xi) belongs to a support.

Enforcing hybrid consistency on a constraint C is equivalent to enforcing GAC if the set variables are represented by their characteristic function. If all variables in C are integer variables, hybrid consistency reduces to generalized arcconsistency, and if all variables in C are set variables, hybrid consistency reduces to bound consistency.

We will compare local consistency properties applied to (sets of) logically equivalent constraints, c1 and c2. As in [Debruyne and Bessi`ere, 1997], a local consistency property Φ on c1 is as strong as Ψ on c2 iff, given any domains, if Φ holds on c1 then Ψ holds on c2; Φ on c1 is stronger than Ψ on c2 iff Φ on c1 is as strong as Ψ on c2 but not vice versa; Φ on c1 is equivalent to Ψ on c2 iff Φ on c1 is as strong as Ψ on c2 and vice versa; Φ on c1 is incomparable to Ψ on c2 iff Φ on c1 is not as strong as Ψ on c2 and vice versa.

A total function F from a set S into a set T is denoted by F : S -→ T where S is the domain of F and T is the range of F. The set of all elements in the domain of F that have the same image j ∈ T is F -1 (j) = {i : F(i) = j}. The image of a set S ⊆ S under F is F(S) = ⋃i∈S F(i), whilst the domain of a set T ⊆ T under F is F -1 (T ) = ⋃j∈T F -1 (j). Throughout, we will view a set of variables, X1 to Xn as a function X : {1, .., n} -→ ⋃i=n i=1 D(Xi). That is, X(i) is the value of Xi.

3 Specification Language

We propose a simple declarative language in which we can specify many different counting and occurrence constraints. This specification language is executable. It permits us to decompose each global constraint into more primitive constraints, each of which has an associated polynomial propagation algorithm. In some cases, this decomposition does not hinder propagation. In other cases, enforcing local consistency on the global constraint is intractable, and decomposition is one method to obtain a polynomial propagation algorithm. The specification language consists of simple nonglobal constraints over integer variables (like X ≤ m), simple non-global constraints over set variables (like S1 ⊆ S2 or |S| = k) and two special global constraints acting on sequences of variables: ROOTS and RANGE.

Given a function X representing a set of variables, X1 to Xn, the RANGE constraint holds iff a set variable, T is the range of this function restricted to the indices belonging to a second set variable, S.

The ROOTS constraint holds iff S is the set of indices which map to an element in T .

ROOTS and RANGE are not exact inverses. A RANGE constraint can hold, but the corresponding ROOTS constraint may not, and vice versa. For instance, RANGE([1, 1], {1}, {1})

holds but not ROOTS([1, 1], {1}, {1}) since X -1 (1) = {1, 2}, and ROOTS([1, 1, 1], {1, 2, 3}, {1, 2}) holds but not RANGE([1, 1, 1], {1, 2, 3}, {1, 2}) as no Xi is assigned to 2.

In an associated report, we discuss how to propagate these two global constraints. Enforcing HC on the RANGE constraint is polynomial and give an O(nd + n · |lb(T)|3/2) algorithm where d is the maximum domain size of the Xi. Enforcing BC on the ROOTS constraint is O(nd). Unfortunately, enforcing HC on the ROOTS constraint is NP-hard. Nevertheless, all the cases needed here are polynomial. For example, if all Xi are ground, or T is ground then enforcing HC on ROOTS([X1, .., Xn], S, T ) is O(nd).

4 Range Constraints

In an associated report, we present a catalog containing over 70 global constraints from [Beldiceanu, 2000] specified with this simple language. We have room here to present just a few of the more important constraints. In this and the subsequent three sections, we list some global constraints which can be specified using RANGE constraints, using ROOTS constraints, and using both RANGE and ROOTS constraints.

4.1 All Different

The ALLDIFFERENT constraint forces a sequence of variables to take different values from each other. Such a constraint is useful in a wide range of problems (e.g. allocation of activities to different slots in a timetabling problem). It can be propagated efficiently [R´egin, 1994]. It can also be decomposed with a single RANGE constraint:

A special but nevertheless important case of this constraint is the PERMUTATION constraint. This is an ALLDIFFERENT constraint where we additionally knowR, the set of values to be taken. That is, the sequence of variables is a permutation of the values in R where |R| = n. This also can be decomposed using a single RANGE constraint:

Such a decomposition of the PERMUTATION constraint obviously does not hinder propagation. However, decomposition of ALLDIFFERENT into a RANGE constraint does. In addition, HC on the RANGE decomposition is incomparable to AC on the decomposition of ALLDIFFERENT which uses a clique of binary inequality constraints. Thus, we may be able to obtain more pruning by using both decompositions.

Theorem 1 GAC on PERMUTATION is equivalent to HC on the decomposition with RANGE. GAC on ALLDIFFERENT is stronger than HC on the decomposition with RANGE. AC on the decomposition of ALLDIFFERENT into binary inequalities is incomparable to HC on the decomposition with RANGE.

RANGE([X1,X2,X3], {1, 2, 3}, T) and |T| = 3 are both HC, but ALLDIFFERENT([X1,X2,X3]) is not GAC. Consider X1, X2 ∈ {1, 2}, X3 ∈ {1, 2, 3}, and T = {1, 2, 3}. Then X1 ̸= X2, X1 ̸= X3 and X2 ̸= X3 are AC but RANGE([X1, X2, X3], {1, 2, 3}, T ) is not HC. Consider X1, X2 ∈ {1, 2, 3, 4}, X3 ∈ {2}, and {2} ⊆ T ⊆ {1, 2, 3, 4}. Then RANGE([X1,X2,X3], {1, 2, 3}, T) and |T| = 3 are HC. But X1 ̸= X3 and X2 ̸= X3 are not AC. The other result holds immediately. ✷

4.2 Number of Values

The NVALUE constraint is useful in a wide range of problems involving resources since it counts the number of distinct values used by a sequence of variables [Pachet and Roy, 1999]. NVALUE([X1, ..,Xn],N) holds iff N = |{Xi | 1 ≤ i ≤ n}|. The ALLDIFFERENT constraint is a special case of the NVALUE constraint in which N = n. Unfortunately, it is NP-hard in general to enforce GAC on a NVALUE constraint [Bessiere et al., 2004]. However, there is an O(n log(n)) algorithm to enforce a level of consistency similar to BC [Beldiceanu, 2001]. An alternative and even simpler way to implement this constraint is with a RANGE constraint:

HC on this decomposition is incomparable to BC on the NVALUE constraint.

Theorem 2 BC on NVALUE is incomparable to HC on the decomposition.

Proof: Consider X1,X2 ∈ {1, 2}, X3 ∈ {1, 2, 3, 4}, N ∈ {3} and {} ⊆ T ⊆ {1, 2, 3, 4}. Then RANGE([X1,X2,X3], {1, 2, 3}, T) and |T| = N are both HC. However, enforcing BC on NVALUE([X1,X2,X3],N) prunes 1 and 2 from X3.

Consider X1,X2,X3 ∈ {1, 3} and N ∈ {3}. Then NVALUE([X1,X2,X3],N) is BC. However, enforcing HC on RANGE([X1,X2,X3], {1, 2, 3}, T) makes {} ⊆ T ⊆ {1, 3} which will cause |T | = 3 to fail. ✷

4.3 Uses

In [Beldiceanu et al., 2004b], propagation algorithms achieving GAC and BC are proposed for the USEDBY constraint. USEDBY([X1, ..,Xn], [Y1, .., Ym]) holds iff the multiset of values assigned to Y1, .., Ym is a subset of the multiset of values assigned to X1, ..,Xn. We now introduce a variant of the USEDBY constraint called the USES constraint. USES([X1, ..,Xn], [Y1, .., Ym]) holds iff the set of values assigned to Y1, .., Ym is a subset of the set of values assigned to X1, ..,Xn. That is, USEDBY takes into account the number of times a value is used while USES does not. Unlike the USEDBY constraint, enforcing GAC on USES is NP-hard.

Theorem 3 Enforcing GAC on USES is NP-hard.

Proof: We reduce 3-SAT to the problem of deciding if a USES constraint has a solution. Finding support is therefore NP-hard. Consider a formula ϕ with n Boolean variables and m clauses. For each Boolean variable i, we introduce a variable Xi ∈ {i,-i}. For each clause cj = x ∨ ¬y ∨ z, we introduce Yj ∈ {x, -y, z}. Then ϕ has a model iff the USES constraint has a satisfying assignment, and i is true iff Xi = i.

✷

One way to propagate a USES constraint is to decompose it using RANGE constraints:

Enforcing HC on this decomposition is polynomial. Not surprisingly, this hinders propagation (otherwise we would have a polynomial algorithm for a NP-hard problem).

Theorem 4 GAC on USES is stronger than HC on the decomposition.

Proof: Consider X1 ∈ {1, 2, 3, 4}, X2 ∈ {1, 2, 3, 5}, X3,X4 ∈ {4, 5, 6}, Y1 ∈ {1, 2}, Y2 ∈ {1, 3}, and Y3 ∈ {2, 3}. The decomposition is HC while GAC on USES prunes 4 from the domain of X1 and 5 from the domain of X2. ✷

Thus, decomposition is a simple method to obtain a polynomial propagation algorithm.

5 Roots Constraints

RANGE constraints are often useful to specify constraints on the values used by a sequence of variables. ROOTS constraint, on the other hand, are useful to specify constraints on the variables taking particular values.

5.1 Global Cardinality

The global cardinality constraint introduced in [R´egin, 1996] constrains the number of times values are used. We consider a generalization in which the number of occurrences of a value may itself be an integer variable. That is, GCC([X1, ..,Xn], [d1, .., dm], [O1, ..,Om]) holds iff |{i | Xi = dj}| = Oj for all j. Such a GCC constraint can be decomposed into a set of ROOTS constraints:

Enforcing HC on these ROOTS constraints is polynomial since the sets {di} are ground. Enforcing GAC on a generalized GCC constraint is NP-hard, but we can enforce GAC on the Xi and BC on the Oj in polynomial time using a specialized algorithm [Quimper et al., 2004]. This is more than is achieved by the decomposition.

Theorem 5 GAC on the Xi and BC on the Oj of a GCC constraint is stronger than HC on the decomposition using ROOTS constraints.

Proof: Sets being represented by their bounds, HC on the decomposition cannot prune more on the Oj than BC does on the GCC. To show strictness, consider X1,X2 ∈ {1, 2}, X3 ∈ {1, 2, 3}, di = i and O1,O2,O3 ∈ {0, 1}. The decomposition is HC (with {} ⊆ S1, S2 ⊆ {1, 2, 3} and {} ⊆ S3 ⊆ {3}). However, enforcing GAC on the Xi and BC on the Oj of the GCC constraint will prune 1 and 2 from X3 and 0 fromO1, O2 and O3. ✷

This example illustrates that, whilst many global constraints can be expressed in terms of ROOTS and RANGE, there are some global constraints like GCC for which it is worth developing specialized propagation algorithms. Nevertheless, ROOTS and RANGE provide a means of propagation for such constraints in the absence of specialised algorithms.

5.2 Among

The AMONG constraint was introduced in CHIP to help model resource allocation problems like car sequencing [Beldiceanu and Contejean, 1994]. It counts the number of variables using values from a given set. AMONG([X1, .., Xn], [d1, .., dm], N) holds iff N = |{i | Xi ∈ {d1, .., dm}}|.

One decomposition using the global cardinality constraint GCC introduced in [R´egin, 1996] is as follows:

Unfortunately, this decomposition hinders propagation.

Theorem 6 GAC on AMONG is stronger than GAC on the decomposition using GCC.

Proof: Consider X1,X2 ∈ {1, 2}, X3 ∈ {1, 2, 3}, d1 = 1, d2 = 2, and N ∈ {1, 2}. The decomposition is GAC, but enforcing GAC on AMONG([X1, X2, X3], [d1, d2], N) prunes 1 and 2 fromX3 as well as 1 fromN. ✷

An alternative way to propagate the AMONG constraint is to decompose it using a ROOTS constraint:

It is polynomial to enforce HC on this case of the ROOTS constraint since the target set is ground. This decomposition also does not hinder propagation. It is therefore a potentially attractive method to implement the AMONG constraint.

Theorem 7 GAC on AMONG is equivalent to HC on the decomposition using ROOTS.

Proof: (Sketch) Suppose the decomposition into ROOTS([X1, ..,Xn], S, {d1, .., dm}) and |S| = N is HC. The variables Xi divide into three categories: those whose domain only contains elements from {d1, .., dm} (at most min(N) such vars); those whose domain do not contain any such elements (at most n - max(N) such vars); those whose domain contains both elements from this set and from outside. Consider any value for a variable Xi in the first such category. To construct support for this value, we assign the remaining variables in the first category with values from {d1, .., dm}. If the total number of assigned values is less than min(N), we assign a sufficient number of variables from the second category with values from {d1, .., dm} to bring up the count to min(N). We then assign all the remaining unassigned Xj with values outside {d1, .., dm}. Finally, we assign min(N) to N. Support can be constructed for variables in the other two categories in a similar way, as well as for any value of N between min(N) and max(N). ✷

The ATMOST and ATLEAST constraints are closely related. The ATMOST constraint puts an upper bound on the number of variables using a particular value, whilst the ATLEAST puts a lower bound. Both can be decomposed using a ROOTS constraint without hindering propagation.

6 Range and Roots Constraints

Some global constraints need both ROOTS and RANGE constraints in their specifications.

6.1 Assign and NValues

In bin packing and knapsack problems, we may wish to assign both a value and a bin to each item, and place constraints on the values appearing in each bin. For instance, in the steel mill slab design problem (prob038 in CSPLib), we assign colors and slabs to orders so that there are a limited number of colors on each slab. ASSIGN&NVALUES([X1, ..,Xn], [Y1, .., Yn],N) holds iff |{Yi | Xi = j}| ≤ N for each j [Beldiceanu, 2000]. It can be decomposed into a set of ROOTS and RANGE constraints:

Decomposition hinders propagation as it considers the values separately. However, since this constraint generalizes NVALUE, enforcing GAC is NP-hard. Decomposition is thus one method to obtain a polynomial propagation algorithm.

6.2 Common

A generalization of the AMONG and ALLDIFFERENT constraints introduced in [Beldiceanu, 2000] is the COMMON constraint. COMMON(N,M, [X1, ..,Xn], [Y1, .., Ym]) ensures N = |{i | ∃j,Xi = Yj}| andM = |{j | ∃i,Xi = Yj}|. That is, N variables in Xi take values in common with Yj and M variables in Yj takes values in common with Xi. We prove that we cannot expect to enforce GAC on such a constraint as it is NP-hard to do so in general.

Theorem 8 Enforcing GAC on COMMON is NP-hard.

Proof: We again use a transformation from 3-SAT. Consider a formula ϕ with n Boolean variables and m clauses. For each Boolean variable i, we introduce a variable Xi ∈ {i,-i}. For each clause cj = x ∨ ¬y ∨ z, we introduce Yj ∈ {x, -y, z}. We let N ∈ {0, .., n} and M = m. ϕ has a model iff the COMMON constraint has a solution in which the Xi take the literals true in this model. ✷

One way to propagate a COMMON constraint is to decompose it into RANGE and ROOTS constraints:

Enforcing HC on this decomposition is polynomial. Decomposition thus offers a simple and promising method to propagate a COMMON constraint. Not surprisingly, the decomposition hinders propagation.

Theorem 9 GAC on COMMON is stronger than HC on the decomposition.

Proof: Consider N = M = 0, X1, Y1 ∈ {1, 2}, X2, Y2 ∈ {1, 3}, Y3 ∈ {2, 3}. Hybrid consistency on the decomposition enforces {} ⊆ T, V ⊆ {1, 2, 3}, and S = U = {} but no pruning on the Xi and Yj . However, enforcing GAC on COMMON(N,M, [X1,X2], [Y1, Y2, Y3]) prunes 2 from X1, 3 from X2 and 1 from both Y1 and Y2. ✷

6.3 Symmetric All Different

In certain domains, we may need to find symmetric solutions. For example, in sports scheduling problems, if one team is assigned to play another then the second team should also be assigned to play the first. SYMALLDIFF([X1, ..,Xn]) ensures Xi = j iff Xj = i [R´egin, 1999]. It can be decomposed into a set of ROOTS and RANGE constraints:

It is polynomial to enforce HC on these cases of the ROOTS constraint. However, as with the ALLDIFFERENT constraint, it is more effective to use a specialized propagation algorithm like that in [R´egin, 1999].

Theorem 10 GAC on SYMALLDIFF is stronger than HC on the decomposition.

Proof: Consider X1 ∈ {2, 3}, X2 ∈ {1, 3}, X3 ∈ {1, 2}, {} ⊆ S1 ⊆ {2, 3}, {} ⊆ S2 ⊆ {1, 3}, and {} ⊆ S3 ⊆ {1, 2}. Then the decomposition is HC. However, enforcing GAC on SYMALLDIFF([X1,X2,X3]) will detect unsatisfiability. ✷

To our knowledge, this constraint has not been integrated into any constraint solver. Thus, this decomposition provides a means of propagation for the SYMALLDIFF constraint.

7 Beyond Counting and Occurrence

The RANGE and ROOTS constraints are useful for specifying a wide range of counting and occurence constraints. Nevertheless, their expressive power permits their use to specify many other constraints.

The ELEMENT constraint introduced in [Van Hentenryck and Carillon, 1988] indexes into an array with a variable. More precisely, ELEMENT(I, [X1, ..,Xn], J) holds iff XI = J. We can use such a constraint to look up the price of a component included in a configuration problem. The ELEMENT constraint can be decomposed into a RANGE constraint without hindering propagation:

We may wish to channel between a variable and the sequence of 0/1 variables representing the possible values taken by the variable. The DOMAIN(X, [X1, .., Xm]) constraint introduced in [Refalo, 2000] ensures X = i iff Xi = 1. This can be decomposed into a ROOTS constraint:

Enforcing HC on this decomposition is polynomial ({1} is ground) and it is equivalent to enforcing GAC on the DOMAIN constraint.

The CONTIGUITY constraint ensures that, in a sequence of 0/1 variables, those taking the value 1 appear contiguously. This is a discrete form of convexity. The constraint was introduced in [Maher, 2002] to model a hardware configuration problem. It can be decomposed into a ROOTS constraint:

Again it is polynomial to enforce HC on this case of the ROOTS constraint. Unfortunately, decomposition hinders propagation. Consider X1,X3 ∈ {0, 1}, X2,X4 ∈ {1}. HC on the decomposition will enforce {2, 4} ⊆ S ⊆ {1, 2, 3, 4}, X ∈ {4}, Y ∈ {1, 2} and |S| to be in {3, 4} but no pruning will happen on the Xi. However, enforcing GAC on CONTIGUITY([X1, ..,Xn]) will prune 0 fromX3.

Whilst ROOTS and RANGE can specify concepts quite distant from counting and occurrences like convexity and discrete derivatives, it seems that we may need other algorithmic ideas to propagate them effectively.

8 Experiments

The last three sections demonstrate that many global constraints can be specified in terms of ROOTS and RANGE constraints. We also argued that these specifications are executable and in certain cases provide efficient and effective propagation algorithms. In this section, we support this argument by means of some experiments.

Table 1: Mystery Shopper. Instance are run with a 5 minutes time limit. #fails (f) and cpu time (t) are averaged on the #instances solved (#s) by each method.

We used a model for the Mystery Shopper problem [Cheng et al., 1998] due to Helmut Simonis that appears in CSPLib. This model contains a GCC constraint and a number of AMONG constraints. ILOG's Solver contains the GCC but not the AMONG constraint. We implement AMONG either with a GCC and a SUM constraint or directly with ROOTS. This gives us two models (2GCC+SUM and GCC+ROOTS, resp.). We also consider the model (ROOTS) which is a variation of GCC+ROOTS where we decompose the GCC constraint using ROOTS. In order to generate a range of instances, we used the following protocol. The duration in weeks as well as the number of varieties of shoppers, visits per salelady and number of areas are all set to 4 (as in the original problem). The number of saleladies takes its value in {10, 15, 20, 25, 30, 35}, and the number of shoppers is the next multiple of 4 that is not consecutive. All the possible ways of partitioning the saleladies into 4 areas (that do not trivially violate the constraints) are solved. As expected, the decomposition of the AMONG constraint using ROOTS is more efficient than the decomposition with a GCC and a SUM constraint (see Table 1). Surprisingly, however, the ROOTS model is the most efficient strategy (see the '#s' column). This is because we were able to branch on the 'extra' set variables, which proved to be the most effective method. Finally, the inference using GCC (2GCC+SUM) is faster (better ratio t/f) than using its decomposition (ROOTS). This suggests that it will be worth investing time and effort into optimizing this new ROOTS constraint.

9 RelatedWork

Beldiceanu has specified a wide range of global constraints using simple properties of suitably constructed graphs [Beldiceanu, 2000]. There are several important differences between this approach and the framework presented here. For instance, our specification language is executable. Given a specification, we immediately have a polynomial propagation algorithm. This is not the case with Beldiceanu's framework. On the other hand, Beldiceanu's framework is more general since the ROOTS and RANGE constraints can easily be specified in terms of some simple graph properties.

A number of researchers have specified global constraints over sequences of variables using automaton. Beldiceanu et al. use an extended polynomial sized automaton, and show how to extract automatically a GAC propagation algorithm [Beldiceanu et al., 2004a]. Pesant uses a deterministic finite automaton, and develops a GAC propagation algorithm for membership of the corresponding regular language [Pesant, 2004]. These approaches are complementary to the framework presented here. For example, automaton can easily specify constraints like the CONTIGUITY constraint and thus provide us with a GAC propagation algorithm. This does not seem possible with just ROOTS and RANGE constraints. On the other hand, deterministic or extended automaton cannot specify a simple PERMUTATION constraint.

10 Conclusions

We have proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the RANGE constraint which computes the range of values used by a set of variables, and the ROOTS constraint which computes the variables in a set mapping onto particular values. This specification language is executable. It immediately provides a polynomial propagation algorithm for any constraint that can be specified. In some cases, this propagation algorithm achieves GAC (e.g. the PERMUTATION and AMONG constraints). In other cases, this propagation algorithm may not make the constraint GAC, but achieving GAC is NP-hard (e.g. the NVALUE and COMMON constraints). Decomposition is then one method to obtain a polynomial algorithm. In the remaining cases, the propagation algorithm may not make the constraint GAC, and specialized propagation algorithms can do so in polynomial time (e.g. the SYMALLDIFF constraint).

Our method can still be attractive in this last case as it provides a generic means of propagation for counting and occurrence constraints in the absence of a specialized algorithm. Experiments demonstrate that such propagation algorithms can be both efficient and effective in practice.