Propagating Logical Combinations of Constraints

1 Introduction

Real world problems often contain logical combinations of numerical and symbolic constraints. For example, many configuration problems are naturally specified using implication and other logical connectives (e.g. if the car is a coupe or a convertible then a roof rack is not a valid option). To facilitate the modeling of such problems, constraint toolkits allow logical combinations of primitive constraints to be posted. However, such combinations are typically not propagated very effectively. For example, the propagation of a disjunction of constraints is generally delayed until all but one of the disjuncts are falsified after which the remaining disjunct (which must now hold) is propagated.

We will present a simple and light weight method to propagate constraint expressions built up from logical connectives and primitive constraints. This method can be incorporated into any current constraint toolkit by a simple extension to the propagators for the primitive constraints. We can therefore provide the user with a rich language for specifying problems, whilst preserving the ability to prune the search space. To demonstrate the usefulness of such a facility, we show that many global constraints can be easily specified and, in some cases, effectively propagated, using simple constraint expressions. Thus our method can often provide the toolkit user with a very low cost alternative to the enterprise of designing and implementing special purpose propagators for unusual global constraints that might appear in their problem.

∗This research funded by NSERC Canada.

†This research funded in part by National ICT Australia.

Toby Walsh† NICTA and UNSW Sydney, Australia

tw@cse.unsw.edu.au

2 Inconsistent and Valid Assignments

A constraint satisfaction problem consists of a set of variables, each with a domain of values, and a set of constraints. Each constraint consists of a scope of variables to which it is applied, and a relation of allowed values for those variables. For convenience, we represent the domains D of the variables by the set of possible assignments. For example, if we have two 0/1 variables, X and Y then D = {X = 0,X = 1, Y = 0, Y = 1}. We let domain(X) be the set of values in the domain of the variable X: domain(X) = {a | X = a ∈ D}. An assignment set τ is a set of assignments to variables such that no variable is assigned more than one value by τ. The scope of an assignment set τ (constraint C) is the set of variables in τ (C) and is denoted by scope(τ) (scope(C)). Given a constraint C and an assignment set τ with scope(C) ⊆ scope(τ), we write C(τ) iff the assignments in τ satisfies C. That is C(τ) iff there exists X1 = a1, ..,Xk = ak ∈ τ with scope(C) = {X1, .., Xk} and X1 = a1, .., Xk = ak satisfies C. We write ¬C(τ) otherwise.

An assignment is (generalized arc) inconsistent for a constraint iff no assignment set containing it satisfies the constraint. That is, X = a is inconsistent for C iff ∀τ.(scope(C) ⊆ scope(τ) ∧ X = a ∈ τ )→ ¬C(τ). A constraint C has an unique maximal set of inconsistent assignments MaxInc(C). For example, given the constraint X < Y with X = {0, 1, 2} and Y = {1, 2}, then {X = 2} is the maximal set of inconsistent assignments. Assignments that are consistent have at least one witness falsifying the above condition; i.e., X = a is consistent iff there is an assignment set τ (called a support) with scope(τ) = scope(C) ∧X = a ∈ τ ∧C(τ ). A constraint C is GAC (Generalized Arc Consistent) iff every value of every variable in scope(C) has at least one support. If X = a is inconsistent, we can prune a from the domain of X. A constraint C can be made GAC by simply pruning all values in MaxInc(C) from the domains of their respective variables.

An essential notion for our approach is the concept of a valid assignment. Valid assignments are the dual of inconsistent assignments. An assignment is valid for a constraint iff all assignment sets containing it satisfy the constraint. That is, X = a is valid for C iff ∀τ.(scope(C) ⊆ scope(τ) ∧X = a ∈ τ ) → C(τ). As with inconsistent values every constraint C has a unique maximal set of valid assignments, MaxValid(C). For example, given the constraint X < Y

