Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction

1 Introduction

The task at hand is on how to relax or weaken some of the hard constraints in an over-constrained problem so as to obtain useful partial solutions. Weighted constraint satisfaction [Schiex et al., 1995] is a framework for handling such tasks. While the basic technique for solving weighted constraint satisfaction problems (WCSPs) relies on a form of branch-and-bound search, various consistency notions and techniques [Larrosa and Schiex, 2003; 2004; Sanchez et al., 2008] for unary, binary, and ternary constraints have been developed to help prune the search space. Higher arity constraints have to be either first converted to their binary counterparts or activated only after enough variables are instantiated during search. The lack of efficient handling of nonbinary constraints in WCSP systems greatly restricts the applicability of WCSP techniques to complex real-life problems.

∗We thank the anonymous referees for their constructive comments. The work described in this paper was substantially supported by grants CUHK413207 and CUHK413808 from the Research Grants Council of Hong Kong SAR.

Incorporating arbitrary soft n-nary constraints into WCSP can be difficult since the costs have to be represented extensionally and maintained in an n-dimensional table, incurring time and space overheads. Soft global constraints are non-binary constraints with semantics. In particular, the cost structure of flow-based soft global constraints [van Hoeve et al., 2006] can be formulated as a flow network, allowing the computation of the minimum cost of the soft global constraints using minimum cost flow algorithm. This is useful in estimating the lower bound of the current search path. We show that a naive incorporation of flow-based soft global constraints into WCSP would result in a strong form of the ∅-inverse consistency [Zytnicki et al., 2006], which is still relatively weak in terms of lower bound estimation and pruning. The question becomes whether we can achieve stronger consistencies, the generalized versions of AC* [Larrosa and Schiex, 2004] and FDAC* [Larrosa and Schiex, 2003], for non-binary constraints efficiently. Consistency algorithms for AC* and FDAC* involve three main operations: (a) computing the minimum cost of the constraint when a variable x is fixed with value v, (b) projecting the minimum cost of a constraint to the unary constraint for x at value v, and (c) extending the unary cost to the non-unary constraints. These operations allow cost movement among constraints and shifting of cost to the C∅ constraint, resulting in higher lower bound and also domain prunings. Part (a) is readily handled by the minimum cost flow (MCF) algorithm. We show how the MCF algorithm and the corresponding flow networks can be adapted for parts (b) and (c) so as to perform projection and extension in polynomial time and space complexity. Using the soft allDifferent constraint as a testbed, we demonstrate the advantages of the stronger consistencies over naive incorporation.

2 WCSP

The weighted CSP (WCSP) framework extends classical constraint satisfaction by associating costs to the tuples of variable assignments. A WCSP [Schiex et al., 1995] is a tuple (X,D,C, k). X is a set of variables {x1, x2, . . . , xn} ordered by their indices. D is a set of domains D(xi) for xi ∈ X. Each xi can only be assigned one value in its corresponding domain. An assignment on a set of variables can be represented by a tuple ℓ. We denote ℓ[xi] as the value assigned to xi, and ℓ[S] as the tuple formed from the assignment on a subset of variables S. C is a set of constraints, each CS of which represents a function mapping tuples corresponding to assignments on S to a cost valuation structure V (k) = ([0 . . . k],⊕,≤). The structure V (k) contains a set of integers [0 . . . k] with standard integer ordering ≤. Addition ⊕ is defined by a ⊕ b = min(k, a + b), and subtraction ⊖ is defined by a ⊖ b = a - b if a ̸= k and k ⊖ a = k for any a.

Without loss of generality, CS can always be defined (initially with all tuples mapping to zero) for all S ⊆ X. The cost of a tuple ℓ corresponding to an assignment on X is defined as:

where C∅ is a null constraint that denotes the lower bound of costs of all possible tuples. A tuple ℓ corresponding to an assignment on X is feasible if cost(ℓ) < k, and is a solution of a WCSP if ℓ has the minimum cost among all feasible tuples.

A soft global constraint CS on variables S has a particular semantics and can have more than one cost measure. Where necessary, we sometimes give also a separate cost function μ in case CS has more than one such function. For simplicity, we assume that when we write CS(ℓ) or μ(ℓ), ℓ is always a feasible assignment to S.

