Decompositions of All Different, Global Cardinality and Related Constraints

1 Introduction

Global constraints allow users to specify patterns that commonly occur in problems. One of the oldest and most useful is the ALL-DIFFERENT constraint [Lauriere, 1978; R´egin, 1994]. This ensures that a set of variables are pairwise different. Global constraints can often be decomposed into more primitive constraints. For example, the ALL-DIFFERENT constraint can be decomposed into a clique of binary inequalities. However, such decompositions usually do not provide a global view and are thus not able to achieve levels of local consistency, such as bound and domain consistency. Considerable effort has therefore been invested in developing efficient propagation algorithms to reason globally about such constraints. For instance, several different propagation algorithms have been developed for the ALL-DIFFERENT constraint [R´egin, 1994; Leconte, 1996; Puget, 1998; Mehlhorn and Thiel, 2000; Lopez-Ortiz et al., 2003]. In this paper, we show that several important global constraints including ALL-DIFFERENT can be decomposed into simple arithmetic constraints whilst still providing a global view since bound consistency can be achieved.

There are many reasons why such decompositions are interesting. First, it is very surprising that complex propagation algorithms can be simulated by simple decompositions. In many cases, we show that reasoning with the decompositions is of similar complexity to existing monolithic propagation algorithms. Second, these decompositions can be easily added to a new solver. For example, we report experiments here using these decompositions in a state of the art pseudo-Boolean solver. We could just as easily use them in an ILP solver. Third, introduced variables in these decompositions give access to the state of the propagator. Sharing of such variables between decompositions can increase propagation. Fourth, these decomposition provide a fresh perspective to propagating global constraints that may be useful. For instance, our decompositions of the ALL-DIFFERENT constraint suggest learning nogoods based on small Hall intervals.

∗Supported by the project ANR-06-BLAN-0383-02.

†NICTA is funded by the Australian Government through the Department of Broadband, Communications and the Digital Economy and the Australian Research Council.

2 Formal Background

A constraint satisfaction problem (CSP) consists of a set of variables, each with a finite domain of values, and a set of constraints specifying allowed combinations of values for some subset of variables. We use capitals for variables and lower case for values. We write dom(X) for the domain of possible values for X, min(X) for the smallest value in dom(X), max(X) for the greatest, and range(X) for the interval [min(X),max(X)]. A global constraint is one in which the number of variables n is a parameter. For instance, the global ALL-DIFFERENT([X1, . . . ,Xn]) constraint ensures that Xi ̸= Xj for any i < j [R´egin, 1994]. We will assume values range over 1 to d.

Constraint solvers typically use backtracking search to explore the space of partial assignments. After each assignment, propagation algorithms prune the search space by enforcing local consistency properties like domain or bound consistency. A constraint is domain consistent (DC) iff when a variable is assigned any of the values in its domain, there exist compatible values in the domains of all the other variables of the constraint. Such an assignment is called a support. A constraint is bound consistent (BC) iff when a variable is assigned the minimum or maximum value in its domain, there exist compatible values between the minimum and maximum domain value for all the other variables. Such an assignment is called a bound support. Finally, between domain and bound consistency is range consistency. A constraint is range consistent (RC) iff when a variable is assigned any value in its domain, there exists a bound support.

Constraint solvers usually enforce local consistency after each assignment down any branch in the search tree. For this reason, it is meaningful to compute the total amortised cost of enforcing a local consistency down an entire branch of the search tree so as to capture the incremental cost of propagation. We will compute complexities in this way.

3 ALL-DIFFERENT constraint

The ALL-DIFFERENT constraint is one of the most useful global constraints available to the constraint programmer. For instance, it can be used to specify that activities sharing the same resource take place at different times. A central concept in propagating the ALL-DIFFERENT constraint is the notion of a Hall interval. This is an interval of m domain values which completely contains the domains of m variables. [a, b] is a Hall interval iff |{i | dom(Xi) ⊆ [a, b]}| = b - a + 1. In any bound support, the variables whose domains are contained within the Hall interval consume all the values in the Hall interval, whilst any other variables must find their support outside the Hall interval.

[1, 1] is a Hall interval of size 1 as the domain of 1 variable, X5 is completely contained within it. Therefore we can remove [1, 1] from the domains of all the other variables. This leaves X2 with a domain containing values 2, 3, 4 and 5.

[3, 4] is a Hall interval of size 2 as it completely contains the domains of 2 variables, X1 and X3. We can thus remove [3, 4] from the domains of X2 and X4. This leaves the following range consistent domains:

