In the quest of the best form of local consistency for Weighted CSP

1 Introduction

It is well known that arc consistency (AC) plays a preemi­ nent role in efficient constraint solving. In the last few years, the CSP framework has been augmented with so-called soft constraints with which it is possible to express preferences among solutions [Schiex eta/., 1995; Bistarelli eta/., 1997]. Soft constraint frameworks associate costs to tuples and the goal is to find a complete assignment with minimum com­ bined cost. Costs from different constraints are combined with a domain dependent operator EB. Extending the notion of AC to soft constraint frameworks has been a challenge in the last few years. z,From previous works we can conclude that the extension is direct as long as the operator EB is idem­ potent. Then, [Schiex, 2000] proposed an extension of AC which can deal with non-idempotent EB. This definition has three nice properties: (i) it can be enforced in polynomial time, ( ii) the process of enforcing AC reveals infeasible val­ ues that can be pruned and (iii) it reduces to existing defini­ tions in the idempotent operator case. [Cooper, 2003] further introduced directional arc consistency (DAC) and full direc­ tional arc consistency for strictly monotonic EB.

Weighted constraint satisfaction problems (WCSP) is a well known soft-constraint framework with a non-idempotent operator EB. It provides a very general model with several ap­ plications in domains such as resource allocation [ Cabon et

Thomas Schiex

Dept. de Biometrie et Intelligence Artificielle Institut National de Recherche Agronomique Toulouse,France Thomas.Schiex@toulouse.inra.fr

a/., 1999], combinatorial auctions [Sandholm, 1999], bioin­ formatics and probabilistic reasoning [Pearl, 1988]. [Larrosa, 2002] introduced AC*, a refinement of the AC definition for WCSP. This definition provides a stronger yet simple and el­ egant property to be maintained during search.

In this paper, we take the definitions of DAC and FDAC, strengthen and extend them to binary WCSP, defining the DAC* and FDAC* properties. We then define correspond­ ing enforcing algorithms. As in the classical CSP case, we then consider the problem of maintaining AC*, DAC* and FDAC* during search and empirically compare these algo­ rithms. These algorithms have a wide range of applications and allow a nice integration of hard and soft constraints in a common algorithmic framework.

2 Preliminaries

2.1 CSP

A binary constraint satisfaction problem (CSP) is a triple P = (X, D,C). X = {1, . . . , n} is a set of variables. Each variable i E X has a finite domain Di E V of values that can be assigned to it. (i, a) denotes the assignment of value a E Di to variable i. A tuple t is an assignment to a set of variables. Actually, t is an ordered set of values assigned to the ordered set of variables Xt s;; X (namely, the k-th ele­ ment oft is the value assigned to the k-th element of Xt) . For a subset B of Xt, the projection oft over B is noted t lB· Cis a set of unary and binary constraints. A unary constraint Ci is a subset of Di containing the permitted assignments to vari­ able i. A binary constraint cij is a set of pairs from Di X Dj containing the permitted simultaneous assignments to i and j. The set of variables affected by a constraint is called its scope. A tuple t is consistent if it satisfies all constraints whose scope is included in Xt. A solution is a consistent complete assignment. Finding a solution in a CSP is an NP­ complete problem. The task of searching for a solution can be simplified by enforcing arc consistency, which may prune values that cannot participate to a solution.

2.2 Weighted CSPs

Valued CSP (as well as semi-ring CSP) extend the CSP framework by associating costs to tuples [Schiex eta/., 1995; Bistarelli et a/., 1997]. In general, costs are specified by means of a so-called valuation structure defined as a triple S = ( E , EB, C:: ), where E is the set of costs totally ordered by C::. The maximum and a minimum costs are noted T and _1_, respectively. EB is an operation on E used to combine costs.

A valuation structure is idempotent if '<ia E E, (a EBa) = a. It is strictly monotonic if Va, b, c E E , s. t.(a >- c) 1\ (b =1T) ,wehave (a EB b) >- (c EB b).

Following [Larrosa, 2002], we define Weighted CSP (WCSP) as a specific subclass of valued CSP that relies on a specific valuation structure S(k) .

Definition 1 S(k) is a triple ([0, 1, . . . , k], EB, ~) where,

• k E [1 , ... , oo].
• EB is defined as a EB b = min{k, a + b}
• ~ is the standard order among naturals.

Observe that in S(k) , we have 0 = _l_ and k = T.