with X = {0, 1, 2} and Y = {1, 2}, the maximal set of valid assignments is {X = 0}. All possible extensions of X = 0 satisfy the constraint X < Y , but all other assignments to X can be extended so that they fail to satisfy the constraint.

All of the concepts presented for inconsistent assignments have dual versions for valid assignments. For example, the dual of consistent assignments is the notion of non-valid assignments. An assignment X = a is non-valid if there is at least one assignment set τ with scope(τ) = scope(C)∧X = a ∈ τ ∧ ¬C(τ). Another example is that the dual of a support is a non-support. An assignment set τ is a nonsupport for an assignment X = a in a constraint C iff scope(τ) = scope(C)∧X = a ∈ τ ∧¬C(τ). A non-support witnesses the non-validity of X = a.

3 Constraint Expressions

To build complex constraints, we combine primitive constraints using negation, disjunction and conjunction. A constraint expression is either a primitive constraint C or any well-founded Boolean expression of the form: true, false, not(C1), or(C1, .., Ck) or and(C1, .., Ck), where each Ci is itself a constraint expression. true is the primitive constraint which is always valid, whilst false is always inconsistent. We also allow the expressions implies(C1, C2), iff (C1, C2), xor(C1, C2) and ifthen(C1, C2, C3), but regard these additional connectives to be abbreviations:

Each constraint expression C represents a new constraint whose scope is equal to the union of the scopes of the primitive constraints in C. An assignment set τ satisfies C iff scope(C) ⊆ scope(τ) and the Boolean expression representing C evaluates to true given the truth values of the component primitive constraints under τ . For example, an absolute value constraint X = abs(Y ) can be written as the constraint expression ifthen(Y ≥ 0, X = Y, X = -Y ). Similarly, a max constraint X = max(Y, Z) can be written as the constraint expression and (X ≥ Y, X ≥ Z, or (X = Y, X = Z)).

Since a constraint expression is itself a constraint, associated with every constraint expression C is a maximal set of inconsistent assignments, MaxInc(C), and a maximal set of valid assignments MaxValid(C). We can make the constraint expression C generalized arc consistent by pruning all assignments in MaxInc(C). It is also useful to observe that the duality between valid assignments and inconsistent assignments implies MaxInc(C) = MaxValid(not(C)): X=a ∈ MaxInc(C) ↔ (∀τ.X=a ∈ tau → (¬C(τ) ↔ not (C)(τ )))↔ X=a ∈ MaxValid (not (C)).

4 Constraint Propagation

Not surprisingly, it is NP-hard to computeMaxInc for an arbitrary constraint expression. More precisely, deciding if a set of assignments is the maximal inconsistent set for an arbitrary constraint expression is DP -complete in general. 1 There are results on tractable languages that identify tractable cases for computing MaxInc and MaxValid. However, we are interested here in computing inconsistent assignments for arbitrary constraint expressions, which is intractable in general.

We propose a simple and light weight method for computing subsets of MaxInc and MaxValid in polynomial time. The method is compositional, computing the inconsistent and valid assignments of a constraint expression from the inconsistent and valid assignments of its parts. For a constraint expression C and variable domains D, the functions Inc(C, D) and Valid (C, D) return subsets of MaxInc(C) and MaxValid (C) respectively. These functions recursively apply the rules in Table 1, until they reach the primitive constraints. We assume that each primitive constraint has a poly-time algorithm to compute inconsistent and valid assignments.

The algorithm can be optimized by a simple caching scheme in which we remember the previously computed value Inc(Ci,D) for each subexpression Ci. If in a subsequent call Inc(Ci,D′ ), D′ is identical to D when restricted to the variables in scope(Ci), then we can reuse the previously computed result for Inc(Ci, D). A similar optimization works for Valid(Ci, D). In addition, if we compute and prune inconsistent values incrementally, we can stop as soon as any variable has a domain wipeout.

4.1 Entailment and Disentailment