Enforcing bound consistency on the same problem does not create holes in domains. That is, it would leave X2 and X4 with the values 2, 3, 4 and 5.

To identify and prune such Hall intervals from the domains of other variables, Leconte has proposed a RC propagator for the ALL-DIFFERENT constraint [Leconte, 1996] that runs in Θ(n2 ) time. We now propose a simple decomposition of the ALL-DIFFERENT constraint which permits us to enforce RC. The decomposition ensures that no interval can contain more variables than its size. We introduce O(nd2 ) new 0/1 variables, Ailu to represent whether Xi takes a value in the interval [l, u]. For 1 ≤ i ≤ n, 1 ≤ l ≤ u ≤ d and u - l < n, we post the following constraints:

We illustrate this decomposition on our running example.

Example 2. Consider again the last example (i.e. an ALL-DIFFERENT constraint on X1 ∈ [3, 4], X2 ∈ [1, 5], X3 ∈ [3, 4], X4 ∈ [2, 5] and X5 ∈ [1, 1]).

First take the interval [1, 1]. Since X5 ∈ [1, 1], (1) implies A511 = 1. Now from (2), ∑5i=1 Ai11 ≤ 1. That is, at most one variable can take a value within this interval. This means that A211 = 0. Using (1) and A211 = 0, we get X2 ̸∈ [1, 1]. Since X2 ∈ [1, 5], this leaves X2 ∈ [2, 5].

Now take the interval [3, 4]. From (1), A134 = A334 = 1. Now from (2), ∑5i=1 Ai34 ≤ 2. That is, at most 2 variables can take a value within this interval. This means that A234 = A434 = 0. Using (1) we get X2 ̸∈ [3, 4], X4 ̸∈ [3, 4]. Since X2 ∈ [2, 5] and X4 ∈ [2, 5], this leaves X2 ∈ {2, 5} and X4 ∈ {2, 5}. Local reasoning about the decomposition has thus made the original ALL-DIFFERENT constraint range consistent.

We will prove that enforcing DC on the decomposition enforces RC on the original ALL-DIFFERENT constraint. We find it surprising that a simple decomposition like this can simulate a complex propagation algorithm like Leconte's. In addition, the overall complexity of reasoning with the decomposition is similar to Leconte's propagator.

Theorem 1. Enforcing DC on constraints (1) and (2) enforces RC on the corresponding ALL-DIFFERENT constraint in O(nd3 ) down any branch of the search tree.

Proof: [Leconte, 1996] provides a necessary and sufficient condition for RC of the ALL-DIFFERENT constraint: every Hall interval should be removed from the domain of variables whose domains are not fully contained within that Hall interval. Let [a, b] be a Hall interval. That is, |H| = b - a + 1 where H = {i | dom(Xi) ⊆ [a, b]}. Constraint (1) fixes Aiab = 1 for all i ∈ H. The inequality (2) with l = a and u = b becomes tight fixing Aiab = 0 for all i ̸∈ H. Constraint (1) for l = a, u = b, and i ̸∈ H removes the interval [a, b] from the domain of Xi as required for RC.

There are O(nd2 ) constraints (1) that can be woken O(d) times down the branch of the search tree. Each propagation requires O(1) time. Constraints (1) therefore take O(nd3 ) down the branch of the search tree to propagate. There are O(d2 ) constraints (2) that each take O(n) time to propagate down the branch of the search tree for a total of O(nd2 ) time. The total running time is given by O(nd3 ) + O(nd2 ) = O(nd3 ). ✷

What about bound consistency of the ALL-DIFFERENT constraint? By using a representation that can only prune bounds [Ohrimenko et al., 2007], we can give a decomposition that achieves BC in a similar way. In addition, we can reduce the overall complexity in the case that constraints are woken whenever their bounds change. We introduce new 0/1 variables, Bik, 1 ≤ k ≤ d and replace (1) by the following constraints:

Theorem 2. Enforcing BC on constraints (2) to (4) enforces BC on the corresponding ALL-DIFFERENT constraint in O(nd2 ) down any branch of the search tree.

Proof: We first observe that BC is equivalent to DC on constraints (2) because Ailu are Boolean variables. So, the proof follows that for Theorem 1 except that fixing Ailu = 0 prunes the bounds of dom(Xi) if and only if Bi(l-1) = 0 or Biu = 1, that is, if and only if exactly one bound of the domain of Xi intersects the interval [l, u]. Only the bounds that do not have a bound support are shrunk. The complexity reduces as (3) appears O(nd) times and is woken O(d) times, whilst (4) appears O(nd2 ) times and is woken just O(1) time. ✷