A binary WCSP is a tuple P = (k , X , V , C) . The valua­ tion structure is S(k) . X and V are variables and domains, as in standard CSP. C is a set of cost functions. A binary constraint Cii assigns costs to assignments to variables i and j (namely, Cii : D; x Di --+ [0, ... , k]). A unary con­ straint Ci assigns costs to assignments to variable i (namely, Ci : Di --+ [0, . . . , k]) . We assume the existence of a unary constraint Ci for every variable, and a zero-arity constraint, noted C0 (if no such constraint is defined, we can always define dummy ones Ci(a) = _l_, Va E Di or C0 = _l) .

When a constraint C assigns cost T to a tuple t, it means that C forbids t, otherwise t is permitted by C with the cor­ responding cost. The cost of a tuple t , noted V(t) , is the sum over all applicable costs,

Tuple tis consistent ifV(t) < T. The usual task of inter­ est is to find a complete consistent assignment with minimum cost, which is NP-hard. Observe that WCSP with k = 1 reduces to classical CSP. In addition, S ( k) is idempotent iff k = 1 and strictly monotonic iff k = oo. Two WCSP defined over the same variables are said to be equivalent if they define the same cost distribution on complete assignments.

For simplicity in our exposition, we assume that every con­ straint has a different scope. For the moment, we also assume that constraints are implemented as tables and that it is pos­ sible to consult and modify entries. This is done without loss of generality (see the proof of Theorem 3).

Example 1 Figure l .a shows a WCSP with valuation struc­ ture S( 4) (the set of costs is [0, . .. , 4]. with _l_ = 0 and T = 4). It has three variables X = {x , y , z} with values a, b. There are 2 binary constraints Cxz, Cyz and two non trivial unary constraints Cx and Cz. Unary costs are depicted in­ side their domain value. Binary costs are depicted as labelled edges connecting the corresponding pair of values (default cost of 1). Zero costs are not shown. One optimal solution is eg. x = y = z = b, with cost 2.

Our definition of WCSP is the same as in [Larrosa, 2002]. It differs from usual definitions [Schiex et al., 1995; Bistarelli et al. , 1997] which restrict WCSP to the k = oo case, a strictly monotonic valuation structure where finite costs can­ not lead to deletion. In practice, most branch and bound­ based solvers maintain an upper bound ub, the maximum ac­ ceptable cost so-far, and a lower bound lb on the optimal ex­ tension of the current assignment. Value pruning occurs as soon as lb ~ ub. The WCSP framework makes these two ele­ ments explicit: a solver uses the valuation structure S( ub) at every subproblem and c0 provides the lower bound.

3 Some local consistencies in WCSP

[n this Section we define node, arc, directed arc and full di­ rected arc consistencies. For node and arc consistencies, our definitions are equivalent to the NC* and AC* definitions in [Larrosa, 2002] . For DAC, and FDAC, the starred(*) def­ initions refine the definitions in [Cooper, 2003] to the WCSP case, using node consistency and C0 . In the sequel, we as­ sume that the set of variables X is totally ordered by >.

Definition 2 Let P = (k , X , V , C) be a binary WCSP

• Node consistency: ( i, a) is star node consistent (NC*) if C0 EB Ci (a) < T. Variable i is NC* if: i ) all its values are NC* and ii) there exists a value a E Di such that Ci (a) = _l_. Value a is a support for the variable i . P is NC* if every variable is NC*.
• Arc consistency. (i, a) is arc consistent (AC) with re­ spect to constraint Cii if there is a value b E D1 such that Cij (a, b) = _1_. Value b is called a support of the value (i , a). Variable i is AC if all its values are AC wrt. every binary constraint affecting i. P is AC* if every variable is AC and NC*.
• Directional arc consistency. (i , a) is directional arc con­ sistent (DAC) wrt. constraint Cii, j > i, if there is a value bE D1 such that C; 1 (a, b) EB C 1 (b) = _l_. Value b is called a full support of a. Variable i is DAC if all its values are DA C with respect to every Cij, j > i. P is DAC* if every variable is DAC and NC*.
• Full directional arc consistency. P is fully star direc­ tional arc consistent (FDAC*) if it is DAC* and AC*.