A constraint expression is entailed iff it holds for all possible assignments. A constraint is disentailed iff it does not hold for any possible assignment. As we show below, Valid (C, D) returns only valid assignments. Hence, if Valid(C, D) equals the domains of all of the variables in the scope of C, C must be entailed. In such a situation, we modify the computation of Valid so that Valid(C,D) = D (note that D might include domains of other variables besides those in the scope(C)). Similarly, if Inc(C,D) equals the domains of all of the variables in the scope of C then C is disentailed; and we modify the computation of Inc so that Inc(C, D) = D.

1 The complexity class DP contains problems which are the conjunction of a problem in NP and one in coNP [Papadimitriou and Yannakakis, 1984].

To show the benefit, consider implies(even(X), odd(Y )) with D={X=0, X=2, Y=1, Y=2}. Now Inc(implies(even(X), odd(Y )), D) = Valid(even(X), D) ∩ Inc(odd(Y ),D). Using the unmodified versions, Valid(even(X), D) will return just valid values for X, whilst Inc(odd(Y )), D) returns just inconsistent values for Y . Inc would then compute the empty set of inconsistent assignments for implies(even(X), odd(Y )). Note, however, that domain(X) only contains even numbers. Hence even(X) is entailed. Therefore the modified Valid(even(X), D) can return D, in which case Inc(implies(even(X), odd(Y ), D) = D ∩ Inc(odd(Y ), D) = {Y=2}. As required, this is the maximal set of inconsistent assignments.

4.2 Correctness

We prove that Inc and Valid are correct. That is, they only return inconsistent and valid assignments respectively.

Theorem 1 Inc and Valid are correct assuming that inconsistent and valid assignments are correctly computed for the constituent primitive constraints.

Proof: By induction on the structure of the constraint expression. The base case holds by assumption. The step case uses case analysis.

For a constraint expression not(C1,D), we have that Inc(not(C1),D) = Valid(C1,D). By induction, the assignments in Valid(C1,D) are valid. Hence all of these assignments are inconsistent for not(C1,D). A dual argument shows that the assignments in Valid(not(C1),D) are valid.

For a constraint expression C = and(C1, .., Ck), we have Valid(C,D) = ⋂i Valid(Ci,D). Suppose X = a ∈ Valid(C,D). Then for all i, X = a ∈ Valid(Ci,D). By the induction hypothesis, the assignments in each Valid(Ci) are valid. Consider any assignment set τ such that X = a ∈ τ and scope(C) ⊆ scope(τ). Since X = a is valid for each Ci, τ must satisfy all Ci and thus must satisfy the conjunction. Hence X = a is also valid for C. For C = Inc(and(C1, .., Ck), D) a similar argument shows that the assignments in ⋃i Inc(Ci,D) are inconsistent. Deleting these assignments from D cannot cause any consistent assignment to lose its support, hence Inc(Ci,D′ ) on the reduced domain D′ must still return inconsistent assignments. ItInc then recomputes ⋃i Inc(Ci, D) until we reach a fixed point.

Similar arguments hold for constraint expressions of the form or (C1, .., Ck). ✷

4.3 Termination

The ItInc and ItValid functions only require a linear (in the size of the CSP) number of iterations to reach their fixed point in the worst case.

Theorem 2 ItInc and ItValid takeO(nd) iterations to reach their fixed points for a constraint expression with n variables and domains of size d. There exist constraint expressions which take Θ(nd) iterations to reach the fixed point.

Proof: As each iteration removes at least one value, we must reach the fixed point in at most nd steps. We can give a simple example in which this bound is reached. Consider and(C1, .., Cn) where Ci is Xi = Xi+1 for i < n and X1 - Xn = 1 for i = n. Suppose domain(Xi) = {1, .., d} for every i. Then in the first iteration, ItInc returns {X1 = 1} as this value is not supported in X1 - Xn = 1. After this is pruned from D, a second iteration returns {X2 = 1} as this value is now not supported in X1 = X2. And so on up to the nth iteration which returns {Xn = 1}. After this is pruned, the n + 1th iteration returns {X1 = 2} as this value is now not supported in X1 -Xn = 1. Hence, there are nd iterations before all the values of all the variables are removed. Note that even if we stop when the first variable has a domain wipeout, it will still take (n-1)d+1 iterations. ✷

4.4 Maximality

These functions do not always compute maximal sets, even if maximal sets are computed for the primitive constraints from which they are composed. This is not surprising given that computing maximal sets for an arbitrary constraint expression is intractable in general. The following result precisely characterizes when Inc returns the maximal inconsistent set of assignments. In other words, the following result identifies exactly when pruning the values returned by Inc ensures that a constraint expression is GAC.

We start with a number of definitions. A hypergraph H = (H,EH ) is a set of vertices H and hyperedges E H each of which is a subset of H. A hypergraph H has an acyclic tree decomposition [Flum et al., 2002] iff there is a tree T satisfying: (1) there is a one-to-one correspondence between the hyperedges of H and the nodes of T; the hyperedge corresponding to a tree node t is called t's label (label(t)); (2) for every vertex v ∈ H the set of nodes t of T such that v ∈ label (t) form a subtree of T . The hypergraph of a conjunctive or disjunctive constraint expression, C = and(C1, .., Ck) or C = or(C1, .., Ck), has the variables in scope(C) as vertices and the sets of variables scope(Ci), i = 1, .., k as hyperedges. We will relax this definition to take account of (dis)entailment. If C = and(C1, .., Ck) then we ignore any entailed subexpression when constructing the hypergraph. Similarly, if C = or(C1, .., Ck) then we ignore any disentailed subexpression. Under this relaxation we define a conjunctive or disjunctive constraint expression to be acyclic if its corresponding hypergraph has an acyclic tree decomposition. For example, a conjunction in which the primitive constraints are in a chain, and each has only one variable in common with the previous and next constraint is acyclic. Acyclicity is, however, more general than being a chain. We will use acyclicity to characterize when Inc computes MaxInc.

Theorem 3 For any constraint expression C and any variable domains D, Inc(C, D) = MaxInc(C, D) if:

1. C is a primitive constraint and Inc(C,D) = MaxInc(C, D);
2. C = not(C1) and Valid(C1,D) =MaxValid(C1,D);
3. C = or (C1, .., Ck) and Inc(Ci, D) = MaxInc(Ci, D) for i ∈ (1, .., k);
4. C = and(C1, .., Ck) and (a) Inc(Ci,D) = MaxInc(Ci,D) for i ∈ (1, .., k); (b) C is acyclic; and (c) |scope(Ci) ∩ scope(Cj)| ≤ 1 for i, j ∈ (1, .., k);

Proof: 1. Immediate.

1. Suppose Valid(C1,D) is maximal. Then for any X = a ̸∈ Valid(C1,D), there exists τ with X = a ∈ τ and ¬C1(τ). Hence X = a cannot be in Inc(not(C1),D) as τ is one assignment that prevents it being inconsistent. Hence Inc(not(C1), D) is maximal.
2. Suppose Inc(Ci,D) are maximal. Consider X = a ̸∈ Inc(or(C1, .., Ck),D). Then X = a ̸∈ ⋂1≤i≤k Inc(Ci,D). That is, X = a ̸∈ Inc(Cj,D) for some j ∈ (1, .., k). As Inc(Cj,D) is maximal, there exists τ with X = a ∈ τ and Cj(τ). Thus X = a cannot be in Inc(or(C1, .., Ck),D) as τ is one assignment that prevents it being inconsistent. Hence Inc(or(C1, .., Ck), D) is maximal.

4. Suppose X ∈ scope(C) with X = a ∈ D, but X = a ̸∈ Inc(C, D). We must show that X = a ̸∈ MaxInc(C, D). Let Dc = D-Inc(C, D), i.e., the consistent assignments remaining in the variable domains. From Table 1 we observe that Inc(Ci,Dc ) = ∅ and by condition (a) MaxInc(Ci,Dc ) = ∅ for all i ∈ (1, .., k). Consider the acyclic tree decomposition associated with C. Orient this tree so that the root is labeled with scope(Ci) for some Ci with X ∈ scope(Ci). Note that by property (2) of an acyclic tree decomposition and condition (c), each of the subtrees below Ci can have at most one variable in common with the other subtrees. Furthermore if two subtrees do have a variable in common that variable must be in the scope(Ci).

Since X = a ∈ Dc it must have some support τ on Ci such that τ ∈ Dc . Now we extend this support downwards in the tree decomposition to the children of Ci: C 1 j , .., C ℓ j . Each such child Cj shares only one variable with Ci, say Y , and Y must be assigned some value in τ, say Y = b. Since Y = b ∈ D c it must have a support τj in Cj such that τj ∈ Dc . Thus we can extend τ to a support for and(Ci, Cj) for each child of Ci. Furthermore the supports τj for the individual children of Ci cannot be in conflict: Cj and Cj′ can only share a variable already assigned by τ, hence τj and τj′ must agree with τ and with each other on the value assigned to this variable. Thus we can extend τ to a support for all of Ci's children. Furthermore, by the same argument each support τj for the child Cj can be extended to a support for all of the conjuncts in the subtree below Cj. Hence, τ can be extended to a support for all of C, and since X = a ∈ τ , X = a ̸∈ MaxInc(C, D).

Note that if and(C1, .., Ck) contains any entailed conjuncts, these can be eliminated without changing the maximal set of inconsistent assignments. We can then apply the argument above to the remaining acyclic part of the conjunction.

5. Immediate since MaxInc(C,D) ⊆D. ✷

In fact, we can show that these five cases are the only ones in which Inc is always guaranteed to be maximal. This reverse direction needs a little care as Inc may compute MaxInc by chance. However, these five cases are the only ones in which, irrespective of the constraint subexpressions, Inc is guaranteed to compute MaxInc. A dual result holds, and characterizes precisely when Valid computes MaxValid .

Previous related results have shown that acyclic database queries of bounded tree width are tractable. Bounded tree width (tree width one) is also known to be the condition that characterizes when arc consistency achieves GAC on conjunctions of binary constraints. The main difference between our result and these previous results is that we do not place any restriction on the arity of the primitive constraints. Hence, our result does not depend on bounded tree width (the tree width of the constraint graph is at least as large as the arity of the primitive constraints). Given primitive constraints for which GAC can be efficiently computed (no matter their arity), our result characterizes when this efficiency can be lifted to complex combinations of these constraints.

5 Some Applications

To demonstrate the usefulness of constraint expressions and our propagation algorithm, we show that a wide range of global and other constraints can be specified and propagated using simple constraint expressions. In many cases, our light weight propagation algorithm is able to achieve GAC. Our method is then an effective and low cost means to implement these constraints. This is especially valuable when the constraints useful for a particular problem are too specialized to be in the user's constraint toolkit.

DOMAIN constraint. This channels between a variable and a sequence of 0/1 variables representing the possible values taken by the variable. More precisely, DOMAIN(X, [X1, .., Xn]) ensures X = i iff Xi = 1 [Refalo, 2000]. We can decompose this into a disjunction:

The equality constraints in each conjunct again have no variables in common. Hence pruning the values returned by Inc enforces GAC.

ELEMENT constraint. This indexes into an array with a variable [Van Hentenryck and Carillon, 1988]. More precisely, ELEMENT(I, [X1, ..,Xn], J) holds iff XI = J. We can use this to look up the price of a particular component included in a configuration problem. It decomposes into a simple disjunction:

The equality constraints within each conjunct share no variables. Hence pruning the values returned by Inc enforces GAC.

MEMBER constraint. This ensures that a particular value is used. More precisely, MEMBER(I, [X1, ..,Xn]) holds iff there exists j with Xj = I. We can decompose this into a disjunction:

Pruning the values returned by Inc enforces GAC.

MAX constraint. This computes the maximum value taken by a sequence of variables. More precisely, MAX(N, [X1, ..,Xn]) holds iff there exists i with N = Xi and Xi ≥ Xj for all j. A MAX constraint can be decomposed into a disjunction:

Pruning the values returned by Inc on such a decomposition enforces GAC.

CHANNELLING constraints. It is often advantageous to specify multiple viewpoints of a problem. Constraints may be easier to specify in one viewpoint and propagate better in another. Channelling constraints are then needed to link the different viewpoints. For example, multiple viewpoints have proved useful in the orchestra rehearsal problem, prob039 in CSPLIB. The channelling constraints used here can be specified as constraint expressions:

The problem also contained a specialized optimality constraint which can be specified as the constraint expression:

Where WX = 1 can itself be specified with an ELEMENT constraint.

LEX constraint. This lexicographically orders two vectors of variables. It has many applications when dealing with symmetry [Frisch et al., 2002]. We can decompose it into a disjunction:

As the constraints in each conjunct share no variables, pruning the values returned by Inc enforces GAC on the LEX constraint. In addition, if we memoize previous results, Inc will be comparable to the efficient algorithm in [Frisch et al., 2002].

The choice of decomposition of a global constraint is important for ensuring as much propagation as possible. For instance, an alternative decomposition is the conjunction:

Pruning the values returned by Inc on this decomposition may not enforce GAC on the LEX constraint. Consider X1 and Y1 ∈ {0, 1}, X2 = 1 and Y2 = 0. Then X1 = 1 and Y1 = 0 are both inconsistent assignments. However, Inc applied to this decomposition will return the empty set.

VALUE PRECEDENCE constraint. This breaks symmetries in a sequence of variables, X1 to Xn caused by two indistinguishable values s and t [Law and Lee, 2004]. We can decompose it into a simple conjunction:

Theorem 2 of [Law and Lee, 2004] shows that enforcing GAC on each conjunct achieves GAC on the global constraint. As each conjunct expands out into a simple disjunction, pruning the values returned by Inc enforces GAC on the global constraint.

AMONG constraint. This limits the number of variables taking values from a set [Beldiceanu and Contejean, 1994]. More precisely, AMONG([X1, ..,Xn], [d1, .., dm],N) holds iff N = |{i|Xi = dj}|. The constraint is useful in many resource allocation and scheduling problems. By introducing additional variables Ni in which to accumulate a count, we can decompose this into a relatively simple constraint expression:

where Xi ∈ D is an abbreviation for or(Xi = d1, ..,Xi = dm).

Unfortunately, Inc does not achieve GAC on such a decomposition. Consider, for example, X1,X2 ∈ {0, 1}, N ∈ {0, 1, 2} and N1 ∈ {0, 1}. Enforcing GAC on AMONG([X1,X2], [0, 1],N) will prune 0 and 1 from N whilst Inc returns the empty set. Similar decompositions and results hold for the ATMOST, ATLEAST, CHANGE, and COUNT constraints.

NOTALLEQUAL constraint. This ensures that not all variables take the same value [Beldiceanu and Contejean, 1994]. More precisely, NOTALLEQUAL([X1, ..,Xn]) holds iff there exists i and j with Xi ̸= Xj. This can be decomposed into the following constraint expression:

Pruning the values returned by Inc enforces GAC.

NVALUE constraint. This counts the number of values used by a sequence of variables [Pachet and Roy, 1999]. More precisely, NVALUE([X1, ..,Xn],N) holds iff |{Xi|1 ≤ i ≤ n}| = N. The constraint is useful in a wide range of problems involving resources 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].