WCSPs are solved with basic branch-and-bound search augmented with consistency techniques which prune infeasible values from variable domains and push lower bound estimates into C∅. Common consistency notions and techniques [Larrosa and Schiex, 2003; 2004; Sanchez et al., 2008] include NC*, AC*, and FDAC*, but are designed for unary to ternary constraints only.

A variable xi is NC* if (1) each value v ∈ D(xi) satisfies Cxi (v)⊕C∅ < k and (2) there exists a value v′ ∈ D(xi) such that Cxi (v′ ) = 0. A WCSP is NC* iff all variables are NC*. Algorithm 1 enforces NC*. Function unaryProject() projects costs from unary constraints to C∅ by simple arithmetic operations, and pruneVal() removes infeasible values from domains.

3 Enforcing ∅IC and Strong ∅IC

In this section, we explain how van Hoeve's method of using minimum cost flow can be adapted for WCSPs to enforce a strong form of ∅-inverse consistency [Zytnicki et al., 2006]. Given a connected flow network G(V, E, w, c, s, t), where V are the vertices, E are the edges, and each edge e ∈ E has a weight we and a capacity ce. A flow f from a source s to a sink t of a value α in G is defined as a mapping from E to R such that :

• ∑(s,u)∈E fsu = ∑(u,t)∈E fut = α;
• ∑(u,v)∈E fuv = ∑(v,u)∈E fvu ∀ v ∈ V \ {s, t};
• 0 ≤ fe ≤ ce ∀ e ∈ E.

If α is not defined, α is the maximum value of all flows in G. The cost of a flow f is defined as ∑e∈E wefe. A soft global constraint CS with cost function μ is flow-based if μ allows for a representation in a flow network G so that the flow with

Procedure enforceNC*()

• foreach xi ∈ X do unaryProject(xi); 1
• foreach xi ∈ X do pruneVal(xi); 2

Procedure unaryProject(xi)

Function pruneVal(xi):Boolean

minimum cost in G corresponds to the tuple mapping to the minimum cost in CS. Van Hoeve et al. [2006] demonstrate his framework on the soft versions of the allDifferent, gcc, regular, and same constraints.

We use the soft allDifferent constraint with the μdec cost measure [Petit et al., 2001] to illustrate the concepts. Given an assignment tuple ℓ on variables S, μdec(ℓ) = |{(i, j)|i < j ∧ ℓ[xi] = ℓ[xj] ∧ xi, xj ∈ S}|, which stands for the number of pairs of variables sharing the same value. We can construct a flow network G(V, E, w, c, s, t) as follows [van Hoeve et al., 2006]. The network consists of |S|+|D|+2 nodes, where |D| is the size of the union of all variable domains in S. Each variable and value have an associated node, with two more nodes s and t. The network contains three sets of edges:

• (s, xi) ∈ E for each xi ∈ X with zero weight and unit capacity;
• (xi, v) ∈ E for each v ∈ D(xi) with zero weight and unit capacity;
• (v, t)i ∈ E, for each i = 1, . . . , dv, where dv is the number of variables containing v. Each edge (v, t)i has a unit capacity and a weight of i - 1.

For example, if X = {x1, x2, x3, x4} with D(x1) = {a, c}, D(x2) = {b, d},D(x3) = D(x4) = {a, d} and allDifferent(X), the network is constructed as shown in Figure 1. Only non-zero weights are shown in the network. All edges assume unit capacity. The minimum cost of the feasible flow in G with value |X| is min{μdec(ℓ)}. To compute min{μdec(ℓ)|ℓ[x] = v}, the minimum cost flow simply enforces fxv = 1. For example, Figure 1 shows a flow (highlighted by thickened edges) of minimum cost when fx1a = 1. Regin [2002] and Van Hoeve et al. [2006] proved that such an enforcement can be derived from an existing flow by constructing a residual network from G and the existing flow, and finding the minimum cost cycle containing (x, v) in the residual network. This can be found by using the single source shortest path algorithm.