In the CSP case (i.e, k = 1), being a support for (i, a) is obviously equivalent to being a full support for it and both notions reduce to the classical notion of support. Therefore, AC* and DAC* reduce to their classical definitions in CSP while FDAC* reduces to arc consistency. In WCSP, however, a support is not necessarily a full support. For this reason, DAC* (which requires a full support on one side of each con­ straint) and AC* (which requires a support on both sides) are incomparable. FDAC* (which requires a support on one side and a full support on the other) cannot be weaker than AC* or DAC* 1 · In WCSP, FDAC* can actually be stronger, in the sense that it may provide a better lower bound as the follow­ ing example shows.

Example 2 The problem in Figure I.a is not NC* since z has no support. Problem I.b is an equivalent NC* problem. It is not DAC* for order xyz since (y , a) has no full support on z. It is not AC* either since eg. (z , a) and (y , a) have no support on x and z respectively. Problem I .e is an equivalent DAC* problem. It is not AC* since (z , a) has no support on x. Problem I.d is an equivalent AC* problem. It is not DAC* since (y, b) has no full support on z. Problem I .e is an equivalent FDAC* problem. The 2 optimal solutions are made obvious here.

There is a strong relation between directional arc consis­ tency and mini-buckets [Dechter, 1997]. It can easily be shown that given a WCSP defined over the valuation struc­ tureS( oo) and a variable ordering, the lower bound induced by mini-buckets involving at most 2 variables is the same as the lower bound induced by 0 0 after the problem is made directional arc consistent. However, the mini-bucket com­ putation provides only a lower bound while DAC enforcing provides both a lower bound and a directional arc consistent equivalent problem. All the work done to compute the lower bound is captured in this problem which offers the opportu­ nity to perform incremental updates of the lower bound.

4 Enforcing Arc Consistencies

The previous node and arc consistency properties can be en­ forced by applying basic operations until the correspond­ ing property is satisfied: pruning node-inconsistent values, forcing supports to variables (NC*), forcing (full) support to node-consistent values (AC). As pointed out in [Schiex, 2000; Larrosa, 2002], value (resp. variable) supports can be forced by sending costs from binary (resp. unary) constraints to unary constraints (resp. 0 0 ). Full support can be forced by first sending costs from a unary constraint oj to oij and then sending the cost from Oii to Oi [Cooper, 2003] . Let us review these concepts before introducing basic algorithms.

Let a, bE [0, ... , k], be two costs such that a ~ b. a e b is the subtraction of b from a, defined as,

The projection of a cost units from Oij E Cover value (i, a) is a flow of a cost units from the binary constraint to the unary cost Oi(a). It is embodied in the Procedure Project(i , a, j, a).

1 The stronger local property that would require a full support on both sides suffers from the fact that most WCSP don't have an equivalent WCSP that satisfies this property.