A special case of ALL-DIFFERENT is PERMUTATION when we have the same number of values as variables, and the values are ordered consecutively. A decomposition of PERMUTATION just needs to replace (2) with the following equality where 1 ≤ l ≤ u ≤ d:

This can increase propagation. In some cases, DC on constraints (1) and (5) will prune values that a RC propagator for PERMUTATION would miss.

These domains are range consistent. However, take the interval [2, 2]. By DC on (1), A122 = A222 = 0. Now, from (5), we have ∑3i=1 Ai22 = 1. Thus A322 = 1. By (1), this sets X3 = 2. On this particular problem instance, DC on constraints (1) and (5) has enforced domain consistency on the original ALL-DIFFERENT constraint.

4 GCC constraint

A generalization of the ALL-DIFFERENT constraint is the global cardinality constraint, GCC([X1, . . . ,Xn], [l1, . . . , lm], [u1, . . . , um]). This ensures that the value i occurs between li and ui times in X1 to Xn. The GCC constraint is useful in resource allocation problems where values represent resources. For instance, in the car sequencing problem (prob001 at CSPLib.org), we can post a GCC constraint to ensure that the correct number of cars of each type is put on the assembly line.

We can decompose GCC in a similar way to ALL-DIFFERENT but with an additional O(d2 ) integer variables, Nlu to represent the number of variables using values in each interval [l, u]. Clearly, Nlu ∈ [∑ui=l li, ∑ui=l ui] and N1d = n. We then post the following constraints for 1 ≤ i ≤ n, 1 ≤ l ≤ u ≤ d, 1 ≤ k < u:

Enforcing RC removes 1 and 3 from X2,X4 and X5 and leaves the other domains unchanged. We can derive this from our decomposition. From the lower and upper bounds on the number of occurrences of the values, we have Nii ∈ [1, 5] except for N33 ∈ [0, 5] and we have N12 ∈ [2, 4],N13 ∈ [2, 5] and N14 ∈ [3, 5]. By (6), A333 = 1. From (7), N33 = ∑5i=1 Ai33 ∈ [1, 4]. From N15 = N14 + N55 we have N14 ∈ [3, 4] (i.e., upper bound decreased) because N15 = 5 and N55 ∈ [1, 5]. Similarly, we derive fromN14 = N13+N44 that N13 ∈ [2, 3] and from N13 = N12 +N33 that N12 ∈ [2, 2]. From the same constraint, we shrink N13 to [3, 3] and N33 to [1, 1]. Finally, N12 = N11 +N22 shrinks N11 to [1, 1]. By (6), A111 = A333 = 1, so by (7), Ai11 = 0, i ∈ {2, 3, 4, 5} and Ai33 = 0, i ∈ {1, 2, 4, 5}. By (6), this removes 1 and 3 from X2,X4,X5. Local reasoning about the decomposition has made the original GCC constraint range consistent.

We next show that enforcing DC on constraint (6) and BC on constraints (7) and (8) enforces RC on the GCC constraint.

Theorem 3. Enforcing DC on constraint (6) and BC on constraints (7) and (8) achieves RC on the corresponding GCC constraint inO(nd3 ) time down any branch of the search tree.

Proof: We use IV for the number of variables Xi whose range range(Xi) intersects the set V of values, and SV for the number of variables Xi whose range is a subset of V . We first show that if RC fails on the GCC, DC on (6) and BC on (7) and (8) will fail. We derive from [Quimper et al., 2005, Lemmas 1 and 2] that RC fails on a GCC if and only if there exists a set of values V such that SV > ∑v∈V uv or such that IV < ∑v∈V lv. Suppose first a set V such that SV > ∑v∈V uv. The fact that domains are considered as intervals implies that either range(V ) includes more variable domains than the sum of the upper bounds (like V ), or the union of the range(Xi) that are included in V lets a hole of unused values in V , which implies that there exists an interval [l, u] ⊂ V such that S[l,u] > ∑v∈[l,u] uv. So, in any case, there exists an interval [l, u] in V with S[l,u] > ∑v∈[l,u] uv. By (6) we have ∑ni=1 Ailu ≥ S[l,u] whereas the greatest value in the domain of Nlu was set to ∑v∈[l,u] uv. So BC will fail on Nlu = ∑ni=1 Ailu. Suppose now that a set V = {v1, . . . , vk} is such that IV < ∑vi∈V lvi . The total number of values taken by Xi variables being equal to n, the number of variables Xi with range(Xi) not intersecting V is greater than n - ∑vi∈V lvi , that is, S[1,v1-1] +S[v1+1,v2-1] + . . . +S[vk+1,d] > n- ∑vi∈V lvi . Thanks to (7), we know that for any l, u, Nlu ≥ S[l,u] . So, N1(v1-1)+N(v1+1)(v2-1)+. . .+N(vk+1)d > n-∑vi∈V lvi .