We now define ∅IC [Zytnicki et al., 2006] and strong ∅IC for WCSPs, the enforcement of which can benefit from van Hoeve's method. A constraint CS is ∅IC if there exists a tuple ℓ corresponding to a feasible assignment with CS(ℓ) = 0. A WCSP is ∅IC iff all constraints are ∅IC.

For example, Figure 2(a) shows a WCSP which is not ∅IC. No matter which values are assigned to the variables, Cx1,x2

returns a cost of at least 1. To enforce ∅IC, a cost of 1 is projected directly fromCx1,x2 to C∅ by reducing the cost of each tuple by 1 and increase C∅ by 1. The resultant WCSP is shown in Figure 2(b).

Procedure enforce∅IC() in Algorithm 2 enforces ∅IC for aWCSP by enforcing∅ICon each constraints. Reducing the cost of each tuple can be expensive. An implementation trick is to use a zero-initialized variable zS to store the cost reduced so far due to projection from CS to C∅. If a tuple ℓ queries its cost fromCS, the result is CS(ℓ) ⊖ zS.

In general, the algorithm is exponential even with the implementation trick since exponential number of tuples have to be examined at line 5. However, minimum cost flow computation allows for a polynomial time algorithm for flow-based soft global constraints, such as allDifferent with μdec.

Enforcing ∅IC only increases C∅. We observe, for example in Figure 2(b), that the value d ∈ D(x1) cannot be part of any solution. The tuple associated with x1 = d has a cost at least 4: 1 from C∅, 2 from Cx1 , and 1 from Cx1,x2 . Extra conditions can be added to strengthen ∅IC to allow also

Function enforce∅IC():Boolean flag := true; 1 foreach CS ∈ C do 2 flag := flag ∨ enforce∅IC(CS); 3 return flag; 4 Function enforce∅IC(CS):Boolean α := min{CS(ℓ)}; 5 foreach tuple ℓ do CS(ℓ) := CS(ℓ) ⊖ α; 6 C∅ := C∅ ⊕ α; 7 return α > 0 8

domain reduction. A non-unary constraint CS is strong ∅IC if:

• CS is ∅IC, and;
• for all values v ∈ D(x) with x ∈ S, C∅ ⊕ Cx(v) ⊕ min{CS(t)|t[x] = v} < k.

A WCSP is strong ∅IC iff all constraints are strong ∅IC.

For example, the WCSP in Figure 2(b) is not strong ∅IC, but removing the value d from D(x1) makes it so. Procedure enforceStrong∅IC() in Algorithm 3 enforces strong ∅IC , based on the W-AC*3() Algorithm [Larrosa and Schiex, 2004]. The algorithm maintains a propagation queue Q (implemented as a set) of variables. Constraints involving variables in Q are potentially not strong ∅IC. Function pop() removes an arbitrary available variable from Q in constant time.

Procedure enforceStrong∅IC()

Function removeInfeasible(CS, xi):Boolean flag := false; 10 foreach v ∈ D(xi) do 11 α := min{CS(ℓ)|ℓ[xi] = v}; 12 if C∅ ⊕ Cxi (v) ⊕ α = k then 13 D(xi) := D(xi) \ {v}; 14 flag := true; 15 return flag; 16

Procedure enforceStrong∅IC() in Algorithm 3 must terminate, the proof of which is similar to those of Larrosa and Schiex's Theorems 12 and 21 [2004]. Suppose removeInfeasible() and enforce∅IC() have a time complexity of O(fstrong) and O(f∅) respectively, the complexity can be stated as follows.

Theorem 1 Procedure enforceStrong∅IC() has a time complexity of O(smaxd(smaxefstrong + f∅)), where e is the number of non-unary constraints, smax is the maximum arity of the constraints, n is the number of variables, and d is the maximum domain size. Thus, enforceStrong∅IC() must terminate.

Proof: In each iteration of the while loop, line 6 will be executed O(smaxe) times. Each variable is pushed into Q at most O(d) times due to line 7 (each time D(xu) is modified); thus the while loop will be executed O(smaxd) times. Therefore, the complexity of procedure enforceStrong∅IC() is O(smaxd(smaxefstrong + f∅)), and it must terminate.