One way to propagate this constraint in polynomial time is to decompose it with an additional set of 0/1 variables representing the characteristic function of the set of values used:

Where the domains of the Xi are assumed to be from 1 to m. Not surprisingly, Inc does not compute the maximal set of inconsistent assignments for this constraint expression. For example, suppose X1, X2 ∈ {1, 2}, X3 ∈ {1, 2, 3}, N = 3 and Si = 1 for 1 ≤ i ≤ 3. Then Inc returns the empty set, even though X3 = 1 and X3 = 2 are inconsistent.

A similar decomposition and result holds for the COMMON constraint, which is also NP-hard to propagate.

6 RelatedWork

Lhomme has proposed GAC algorithms for logical combinations of primitive constraints, focused primarily on those that are given in extension [Lhomme, 2004]. For example, on a disjunction like or(C1, ..,Ck), the algorithm tests each assignment for membership in ⋂i MaxInc(Ci). If the assignment is not inMaxInc(Ci) for some i, the remainingMaxInc sets do not have to be tested. However, in the worst case, we still have to compute MaxInc for all of the primitive constraints, as we require in our method.

Bessi`ere and R´egin have proposed an algorithm for enforcing GAC on a conjunction of primitive constraints [Bessi`ere and R´egin, 1998]. However, as could be expected, this requires O(dn ) time in the worst case.