The initial domains of Nlu variables also tell us that for every vi in V , Nvivi ≥ lvi . Thus, min(N1(v1-1)) + min(Nv1v1 )+min(N(v1+1)(v2-1))+. . .+min(N(vk+1)d) > n = max(N1d). Successively applying BC on N1v1 = N1(v1-1)+Nv1v1 , then on N1(v2-1) = N1v1 +N(v1+1)(v2-1), and so on until N1d = N1vk + N(vk+1)d will successively increase the minimum of these variables and will lead to a failure on N1d.

We now show that when DC on (6) and BC on (7) and (8) do not fail, it prunes all values that are pruned when enforcing RC on the GCC constraint. Consider a value v ∈ dom(Xq) for some q ∈ 1..n such that v does not have any bound support. We derive from [Quimper et al., 2005, Lemmas 1 and 6] that a value v for a variable Xq does not have a bound support on GCC if and only if there exists a set V of values such that either (i) SV = ∑w∈V uw, v ∈ V and range(Xq) is not included in V , or (ii) IV = ∑w∈V lw, v /∈ V and range(Xq) intersects V . In case (i), V contains v and the values it contains will be taken by too many variables if Xq is in it. In case (ii), V does not contain v and its values will be taken by not enough variables if Xq is not in it. Consider case (i): Since DC did not fail on (6), by a similar reasoning as above for detecting failure, we derive that V is composed of intervals [l, u] such that S[l,u] = ∑w∈[l,u] uw. Consider the interval [l, u] containing v. The greatest value in the initial domain of Nlu was ∑w∈[l,u] uw, which is exactly the number of variables with range included in [l, u] without counting Xq because its range is not included in V . Thus, (7) forces Aqlu = 0 and (6) prunes value v from dom(Xq) because v ∈ [l, u] by assumption. Consider now case (ii): V = {v1, . . . , vk} is such that IV = ∑vi∈V lvi . The total number of values taken by the Xi variables being equal to n, the number of variables Xi with range(Xi) not intersecting V is equal to n- ∑vi∈V lvi , that is S[1,v1-1] +S[v1+1,v2-1] +. . .+S[vk+1,d] = n-∑vi∈V lvi . Thanks to (7), we know that for any l, u, Nlu ≥ S[l,u] . So, N1(v1-1)+N(v1+1)(v2-1)+. . .+N(vk+1)d ≥ n-∑vi∈V lvi . The initial domains of Nlu variables also tell us that for every vi in V , Nvivi ≥ lvi . Thus, min(N1(v1-1)) + min(Nv1v1 )+min(N(v1+1)(v2-1))+. . .+min(N(vk+1)d) ≥ n = max(N1d). Successively applying BC on N1v1 = N1(v1-1)+Nv1v1 , then on N1(v2-1) = N1v1 +N(v1+1)(v2-1), and so on until N1vk = N1(vk-1) + Nvkvk will increase all min(N1(vi-1)) and min(N1vi ), to the sum of the minimum values of the variables in the right side of each constraint so that min(N1vk ) = min(N1(v1-1))+min(Nv1v1 )+ min(N(v1+1)(v2-1)) + . . . + min(Nvkvk ). Then, because max(N1d) = n, BC on N1d = N1vk + N(vk+1)d will decrease the maximum value of N1vk and N(vk+1)d to their minimum value, BC on N1vk = N1(vk-1) + Nvkvk will decrease the maximum value of N1(vk-1) and Nvkvk to their minimum value, and so on until all N(vi+1)(vi+1-1) are forced to the singleton min(N(vi+1)(vi+1-1)) = S[vi+1,vi+1-1] . At this point, (7) forces Aj(vi+1)(vi+1-1) = 0 for every variable Xj with range not included in the interval [vi + 1, vi+1 - 1] because that interval is saturated by variables Xp in S[vi+1,vi+1-1] , for which Ap(vi+1)(vi+1-1) = 1. By assumption value v is not in V , so there exists such an interval [vi + 1, vi+1 - 1] that contains v. Furthermore, range(Xq) intersects V , so it is not included in [vi +1, vi+1 - 1]. Therefore, Aq(vi+1)(vi+1-1) is forced to 0 and (6) prunes v from dom(Xq ).