Again, enforceStrong∅IC() requires exponential complexity since line 12 is exponential in general. However, line 12 can be computed in polynomial time for flow-based soft global constraints. The following result is a consequence of Regin's Lemma 1 [2002] and van Hoeve et al.'s Theorem 1 [2006].

Theorem 2 If CS is a flow-based soft global constraint, removeInfeasible() has a time complexity of O(K + d · SP), where O(K) and O(SP) are the time complexity to find the minimum cost flow and single source shortest path respectively, and d is the maximum domain size.

Given a network G(V,E,w, c, s, t). A typical O(K) is O(|V |2 |E|) if the successive shortest path algorithm is used, and a typical O(SP) is O(|V ||E|) if a label correcting algorithm, like the Bellman-Ford algorithm, is used [Ahuja et al., 2005].

Due to space limitation, we cannot give the details of the reasoning that the "Soft as Hard" approach [Petit et al., 2001] is slightly weaker than enforcing strong ∅IC together with NC*, which is still relatively weak in terms of the deduced lower bound and pruning. Stronger consistencies for soft global constraints are desirable.

4 Projection in GAC*

We specialize the definition of GAC in Cooper et al. [2004] for WCSP. A variable xi ∈ S is generalized arc consistent star (GAC*) with respect to a non-unary constraint CS if:

• xi is NC*, and;
• for each value vi ∈ D(xi), there exists values vj ∈ D(xj) for all j ̸= i and xj ∈ S so that they form a tuple ℓ with CS(ℓ) = 0. {vj} is a simple support of vi with respect to CS.

A WCSP is GAC* iff all variables are GAC* with respect to all constraints. Notice that GAC* collapses to AC* for binary constraints [Larrosa and Schiex, 2004] and AC for ternary constraints [Sanchez et al., 2008].

Procedure enforceGAC*() in Algorithm 4 enforces GAC* for a WCSP and is based on the W-AC*3() Algorithm [Larrosa and Schiex, 2004]. Algorithm 4 must termi- Procedure enforceGAC*()

Q := X; 1 while Q ̸= ∅ do 2 xu := pop(Q); 3 flag := false; 4 foreach CS s.t. {xu} ⊂ S do 5 foreach xi ∈ S \ {xu} do 6 flag := flag ∨ findSupport(CS, xi); 7 if pruneVal(xi) then Q := Q ∪ {xi}; 8 if flag then 9 foreach xi ∈ X do 10 if pruneVal(xi) then Q := Q ∪ {xi}; 11

Function findSupport(CS, xi):Boolean

flag := false; 12 foreach v ∈ D(xi) do 13 α := min{CS(ℓ)|ℓ[xi] = v}; 14 if Cxi (v) = 0 ∧ α > 0 then flag := true; 15 Cxi (v) := Cxi (v) ⊕α; 16 foreach tuple ℓ with ℓ[xi] = v do 17 CS(ℓ) := CS(ℓ) ⊖α; 18 unaryProject(xi); 19 return flag; 20

nate, the proof of which is similar to that of Theorem 1. By replacing O(fstrong) and O(f∅) by O(fGAC) (the complexity of findSupport()) and O(nd) (n times the complexity of pruneVal()) respectively, the complexity of Algorithm 4 can be stated as follows.

Theorem 3 Procedure enforceGAC*() has a time complexity of O(smaxd(esmaxfGAC + nd)), where n, d, e, and smax are as defined in Theorem 1. Thus, enforceGAC*() must terminate.

Again, Algorithm4 requires exponential time complexity since function findSupport() is exponential. The time complexity of findSupport() is determined by two operations: minimum cost computation (line 14) and cost projection (lines 16 to 18). Line 14 computes the minimum cost of CS when xi = v. Line 16 projects the cost to the unary constraint Cxi , which is a simple arithmetic operation. Lines 17 and 18 update the cost of all tuples corresponding to xi = v. In general, this two sub-procedures require exponential time complexity, which can be reduced for flow-based soft global constraints. Van Hoeve's method can be applied similarly to line 14 as in Section 3. Lines 17 to 18 modify the cost function of the soft (global) constraint CS. Before we give our method, we state the conditions under which our method is applicable.