Other approaches to propagating constraint expressions are based on reification or delaying. It is not hard, however, to show that Inc provides strictly more pruning. Suppose we have a disjunction like or (X < 2, X > 4). We can reify this into B1 ↔ X < 2, B2 ↔ X > 4, and B1 + B2 > 0. These constraints are delayed until either inequality is entailed or disentailed. However, Inc can prune values immediately. Consider X ∈ {1, 3, 5}. Then neither inequality is entailed or disentailed. However, Inc will return the inconsistent assignment X = 3.

To perform more pruning on such disjunctions, cc(FD) introduced constructive disjunction [Van Hentenryck et al., 1998]. If any of the disjuncts, Ci in a constructive disjunction, C1 ∨c .. ∨c Ck is entailed by the constraint store, then the constructive disjunction is satisfied. Otherwise, each constraint Ci is added in turn to the constraint store and propagated. The resulting inconsistent assignments are recorded, the state restored, and the next constraint is processed. The intersection of the inconsistent assignments found for each constraint are then taken to be the inconsistent assignments for the disjunction. Constructive disjunction can do more pruning than enforcing GAC. For example, even though both or(X = 0, Y = 0) and X = Y on 0/1 variable are GAC, propagating X = 0 ∨c Y = 0 and X = Y prunes X = Y = 1. This extra pruning arises from interaction between the disjunctive constraint and the other constraints in the constraint store. For this reason, constructive disjunction can be very expensive, and may not justify its costs in practice [J. W¨urtz and T. M¨uller, 1996].