There are O(nd2 ) constraints (6) that can be woken O(d) times down the branch of the search tree in O(1), so a total of O(nd3 ) down the branch. There are O(d2 ) constraints (7) which can be woken O(n) times each down the branch for a total cost in O(n) time down the branch. Thus a total of O(nd2 ). There are O(d2 ) constraints (8) that can be woken O(n) times down the branch. Each propagation takes O(1) time to execute for a total of O(nd2 ) time down the branch. The final complexity down the branch of the search tree is therefore O(nd3 ) + O(nd2 ) + O(nd2 ) = O(nd3 ). ✷

What about bound consistency of the GCC constraint? As in the case of ALL-DIFFERENT, by replacing constraints (6) by constraints (3) and (4), the decomposition achieves BC.

Theorem 4. Enforcing BC on constraints (3), (4), (7) and (8) achieves BC on the corresponding GCC constraint in O(nd2 ) time down any branch of the search tree.

Proof: The proof follows that for Theorem 3 except that fixing Ailu = 0 prunes the bounds of dom(Xi) if and only if exactly one bound of the domain of Xi intersects the interval [l, u]. The complexity reduces to O(nd2 ) as BC on (3) and (4) is in O(nd2 ) (see Theorem 2) and BC on (7) and (8) is in O(nd2 ) (see Theorem 3). ✷

The best known algorithm for BC on GCC runs in O(n) time at each call [Quimper et al., 2005] and can be awaken O(nd) times down a branch. This gives a total of O(n2d), which is greater than the O(nd2 ) here when n > d. Our decomposition is also interesting because, as we show in the next section, we can use it to combine together propagators.

5 Other global constraints

Many other global constraints that count variables or values can be decomposed in a similar way. For example, the global constraint SAME([X1, . . . ,Xn], [Y1, . . . , Yn]) is satisfied if and only if the Yi variables are a permutation of the Xi variables. A monolithic flow-based propagator for this constraint is given in [Beldiceanu et al., 2004]. The following decomposition encodes the SAME constraint where 1 ≤ i ≤ n, 1 ≤ l ≤ u ≤ d, l ≤ k and k < u:

This decomposition can be obtained by posting decompositions for EGCC([X1, . . . ,Xn], [O1, . . . ,Om]) and EGCC([Y1, . . . , Yn], [O1, . . . ,Om]) and eliminating common sub-expressions (EGCC is an extended form of the GCC constraint in which upper and lower bounds on occurrences of values are replaced by integer variables). This is another argument in favor of decompositions since it allows constraints to share "internal" state through common intermediate variables. Such sharing can increase propagation.

If we have Oi ∈ [0, 1] for 1 ≤ i ≤ 5 then both EGCC([X1, X2], [O1, O2, O3, O4, O5]) and EGCC([Y1, Y2], [O1, O2, O3, O4, O5]) are BC. However, enforcing BC on the decomposition of SAME([X1,X2], [Y1, Y2]) removes 3 from the domain of X2 and Y1.

In fact, we conjecture that enforcing BC on this decomposition achieves BC on the SAME constraint itself. Similar decompositions can be given for other global constraints like NVALUE and COMMON.

6 Experimental Results

To test these decompositions, we ran experiments on pseudo-Boolean encodings (PB) of CSPs containing ALL-DIFFERENT and PERMUTATION constraints. We used the MiniSat+ 1.13 solver on an Intel Xeon 4 CPU, 2.0 Ghz, 4G RAM with a timeout of 600 seconds for each experiment. Our decompositions contain two types of constraints: SUM constraints like (2) and MEMBER constraints like (1). The SUM constraints is posted directly to the MiniSat+ solver. To encode MEMBER constraints, we use literals Bij for the truth of Xi ≤ j [Ohrimenko et al., 2007], and clauses of the form (Ailu = 1) ⇔ (Bi(l-1) = 0 ∧ Biu = 1). This achieves bound consistency (Theorem 2). To increase propagation, we use a direct encoding with literals Zij for the truth of Xi = j and clauses (Ailu = 0) ⇒ (Zij = 0), j ∈ [l, u]. The overall consistency achieved is therefore between BC and RC. We denote this encoding HI. To explore the impact of small Hall intervals, we also tried HIk, a PB encoding with only those constraints (2) for which u - l + 1 ≤ k. This detects Hall intervals of size at most k. Finally, we decomposed ALL-DIFFERENT into a clique of binary inequalities, and used a direct encoding to convert this into SAT (denoted BI).