A soft global constraint CS with cost function μ is projection-safe if

• the soft global constraint CS with cost function μ is flow-based, and has the corresponding flow network

G(V, E, w, c, s, t),

• there is a one-one correspondence between every flow f of G and a complete variable assignment tuple ℓ for CS, and
• there exists an injection from an assignment xi = v to ¯ e ∈ E such that whenever ℓ[xi] = v for some tuple ℓ, f¯ e = 1 in the flow f corresponding to ℓ; whenever ℓ[xi] ̸= v, f¯ e = 0.

Given a projection-safe soft global constraint CS with cost function μ defined above. Suppose a cost of α is projected from CS to Cxi associated with xi = v, resulting in a new cost function μ′ . In other words, μ′ (ℓ) = μ(ℓ) ⊖ α if ℓ[xi] = v; otherwise μ′ (ℓ) = μ(ℓ). We construct the corresponding flow network of CS with cost function μ′ as G′ (V, E, w′ , c, s, t), where w′e = we ⊖ α if e is the edge corresponding to xi = v; otherwise w′e = we.

We use again the allDifferent constraint with μdec as an example. Figure 1 shows the corresponding flow network and the flow representing (x1, x2, x3, x4) = (a, b, a, d) with cost 1. If a cost of 1 is projected from the constraint to Cx1 associated with x1 = a, a new network can be constructed by decreasing the weight wx1a of the edge (x1, a) from 0 to

-1, as shown in Figure 3. The new cost of the flow in the network is now 0, which corresponds to the cost of the tuple (a, b, a, d) after projection.

The soundness and closure of our method are guaranteed by the following theorem.

Theorem 4 Suppose CS is a soft global constraint with cost function μ is projection safe, a cost of α associated with xi = v is projected from CS to Cxi , resulting in a new cost function

• μ′ .· (Soundness) If f is a minimum cost flow of G′ (V, E, w′ , c, s, t), then ∑e∈E w′efe = min{μ′ (ℓ)}.
• (Closure) CS with cost function μ′ is projection safe.

Proof: Projection-safety implies that ∑e∈E w′e fe = ∑e∈E wefe⊖αf¯ e = min{μ(ℓ)}⊖αf¯ e = min{μ′ (ℓ)}, where ¯ e is the edge corresponding to xi = v. This concludes soundness.

In addition, CS with μ′ is flow-based with G′ (V,E,w′ , c, s, t) as the corresponding flow network. Since the topology of G′ (V,E,w′ , c, s, t) is the same as that of G(V,E,w, c, s, t), CS with μ′ is projection-safe.

We state without proof that the majority of the flow-based global constraints [van Hoeve et al., 2006] are projection-safe so that GAC* can be enforced on them in polynomial time.

Theorem 5 The following flow-based soft global constraints are projection-safe.

• allDifferent with either μvar or μdec;
• gcc with either μvar or μval;
• same with μvar;

Unfortunately, the regular constraint with either μvar or μedit [van Hoeve et al., 2006] and the soft SEQUENCE constraint [Maher et al., 2008] are not projection-safe since they do not satisfy the third requirement.

Again, the complexity of enforcing GAC* for a variable with respect to the projection-safe soft global constraints follows from van Hoeve et al.'s Theorem 1.

Theorem 6 If CS is projection safe, findSupport() has a time complexity of O(K + d · SP), where K and SP are as defined in Theorem 2.

Based on FDAC* [Larrosa and Schiex, 2003], even stronger consistency can be defined but its enforcement involves an extension operator, which is the reverse of projection and the focus of the next section.

5 Extension in FDGAC*

Suppose variables are ordered by their indices. A variable xi ∈ S is directional generalized arc consistent star (DGAC*) with respect to a non-unary constraint CS if:

• xi is NC*, and;
• for each value vi ∈ D(xi), there exists values vj ∈ D(xj) for all j ̸= i and xj ∈ S so that they form a tuple ℓ with CS(ℓ) ⊕ ⊕j>i∧xj∈S Cxj (vj) = 0. {vj} is a full support of vi with respect to CS.