The cardinality constraint can be used to implement conjunction, disjunction, negation, as well as a host of other useful constraints [Van Hentenryck and Deville, 1991]. However, only a very restricted form of consistency is enforced on the cardinality constraint, and Inc does more pruning in general. For example, if C1 is X = 0, C2 is X = 1 and D = {X = 0, X = 1, X = 2} then Inc(or (C1, C2), D) = {X = 2}. Pruning X = 2 makes the problem GAC. However, the equivalent cardinality constraint, card(N, [C1,C2]) where N ≥ 1 is consistent without any prunings.

In contrast to these previous works, we have provided a tractable method for computing a subset of MaxInc that does a useful amount of constraint propagation. Our algorithm is compositional as it uses the propagators provided for the primitive constraints. Hence it can be applied to complex, nested logical expressions.

7 Conclusion

We have proposed a simple and light weight method for propagating logical combinations of primitive constraints. Since computing the maximal set of inconsistent assignments for such constraint expressions is intractable in general, we have given a polynomial time function which computes a tractable subset compositionally. We characterized precisely when this function computes the maximal set of inconsistent assignments. Finally we have shown that many different global constraints can be implemented using these methods. There remain many interesting directions to follow both from a theoretical and practical perspective. For example, how do we compute and use nogoods for constraint expressions?