Pigeon Hole Problems. Table 1 gives results on pigeon hole problems (PHP) with n pigeons and n1 holes. Our decomposition is both faster and gives a smaller search tree compared to the BI decomposition. On such problems, detecting large Hall intervals is essential.

Double-Wheel Graceful Graphs. The second set of experiments uses double-wheel graceful graphs [Petrie and Smith, 2003]. We converted the CSP model in [Petrie and Smith, 2003] into a PB formula. This model has an ALL-DIFFERENT constraint on node labels and a PERMUTATION constraint on edge labels. For the PERMUTATION constraint we use (5). We strengthen the BI decomposition with clauses to ensure that every value appears at least once. Table 2 show that our decomposition outperforms the augmented BI decomposition on many instances. Whilst detecting large Hall intervals can greatly reduce search, in some cases the branching heuristics appear to be fooled by the extra variables introduced in the encodings.

Overall these experiments suggest that detecting Hall intervals reduces search significantly, and focusing on small Hall intervals may be best except on problems where large Hall intervals occur frequently.

7 Other RelatedWork

The ALL-DIFFERENT constraint first appeared in the ALICE constraint programming language [Lauriere, 1978]. Regin proposed a DC propagator that runs in O(n2.5 ) time [R´egin, 1994]. Leconte gave a RC propagator based on Hall intervals that runs in O(n2 ) time [Leconte, 1996]. Puget then developed a BC propagator also based on Hall intervals that runs in O(n log(n)) time [Puget, 1998]. This was later improved by Melhorn and Thiel [Mehlhorn and Thiel, 2000] and then Lopez-Ortiz et al. [Lopez-Ortiz et al., 2003].

The global cardinality constraint, GCC was introduced in the CHARME language [Oplobedu et al., 1989]. Regin proposed a DC propagator based on network flow that runs in O(n2 ) time [R´egin, 1996]. Katriel and Thiel proposed a BC propagator for the EGCC constraint [Katriel and Thiel, 2003]. Quimper et al. proved that enforcing DC on the EGCC constraint is NP-hard [Quimper et al., 2004]. They also improved the time complexity to enforce DC and gave the first propagator for enforcing RC on GCC.

Many decompositions have been given for a wide range of global constraint. However, decomposition in general tends to hinder propagation. For instance, [Stergiou and Walsh, 1999] shows that the decomposition of ALL-DIFFERENT constraints into binary inequalities hinders propagation. On the other hand, there are global constraints where decompositions have been given that do not hinder propagation. For example, Beldiceanu et al. identify conditions under which global constraints specified as automata can be decomposed into signature and transition constraints without hindering propagation [Beldiceanu et al., 2005]. As a second example, many global constraints can be decomposed using ROOTS and RANGE which can themselves often be propagated effectively using simple decompositions [Bessiere et al., 2005; 2006a; 2006b]. As a third example, decompositions of the REGULAR and CFG constraints have been given that do not hinder propagation [Quimper and Walsh, 2006; 2007; 2008; Bessiere et al., 2008; Katsirelos et al., 2008]. As a fourth example, decompositions of the SEQUENCE constraint have been shown to be effective [Brand et al., 2007]. Finally, the PRECEDENCE constraint can be decomposed into ternary constraints without hindering propagation [Walsh, 2006].

8 Conclusions

We have shown that some common global constraints like ALL-DIFFERENT and GCC can be decomposed into simple arithmetic constraints whilst still maintaining a global view that achieves range or bound consistency. These decompositions are interesting for a number of reasons. First, we can easily incorporate them into other solvers. Second, the decompositions provide other constraints with access to the state of the propagator. Third, these decompositions provide a fresh perspective on propagation of global constraints. For instance, our results suggest that it may pay to focus propagation and nogood learning on small Hall intervals. Finally, these decompositions raise an important question. Are there propagation algorithms that cannot be efficiently simulated using decompositions? In [Bessiere et al., 2009], we use circuit complexity to argue that a domain consistency propagator for the ALL-DIFFERENT constraint cannot be simulated using a polynomial sized decomposition.