A WCSP is full directional generalized arc consistent star (FDGAC*) if all variables are DGAC* and GAC* with respect to all non-unary constraints. When the constraints are binary, FDGAC* collapses to FDAC* [Larrosa and Schiex, 2004]. When the constraints are binary and ternary, however, FDGAC* differs slightly from FDAC [Sanchez et al., 2008]. FDGAC* requires full supports with only zero unary costs, while FDAC [Sanchez et al., 2008] requires full supports with not only zero unary but also zero binary costs.

Based on the FDAC*() Algorithm [Larrosa and Schiex, 2003], procedure enforceFDGAC*() in Algorithm 5 enforces FDGAC*. Q and R store variables which are potentially not GAC* and not DGAC* respectively. Function popMax() always removes the variable with the largest index from R in constant time. Procedure enforceFDGAC*() in Algorithm 5 must terminate, the proof of which is similar to those of Larrosa et al.'s Theorems 3 and 4 [2003]. Suppose findFullSupport() and findSupport() are of order O(fDGAC) and O(fGAC) respectively, the complexity of procedure enforceFDGAC*() can be stated as follows.

Procedure enforceFDGAC*() R := Q := X; 1 while R ̸= ∅ ∨ Q ̸= ∅ do 2 while Q ̸= ∅ do 3 xu := pop(Q); 4 flag := false; 5 foreach CS s.t. {xu} ⊂ S do 6 foreach xi ∈ S \ {xu} do 7 if findSupport(CS, xi) then 8 R := R ∪ {xi}; 9 flag := true; 10 if flag then 11 foreach xi ∈ X s.t. pruneVal(xi) do 12 Q := Q ∪ {xi}; 13 while R ̸= ∅ do 14 xu := popMax(R); 15 if pruneVal(xu) then Q := Q ∪ {xu}; 16 foreach CS s.t. {xu} ⊂ S do 17 for i = u - 1 DownTo 1 s.t. xi ∈ S do 18 if findFullSupport(CS, xi) then 19 R := R ∪ {xi}; 20 foreach xi ∈ X s.t. pruneVal(xi) do 21 Q := Q ∪ {xi}; 22 Function findFullSupport(CS , xi):Boolean foreach j > i and xj ∈ S do 23 foreach v ∈ D(xj) do 24 foreach tuple ℓ with ℓ[xj ] = v do 25 CS(ℓ) := CS(ℓ) ⊕Cxj (vj); 26 Cxj (vj) := 0; 27 flag := findSupport(CS , xi); 28 foreach j > i and xj ∈ S do findSupport(CS , xj); 29 unaryProject(xi ); 30 return flag; 31

Theorem 7 enforceFDGAC*() has a time complexity of O(s2maxed(nfDGAC + fGAC) + n2d2 ), where n, d, e, and smax are defined in Theorem 1. Thus, enforceFDGAC*() must terminate.

Again, the complexity can be exponential due to findSupport() and findFullSupport(). In the following, we focus the discussion on findFullSupport(). The first part (lines 23 to 27) performs extension, a reversal of projection, to push all the unary costs back to CS. By the time we execute line 28, all unary costs are 0, and enforcing GAC* for xi achieves the second requirement of DGAC*. Line 29 re-instates GAC* for all variables xj , where j > i. Note that the success in line 28 guarantees that Cxj (vj) = 0 if vj appears in a tuple ℓ which makes CS(ℓ) = 0.

The key idea to performing extension properly is similar to that of projection: the method is applicable to a projectionsafe soft global constraint CS with cost function μ. Suppose now we want to extend a cost of α associated with xi = v fromCxi to CS resulting in a new cost function μ′′ . In other words, μ′′ (ℓ) = μ(ℓ) ⊕ α if ℓ[xi] = v; otherwise μ′′ (ℓ) = μ(ℓ). We construct the corresponding flow network of CS with cost function μ′′ as G′′ (V,E,w′′ , c, s, t), where w′′ e = we ⊕ α if e is the edge corresponding to xi = v; otherwise w′′ e = we.