For the subtraction to be defined, the maximum flow that can be projected is minbEDj { oij(a, b)}. The converse extension of f3 cost units from value ( i, a) to Oij E Cis a reverse flow of f3 cost units from ( i , a) to the binary constraint. It is embodied in the Procedure Extend(i, a, j, (3). The maximum flow that can be extended is Oi(a). Unless stated otherwise, we always assume that maximum flows are projected or extended in the rest of the paper. Similar operations can be defined between unary constraints and 0 0 .

Procedure Project(i, a, j, a)

Theorem 1 {Schiex, 2000} Let P = (k , X , 'D,C) be a binary WCSP. Leta~ minbED 1 {0ij (a,b)}, f3 ~ Oi(a). The pro­ jection of a cost unit of Oij E C over ( i, a) or the converse extension of f3 cost unit from ( i , a) to o ij transform p into an equivalent problem P'.

Example 3 Consider the problem in Figure I .a. To enforce NC* we must force a support for z by projecting Oz onto 0 0 . The resulting problem I.b is NC* but not AC*. To en­ force AC*, it suffices to force a support for (y , a) and ( z, a): we project Oyz over (y, a) by adding 1 to Oy(a) and sub­ tracting 1 from Oyz (a, a) and Oyz (a , b) and similarly project Oxz over (z, a). We get problem I.d which is AC* but not FDAC* using the order xyz since (y, b) has no full support on z. To force a full support for (y , b), we extend 1 cost unit from Oz(a) to Oyz by adding 1 to Oyz(a , a) and Oyz (b, a) and subtracting 1 from Oz(a). We then project Oyz to (y, b) which increases Oy(b) to 1. y is now node-inconsistent, we project yon 00 and get 00 = 2. X is now node-inconsistent, we prune (x, a) and get problem I .e which is FDAC* accord­ ing to order xyz.

For simplicity, the following descriptions assume that no empty domain is produced and that the initial problem is NC*. It also assumes that the problems have no constraints of arity larger than two. [Larrosa, 2002] defined W-AC*2001, an algorithm based on AC2001 [Bessiere and Regin, 2001] to enforce AC*. It is embodied in the AC*() function of Algo­ rithm 1. It requires two data structures S( i , a, j) and S( i) which respectively store the current value support for ( i , a) with respect to constraint Oij and the current variable support for i . The algorithm uses three auxiliary functions : Function ProjectUnary(i) projects Oi onto 0 0 , Function PruneVar(i ) prunes node inconsistent values in Di and returns true if the domain is changed. Function FindSupportAC*(i , j) forces a support on Oii for each value in Di by projecting Oii on Oi. The main procedure AC*() uses a queue Q containing those variables whose domain has been pruned: adjacent vari­ ables may have unsupported values in their domains and new supports must be sought. Q should be initialized with all variables because every variable must find an initial support on every constraint. Ignore for the moment the boolean re­ turned by FindSupportAC* and the use of R. [Larrosa, 2002]

showed that AC*() is time O(n 2 d 3 ) and space O(ed) on gen­ eral WCSP.

[Cooper, 2003] introduced non incremental algorithms for enforcing DAC and FDAC on strictly monotonic valuation structures. These algorithms are inadequate for maintaining DAC* or FDAC* in a WCSP branch and bound algorithm that relies on a non strictly monotonic valuation structure S(k), k ::/= +oo as soon as a feasible solution is found.

The new basic operation needed to enforce {F} DAC* con­ sists in forcing full supports for the values of a variable i on one side of a constraint Cii. As shown in the example, this can be ~on~ by extending ~nary costs from cj to cij and then proJectmg Cii onto vanable Ci. However, extending all unary costs may destroy supports for j on Cii. Consider the AC* Problem l.d. If we extend 2 cost units from (z, a) to Cyz instead of 1 as in the example and then project on Cy, we get Problem l.f where (z, a) has lost all supports on y. In order to smoothly integrate DAC* and AC* enforcing to obtain FDAC* enforcing, we must obtain full supports for variable i on Cii while preserving supports for all values of j on Cii. This is obtained by extending the minimum cost of Ci required for the subsequent projection onto Ci. The cor­ rectness of our algorithms is based on the following theorem,

Theorem 2 Let j, a variable whose values are AC wrt. Cii· Va E Di,b E Di, let P[a] = minbEDj {Cii(a,b) EB Ci(b)} and E[b] = maxaED,{P[aJ- Cii(a,b)}. Extending E[b] cost units from (j, b) to Cij for all b E Di and project­ ing P[a] cost units from Cii to (i, a) for all a E Di yields an equivalent WCSP s.t. every node consistent value of i is DAC wrt. Cii and s.t. every value (j, b) is supported by argmaxaED; { P[a] - cij (a, b)} if it is node consistent.

Proof: We denote Cfi(a, b) the original value of Cii(a, b). We first show that E[b] and P[a] are possible flows. We first prove that 0 :S E[b] :S CJ(b): we have P[a] - Cii(a, b) = minb'EDj(Cii(a,b') EB Ci(b'))- Cii(a,b) :S (Cii(a,b) EB Ci(b)) - Cii(a, b) :S (Cii(a, b) + Ci(b)) - Cii(a, b) = Ci(b) and therefore E[b] :S Ci(b). Since j is AC, it has a support (i, a) s.t. C~(a, b) = j_ ::; P[a]. Therefore P[a]- Cii(a, b) ~ 0 and E[b] ~ _l.

After the extension of E[b] cost units, Cii (a, b) will be equal to Cfi(a,b) EB maxa'ED,{P[a'J- Cfi(a',b)} ~ Cfi(a, b) EB (P[a] - C~(a, b)). Either this is equal to T and obviously Cii(a, b) ~ P[a] or else Cfi(a, b) EB (P[a] - Cfi(a, b)) = P[a] and again Cii(a, b) ~ P[a].

Since P[a] = minbEDi { Cfi (a, b) EB Ci (b)} the value b for which this minimum is reached will either be a full support for (i, a) if P[a] ::/=Tor (i, a) will be deleted.

On the other side, consider value (j, b) and a argmax(P[a] - C~(a, b)). After extension and projection, either Cii(a, b) = Cfi(a, b) EB (P[a] - C~(a, b)) e P[a] :S P[a] e P[a] and either P[a] < T and a is a support of (j, b) or P[a] = T and a is node inconsistent. 0

Based on this theorem, Function FindFuiiSupportAC*(i, j) forces full supports for all the values of i on cij while taking care of supports for values in Di. It returns true whenever the cost of a value ( i, a) has been increased from _l. The Procedure DAC*() has been designed to be used alone to en­ force DAC* or in conjunction with AC*() to enforce FDAC*. Therefore, whenever a value is pruned, DAC*() inserts its vari­ able in Q to inform AC*() of the deletion. DAC* further uses a priority queue R that contains those variables such that a unary cost has been increased from j_: in this case, some values in lower variables may have lost full support and new supports need to be found. The main loop iterates while R is not empty. At each iteration, the highest variable j is fetched from R. Node inconsistent values (due to unary cost and lower bound increments) are removed using PruneVar() and pruned variables are inserted in Q. Then new full supports are sought for every lower variable connected to j. Finally, all variables are processed to enforce NC* which can be lost during the process, due to lower bound increments. Pruned variables are inserted in Q. FDAC*() simply enforces AC* and DAC* simultaneously: the enforcement ofAC* empties Q but may add variables to R, and the enforcement of DAC* empties R but may add variables to Q. FDAC* is achieved when both R and Q are simultaneously empty. Correction of both algorithms follows from theorem 2.

Theorem 3 The complexity of DAC*() is time O(ed 2 ) and space O(ed). n, e and dare the number of variables, con­ straints and largest domain size respectively.

Proof: FindFuiiSupportAC*(i, j) and PruneVar(i ) have com­ plexities O(d 2 ) and O(d) respectively. The only way a vari­ able j may enter the queue R is because some null unary cost Cj(b) has been increased in FindFuiiSupportAC*. R being a priority queue, when a variable j is extracted from R, all the variables before j in R have already been processed. Since FindFuiiSupportAC*() can only increase non zero unary costs of variables strictly lower than j, j will never be reintroduced in R and therefore each variable j is added to the queue R at most once. The queue is implemented as an array ofbooleans and a pointer to the highest true element. Adding new el­ ements to R means updating the pointer, the pop operation consists on returning the value of the pointer and searching for the new highest true element. Clearly, DAC*() only tra­ verses the array once. Thus, the complexity of the while loop is in O(ed 2 ) . Since the complexity of the secondforeach loop is in O(nd), the global complexity is in O(ed 2 ).

As it is, DAC*() is space O(ed 2 ) since it modifies binary constraints. As [Larrosa, 2002], we note that when a binary constraint Cij is modified (line 1 and 2 in Project and Ex­ tend), it is by addition or subtraction of costs that depend either on i or j. It is therefore possible to record only row and column changes, the current value of Cij (a, b) being ob­ tained as C~(a,b) 8 F(i , j,a) 8 F(j,i,b) where C? 1 (a,b) denotes the original constraint. There is one F(i,j ,a) entry per constraint-value pair which is space O(ed). D

Theorem 4 The complexity ofFDAC*() is time O(end 3 ) and space 0( ed).

Proof: Regarding space, there is no difference with DAC*() and the same proof applies. Regarding time, a variable j enters Q only if a value has been deleted. Therefore, each variable j is added to Q at most d + 1 times (once at initial­ ization and then upon value deletion at lines 5, 6 or 4). Therefore, line 3 of Procedure AC*() is executed at most 2e( d + 1) times and line 4 at most nd times. Globally, line 7 of Al­ gorithm 2 will therefore use O(n 2 d 2 + ed 3 ) elementary op­ erations. For the same reason, line 8 is executed at most O(nd) times. Since DAC* is in O(ed 2 ), this can generate O(end 3 ) elementary operations. Globally, the algorithm is time O(n 2 d 2 + ed 3 + end 3 ) = O(end 3 ). D

A consequence of these complexity results is that all algo­ rithms terminate (even in the S(oo) structure).

5 Experimental results

In this Section we perform an empirical evaluation of the ef­ fect of maintaining various forms of arc consistency during search. We consider a depth-first search maintaining either NC*, AC*, DAC* or FDAC* which yields the algorithms MNC*, MAC*, MDAC* and MFDAC*. For comparison, we include results obtained with PFC-RDAC [Larrosa eta!., 1999], which is normally considered as a reference algorithm.

For variable selection we use the domj deg heuristic which for each variable computes the ratio of the domain-size di­ vided by the future degree (i.e., degree considering future variables only) and selects the variable with the smallest value. For value selection we consider values in increasing order of unary cost Ci . The variable ordering used for direc­ tional arc consistencies is lexicographic.

We consider the Max-CSP problem, where the goal is to find a complete assignment with a maximum number of satisfied constraints in an overconstrained CSP. It can easily be formulated as a WCSP. We experiment with bi­ nary random problems using the well-known four-parameters model [Smith, 1994]. A random CSP class is defined by (n, d, e, t) where n is the number of variables, d is the do­ main size, e is the number of binary constraints (i.e, graph connectivity), and t the number of forbidden tuples in each constraint (i.e, tightness). Pairs of constrained variables and their forbidden tuples are randomly selected using a uniform distribution. Samples have 50 instances and we report aver­ age values. The experiments were performed on a 800 MHz Pentium III computer.

For fixed values of n, d and e and increasing tightness t, most problems are solved almost instantly until the cross-over point is reached. Then, problems become overconstrained and much harder to solve. We denote t 0 the lowest tightness where every instance in our sample is overconstrained. Based on this, we define different categories of problems:

• For graph density, we define two problem types: sparse (S) withe= 2.5n and, dense (D) withe= n(~-l).
• For tightness, we define two problem types: loose (L) with t = t 0 , and tight (T) with t = d 2 - 0.25t 0 ·

Combining the different types, we obtain 4 different classes, each being denoted by a pair of characters (SL,ST,DL and DT). In each class, the domain size is set to 10 and the num­ ber of variables n is used as a varying parameter. Figure 2 shows the average cpu time used with SL, ST, DL and DT from left to right. In each plot, the five algorithms are listed in increasing order of efficiency, from top to bottom. In all cases, the search effort seems to grow exponentially with n .

For all classes except the DL class, MFDAC* is the most efficient algorithm, with only minor differences with MDAC* (sometimes they are so closed that the two lines can hardly be distinguished). The best performance of MFDAC* is ob­ tained in the ST problems, where it is up to 5 times faster than PFC-RDAC, 20 times faster than MAC* and 50 times faster than MNC*. For the DL class, however, MNC* is the most efficient algorithm, followed by PFC-RDAC, MAC*, MF­ DAC* and MDAC*. The differences between the algorithms are however more limited than in previous classes (MNC* is twice faster than MFDAC*).

The ability of directional arc consistency to collect costs along the constraints in order to bring them together in the same variable allows to build stronger lower bounds. This is confirmed by the analysis of the number of nodes expanded by each algorithm (not reported here for lack of space) where MDAC* and MFDAC* always expand less nodes that PFC­ RDAC, MNC* or MAC*, with a ratio that can reach 300 be­ tween the extreme algorithms on eg. ST problems. On the DL problems however, this ratio is much more limited, typi­ cally bounded by 4. With loose constraints, the upper bound reaches low values early in the search which allows pruning at high levels of the search tree and makes sophisticated lower bounds less significant.

It is worth to mention at this point that PFC-RDAC heuris­ tically assigns a direction to every constraint in each sub­ problem and this has a strong influence on the efficiency on random Max-CSP. Similarly, the behavior of AC, DAC and FDAC based algorithms depends on the order in which vari­ ables are fetched from Q and R (i.e., on the variable order­ ing used to define DAC) and on the order in which values are considered for projection. In our current implementation, Q is implemented as a stack, values are considered in lexi­ cographic ordering and the DAC variable ordering is lexico­ graphic. This leaves room for further improvement.

6 Conclusion and Future Work

In this paper we have refined two local consistency properties and adapted them to WCSP. We have developed enforcing algorithms and have studied their complexity.

As in classical CSP, we observe that the choice of the right level of local consistency to maintain during search is impor­ tant. Despite its theoretical cost, the strongest local consis­ tency we considered (FDAC*) appears to be the best level for solving WCSP. In the future, we want to extend these algo­ rithms to non binary constraints, apply them to other prob-

!ems and take into account heuristics for the variable and value ordering used in AC, DAC and FDAC enforcing.