Similarly, extension is both sound and closed.

Theorem 8 Suppose CS is a projection safe soft global constraint with cost function μ, and a cost of α associated with xi = v is extended from Cxi to CS, resulting in a new cost function μ′′ .

• (Soundness) If f is a minimum cost flow of G′′ (V, E, w′′ , c, s, t), then ∑e∈E w′′ e fe = min{μ′′ (ℓ)}.
• (Closure) CS with cost function μ′′ is projection safe.

The complexity result again follows from van Hoeve et al.'s Theorem 1 [2006].

Theorem 9 If CS is a projection-safe soft global constraint, findFullSupport() has a time complexity of O(K + smaxd · SP ), where K and SP are as defined in Theorem 2.

Last but not least, we state the relative strength of the consistencies concerned. Given two consistencies β and γ, β is stronger than γ (β ≥ γ) if a WCSP P is γ whenever P is β.

Theorem 10 FDGAC* ≥ GAC* ≥ strong ∅IC ≥ GAC in "Soft as Hard" Approaches.

6 Experimental Results

To demonstrate the efficiency of our proposals, we have implemented strong ∅IC, GAC*, and FDGAC* for the soft allDifferent constraint with the μdec and μvar cost functions in ToulBar2 1 . Our benchmark instances are based on a softened version of the all-interval series problem (CSPLib Prob007). This problem contains mainly allDifferent constraints, unconcerning us from other possible external factors and focusing on evaluating the efficiency of our proposed algorithms. Such a benchmark also allows us to study the scaling behavior of our algorithms. The original problem of order n is to find a series {x1, . . . , xn} such that it is a permutation of {0, . . . , n - 1} and the adjacent differences di = |xi - xi+1|, i = {1, . . . , n - 1} are distinct. To model its softened version as a WCSP, we use {xi} and {di} as variables with domains {0, . . . , n - 1}. Two allDifferent constraints are placed on {xi} and {di} respectively. Ternary table constraints are used to enforce di = |xi - xi+1|. Besides, random unary constraints are placed on {xi}, assigning random costs to each assignment ranging from 0 to 9.

During the experiment, variables {xi} are first assigned in lexicographic order, followed by {di} in the same order. Value assignments start with the value with minimum unary cost first. The test is conducted in a Dell Optiplex 280 with an Intel P4 3.2GHz CPU and 2GB RAM. The average runtime and number of backtracks of five instances are measured for each value of n with no initial upper bound. Entries are marked with a "*" if the average runtime exceeds the limit of 1 hour.

1 http://carlit.toulouse.inra.fr/cgi-bin/awki.cgi/ToolBarIntro

(b) μvar

Figure 4: The time in seconds and the number of backtracks in solving softened all-interval series instances by enforcing different consistencies on the soft allDifferent constraints with μdec (top) and μvar (bottom).

We give the results for allDifferent with μdec and μvar in Figure 4, which agrees well with the theoretical comparison of the three consistencies. This demonstrates that minimum cost flow computation is an efficient method for enforcing the consistencies of projection-safe soft global constraints. Despite a higher complexity, FDGAC*, the strongest consistency both in terms of pruning and lower bound reasoning, is the clear winner bettering strong ∅IC by one to two orders of magnitude, while GAC* comes in a clear second. In the best case, enforcing FDGAC* can remove 18 times more search nodes than enforcing GAC*, and 220 times more than enforcing strong ∅IC. Last but not least, we note that, without strong ∅IC, Toulbar2 delays the propagation of n-ary constraints until only two variables restricted by the constraints are not yet assigned. It is impractical to solve the benchmark even with a small value of n.

7 Conclusion

Global constraints are one of the keys for modeling and solving complex real-life problems. To the best of our knowledge, this is the first success report of global constraints in WCSP solvers with practical efficiency. Our techniques make it possible to enforce generalized versions of existing consistencies exploiting specifically characteristics of WCSPs.

Immediate future work includes studies of the implementation of more projection-safe soft global constraints, feasibility of other forms of consistencies, experiments on a wider variety of benchmarks. It is also interesting to investigate if there are other forms of projection-safety.