Valued Constraint Satisfaction Problems: Hard and Easy Problems

1 Introduction and related works

The CSP framework provides a very convenient framework for representing and solving various problems related to AI and OR (scheduling, assignment, design ... ). When a real problem is casted in the CSP framework, different types of knowledge have to be dealt with:

• Hard constraints: physical properties (eg. spatial or temporal constraints), which have to be necessarily sat­ isfied, are naturally represented as constraints;
• Preferences: properties which should be satisfied "when possible" (due dates, user preferences, cost. .. ) are either represented as constraints or simply ignored;
• Uncertainties: properties that are relevant in some sit­ uations which cannot be predicted with certainty; such properties are then ignored, or represented as constraints.

Thus, such soft constraints can be either ignored, which nat­ urally leads to a poor mean quality of the solutions or rep­ resented as hard constraints which may yield an inconsis­ tent CSP. A better solution is to take the violation of these constraints into account in a specific criterion that should be minimized.

Various proposals have been made in this direction, extend­ ing classical CSP in order to express "sojf' constraints with CERT-ONERA 2 Av. Edouard Belin 31055 Toulouse Cedex France verfail@cert.fr a dedicated semantics in terms of priorities [Schiex, 1992; Borning et al., 1989], preference degrees [Rosenfeld et al., 1976; Martin-Clouaire, 1992; Dubois et al., 1993; Ruttkay, 1994], costs [ShapiroandHaralick,1981; Dechteretal.,1990; Freuder and Wallace, 1992] or probabilities [Rosenfeld et al., 1976; Fargier and Lang, 1993]. The specific nature of the criterion optimized allows dedicated branch and bound algo­ rithms to be defined.

·This work has been partially funded by the French Centre Na­ tional d'Etudes Spatiales and by the European Euclid project CALMA.

In these approaches, hard constraints and preferably satis­ fied/uncertain constraints are expressed as constraints but a valuation (usually a number) is associated to each constraint c, or each tuple t of a constraint. This valuation expresses the impact of violating the constraint c or using the tuple t on the quality of the solution. These valuations are combined using an operator that gives them a specific semantics. For example, in [Schiex, 1992], the valuations of violated constraints are combined using a max operator, which gives the valuations an interpretation in terms of priorities, while in [Shapiro and Haralick, 1981]. the valuations are numbers combined using addition, with an obvious interpretation as costs.

In this paper, rather than choosing a specific set for ex­ pressing valuations and a specific operator, we observe that an ordered commutative monoid (an ordered set with an oper­ ator satisfying some properties), is enough to encompass most existing CSP extensions. The valuations are taken from the set of the monoid, combined using its operator and compared using the order. For the sake of simplicity, we consider that valuations are only associated to constraints.

Our aim is then to use this abstract framework to provide general algorithms and properties, to bring to light relations between previous proposals and to identify where the difficult problems are, and what property makes them difficult 1 .

The next section defines the valued CSP (VCSP) frame­ work, rapidly justifies the algebraic structure used and gives some simple properties. Section 3 describes previous propos­ als as VCSP and shows how they relate to each other in terms of rationality and complexity. Section 4 considers the generic extension of different Backtrack based algorithms and ends with preliminary experiments on the related observed com­ plexities of some types of VCSP.

1 This work is therefore related to [Shafer, 1991] which considers an axiomatic framework where hyper-tree structured problems are solved efficiently and to [Minoux, 1976; Bistarelli et al., 1995] where a semi-ring is used to study the possible generalization of shortest path and k-consistency enforcing algorithms respectively.

2 Towards valued CSP

A classical CSP is defined by a set X = { x 1 , ... , x n} of variables, each variable Xi having an associated finite domain di. A constraint c = (Xc, Rc) is defined by a set of variables Xc C X and a relation Rc between the variables of Xc i.e., a subset of the Cartesian product IL:,EXc di. A CSP is noted (X, D, C), where Dis the set of the domains and C the set of the constraints. A solution of the CSP is an assignment of values to the variables in X such that all the constraints are satisfied: for each constraint c = (Xc, Rc), the tuple of the values taken by the variables of Xc belongs to Rc.

To express the fact that a constraint may eventually be vio­ lated, we annotate each constraint with a valuation taken from a set of valuations E equipped with the following structure:

Definition 1 A valuation structure (E, ®, >-) verifies:

• E is a set, whose elements are called valuations, which is totally ordered by >-,with a maximum element noted T and a minimum element noted ..L;
• ® is a commutative, associative closed binary operation on E that verifies:

• Identity: Va E E, a® ..L =a;
• Monotonicity: Va, b, c E E,

• Absorbing element 2 : Va E E, (a® T) = T.

This structure of totally ordered commutative monoid with a monotonic operator is also known in uncertain reasoning, E being restricted to [0, 1], as a "triangular co-norm" [Dubois and Prade, 1982]. In the rest of the paper, we implicitly sup­ pose that the computation of >- and ® are always polynomial in the size of their arguments.

2.1 Justification and properties

The ordered set E allows different levels of violations to be expressed. Commutativity and associativity guarantee that the valuation of an assignment depends only on the set of the valuations of the violated constraints, and not on the way they are aggregated. The element T corresponds to unacceptable violation and is used to express hard constraints. The element ..L corresponds to complete satisfaction. These maximum and minimum elements can be added to any totally ordered set, and their existence is supposed without any loss of generality. Monotonicity guarantees that the valuation of an assignment that satisfies a set B of constraints will always be as good as the valuation of any assignment which satisfies a subset of B. 1\vo additional properties will be considered later because of their influence on algorithms and computation:

Strict monotonicity (Va, b, c E E, if (a >- c), (b 'I T) then (a ® b) >- ( c ® b)) guarantees that any modification in a set of valuations that does not contain T passes on the aggregation, via ®, of these valuations: the fact that something can be locally improved can not be globally ignored. This type of property is usual in multi-criteria theory, namely in social welfare theory [Moulin, 1988].

2 Actually, the "absorbing element" property can be inferred from the other axioms: since ..Lis the identity, (..L@ T) = T; since ..Lis minimum, Va E E, (a® T) ~ (..L® T) = T; since, Tis maximum, VaEE,(a®T)=T

ldempotency (Va E E, a® a= a) is fundamental in all CSP algorithms that enforce k-consistency since it guarantees that a constraint that is satisfied by all the solutions of a CSP can be added to the CSP without changing its meaning. Idempotency is incompatible with strict monotonicity as soon as E has more than two elements 3 · It should be noted that the only idempotent operator in a valuation structUre is max 4 ·

2.2 Valued CSP

A valued CSP is then simply obtained by annotating each constraint of a classical CSP with a valuation denoting the impact of its violation 5 or, equivalently, of its rejection from the set of constraints.

Definition 2 A valued CSP is defined by a classical CSP (X, D, C), a valuation structure S = (E, ®, >- ), and an application cp from C to E. It is noted (X, D, C, S, cp). cp(c) is called the valuation of c.

An assignment A of values to some variables Y c X can now be simply evaluated by combining the valuations of all the violated constraints using ®:

Definition 3 Given a VCSP P = (X, D, C, S, cp) and an assignment A of the variables ofY C X, the valuation of A with respect to the VCSP P is defined by:

The semantics of a VCSP is a distribution of valuation on the assignments of X (potential solutions). The problem consid­ ered is to find an assignment A with a minimum valuation. The valuation of such an optimal solution will be called the CSP valuation. It provides a gradual notion of inconsistency, from ..L, which corresponds to consistency, to T, for complete inconsistency.

Our notion ofVCSP is equivalent to [Freuder and Wallace, 1992] view of partial consistency. Indeed, a VCSP defines a relaxation lattice equipped with a distance measure:

Definition4 Given a VCSP P = (X,D,C,S,cp), a relax­ ation ofP is a classical CSP (X, D, C'), where C' C C.

Relaxations are naturally ordered by inclusion of constraint sets. Obviously, the consistent inclusion-maximal relaxations are the classical CSP which can not get closer to the original problem without loosing consistency. It is also possible to order relaxations by extending the valuation distribution to relaxations:

Definition 5 Given a VCSP P = (X, D, C, S, cp), and are­ laxation (X, D, C') ofP, the valuation of this relaxation is:

3 From identity, it follows that Va E E, (a@ ..L) = a, then for any a, ..L -< a -< T, strict monotonicity implies that (a@ a) >- a and idempotency implies that (a @ a) = a.

4 This result is well known fort -conorrns. From monotonicity and idempotency, wehaveVb ~a, (a®..L) =a~ (a®b) ~a= (a®a) and therefore a @ b = a.

6 The finer approach which associates a valuation to each tuple of a relation allows the expression of gradual violation of a constraint. However, since ..L is the identity, and since domains are finite, such a gradual relation may be simply expressed as a conjunction of annotated constraints and the restriction to annotated constraints is made without any loss of generality.

The valuation of the top of the relaxation lattice, CSP (X , D , C), is obviously .L The valuations of the other relax­ ations can be understood as a distance to this ideal problem. The best assignments of X are the solutions of the closest consistent problems of the lattice. The monotonicity of ® ensures that the order on problems defined by this valuation distribution is consistent with the inclusion order on relax­ ations.

Definition 6 Given a VCSP P = (X, D, C, S, <p), and (X, D , C'), (X, D, C"), two relaxations ofP:

If® is strictly monotonic, the inequality becomes strict if the valuation ofP is not T.

This last result shows that strict monotonicity is indeed a highly desirable property since it guarantees that the order induced by the valuation distribution will respect the strict inclusion order on relaxations (if the VCSP valuation is not equal to T). In this case, optimal consistent relaxations are always selected among inclusion-maximal consistent relax­ ations, which seems quite rational.

Since idempotency and strict monotonicity are incompati­ ble as soon as E has more than two elements, idempotency can be seen as an undesirable property, at least from the ra­ tionality point of view. Using an idempotent operator, it is possible for a consistent non inclusion-maximal relaxation to get an optimal valuation.

There is an immediate relation between optimal assign­ ments and optimal consistent relaxations. Indeed, to any assignment A of X, we can associate the classical consistent CSP [A]p obtained by excluding the constraints violated by A.

Definition 7 Given a VCSP P = (X, D, C, S, <p) and an assignment A of the variables of X , we note [A]p the classical consistentCSP(X,D,C')whereC' = {c E C,Asatisfiesc}. [A]p is called the consistent relaxation ofP associated to A.

Obviously, Vp (A) = Vp ([A]p) and [A]p is among the opti­ mal problems that A satisfies. It is equivalent to look for an optimal assignment or for an optimal consistent relaxation.

3 Classes of VCSP and their relationships

We consider some extensions of the CSP framework as VCSP:

I\· VCSP or classical CSP correspond to the trivial boolean lattice E = {t, f}, t = .l -< f = T, ® = 1\ (or max), all constraints being annotated with T. The operation 1\ is both idempotent and strictly monotonic (this is the only case where both properties may exist simultaneously).

Max-VCSP or possibilistic CSP [Schiex, 1992] correspond to the operation ® = max. Traditionally, E = [0, 1], 0 = .l, 1 = T . The annotation of a constraint is interpreted as a pri­ ority degree. A preferred assignment minimizes the priority of the most important violated constraint. The idempotency of max lead to the so-called "drowning-effect": if a constraint with priority a has to be necessarily violated then any con­ straint with a priority lower then a is simply ignored and can be rejected from any consistent relaxation without changing its valuation.

Obviously, a classical CSP is simply a specific possibilistic CSP where only one valuation other than .l is used. Note that finite fuzzy CSP [Dubois et al., 1993] can easily be cast as possibilistic CSP and vice-versa.

E· VCSP or penalty CSP, correspond to the operation ® = + inN u { +oo }, using the usual ordering <. First considered in [Shapiro and Haralick, 1981 ], penalty CSP have been con­ sidered as Partial CSP in [Freuder and Wallace, 1992], all constraint valuations being equal to 1.

II-VCSP or probabilistic CSP correspond to the operation x ® y = 1 - (1 - x)(1 - y) in E = [0, 1]. II-VCSP have been defined in [Fargier and Lang, 1993] to enable the user to represent ill-known problems, where the existence of con­ straints in the real problem is uncertain. Each constraint c is annotated with its probability of existence, all supposed to be independent. The probability that an assignment that vio­ lates 2 constraints c1 and c2 will not be a solution of the real problem is therefore 1- (1 - <p(c1))(1- <p(c2 )).

Lex-VCSP (or lexicographic CSP) offer a combination of penalty and possibilistic CSP and suppress the "drowning effect" of the latter [Fargier et al., 1993]. A valuation is either a designated element T or a multiset (elements may be repeated) of elements of [0, 1[ (or any other totally ordered set, defining priorities).

The operation ® is simply multi-set union, extended to treat T as an absorbing element (the empty multi-set is the identity .l). The order >- is the lexicographic (or alphabetic) total order induced by the order > on multisets and extended to give T its role of maximum element: let v and v' be two multisets and a and a' be the largest elements in v and v', v >- v' iff either a > a' or (a = a' and v - {a} >- v' - {a'}). The recursion ends on 0, the minimum multi-set.

3.1 Properties and relations

In order to compare the previous VCSP classes, that relies on different valuation structures, we introduce the following notion:

Definition 8 A VCSP P = (X, D, C, S , <p) is a refinement of the VCSP P' = (X, D, C', S', <p 1 ) if for any pair of assign­ ments A, A' of X such that Vp· (A) >- Vp· (A') in S' then Vp(A) >- Vp(A') inS. Pis a strong refinement ofP' if the property holds when A, A' are assignments of subsets of X .

This main point is that if P is a refinement of P', then the set of optimal assignments of P is included in the set of optimal assignments of P'; the problem of finding an optimal assignment of P can be reduced to the same problem in P'.

Definition9 1Wo VCSP P = (X,D,C, S, <p) and P' = (X, D , C', S', <p 1 ) will be said equivalent iff each one is a refinement of the other. They will be said strongly equivalent if each one is a strong refinement of the other.

Equivalent VCSP define the same ordering on assignments of X and have the same set of optimal assignments: the problem of finding an optimal assignment is equivalent in both VCSP.

Considering all previous VCSP classes, we may partition them according to the idempotency of the operator: /\-VCSP and Max-VCSP on one side and E-VCSP, II-VCSP and Lex­ VCSP on the other. Interestingly, this partition is in agreement with polynomial transformations that exist between instances of different classes for the problem of finding an optimal as­ signment (or the corresponding decision problem of existence of an assignment with a valuation lower than a given v E E).

Idempotent classes: a/\-VCSP is nothing but a specific Max­ VCSP that uses only the valuation T and the transformation from 1\-VCSP to Max-VCSP is simply the identity.

Conversely, the problem of the existence of an assign­ ment of valuation strictly lower than v in a Max-VCSP (X, D, C, S, cp) can easily be reduced to the existence of a solution for the classical CSP (X,D,C") such that C' = { c E C I cp( c) ~ v}: if such a constraint is violated, the assignment valuation is larger than v and conversely. Thus, using binary search, the optimal assignment in a Max-VCSP can be found in a logarithmic number of resolution of a clas­ sical CSP. Indeed, all the traditional polynomial classes and problems (k-consistency enforcing ... ) of classical CSP can be extended to Max-VCSP in this way [Fargier, 1994].

Stricly monotonic classes: in this section, we put II-VCSP aside because II-VCSP combination operator relies on mul­ tiplication of real numbers. However, note that if we also relax the integrity constraint on penalties in L:-VCSP (penal­ ties are allowed to take values in lR instead of N), then these frameworks are related by a simple isomorphism: a constraint with a probability cp(c) of existence can be transformed in a constraint with a penalty of -log(1 - cp(c)) (and conversely using the transformation 1-e-tp{c)). The two VCSP obtained in this way are obviously strongly equivalent.

A penalty CSP can easily be polynomially transformed in a lexicographic CSP: the valuation k E N is transformed in a multiset containing a given element a "I 0 repeated k times (noted { (a, k)} ), where a is a fixed priority and the valuation +oo is transformed to T. The lexicographic VCSP obtained (in polynomial time) is obviously strongly equivalent to the original penalty VCSP.

Interestingly, a lexicographic CSP may also be transformed into a strongly equivalent penalty CSP. Let a 1 , ... , ak be the elements of ]0, 1[ that appear in all the Lex-VCSP annota­ tions, sorted in increasing order. Let ni be the number of occurrences of ai in all the annotations of the VCSP. The lowest priority a 1 is associated to the penalty I ( a 1) = 1, and inductively ai is associated to l(ai) =I( ai-l) x (ni-l+ 1) (this way, the penalty l(ai) associated to priority i is strictly larger than the largest possible sum of l(aj),j < i. This is immediately satisfied for a 1 and inductively verified for ai). An initial lexicographic valuation is converted in the sum of the penalties I ( ai) for each ai in the valuation. The valuation T is converted to +oo. All the operations involved, sum and multiplication, are polynomial and the sizes of the operands remain polynomial: if k is the number of priorities used in the VCSP and f.. the maximum number of occurrences of a priority, then the largest penalty l(ak) is in O(f..k), with a length in 0 ( k. log (f..)) while the original annotations used at least space O(k + log(f..)). Therefore, the transformation is polynomial.

An isthm between idempotent and strictly monotonic VCSP is provided by Lex-VCSP: a Max-VCSP can be transformed in a Lex-VCSP by annotating each constraint with a multi-set containing one occurrence of the original (possibilistic) an­ notation if it is not equal to 1, or by T else. In this case, an optimal assignment of the Lex-VCSP not only minimizes the priority of the most important constraint violated, but also, the number of constraint violated successively at each level of priority, from the highest first to the lowest. The Lex­ VCSP is therefore a strong refinement of the original possibilistic VCSP, obtained in polynomial time and the problem of finding one optimal assignment for the Max-VCSP may be reduced to the problem of finding one optimal assignment of the corresponding Lex-VCSP.

The partition between idempotent and strictly monotonic VCSP classes is also made clear at the level of polynomial classes: the existence of an assignment with a valuation lower than v in a strictly monotonic binary VCSP with domains of cardinality two is obviously NP-hard by restriction to MAX2SAT [Garey et al., 1976]. One of the few polynomial classes which seems to extend to all classes of VCSP is the class of CSP structured in hyper -tree (see !Dechter et al., 1990; Shafer, 1991]).

4 Extending traditional algorithms

4.1 Local consistency

In classical binary CSP (all constraints are supposed to involve two variables only), satisfiability defines an NP-complete problem. k-consistency properties and algorithms [Freuder, 1982] offer a range of polynomial time weaker properties: enforcing strong k-consistency in a consistent CSP will never lead to an empty CSP.

From the VCSP point of view, strong k-consistency enforc­ ing defines a kind of lower bound of the CSP valuation: if strong k-consistency enforcing yields an empty CSP, then we know that the CSP valuation is greater than T and therefore equal to T, else it is simply greater than .l, which is always true.

Arc-consistency (strong 2-consistency) is certainly the most prominent level of local consistency and has been ex­ tended to Max-VCSP years ago [Rosenfeld et al., 1976]. In Max-VCSP, arc-consistency can be defined as follows:

Definition 10 A VCSP P is said to be arc-consistent iff ( 1) there exists ,for each variable, a value that defines an assign­ ment with a valuation strictly lower than T and (2) any assign­ ment A of one variable can be extended to an assignment A' on two variables with the same valuation (Vp(A) = Vp(A')).

Polynomial worst-case time algorithms that enforce this prop­ erty on Max-CSP are defined in [Rosenfeld et al., 1976; Snow and Freuder, 1990; Schiex, 1992]. These algorithms yield an arc-consistent Max-VCSP with the same valuation distribution on complete assignments, and a lower bound on the VCSP valuation can easily be derived from it.

Obviously, this definition could also be used in non idempo­ tent VCSP. But it is useless if we can not define the correspond­ ing arc-consistency enforcing algorithms that should compute, in polynomial time, a VCSP P' which is both arc-consistent and in some sense "equivalent' to the original VCSP P. The strongest level of equivalence one could achieve (stronger than our strong equivalence notion, def. 9) is the equality of the valuations in both VCSP for all complete assignments.

But the generalization of AC enforcing algorithms that consists in using min and ® respectively for projection and combination of constraints fails for non idempotent mono­ tonic VCSP as it has been shown in a similar framework (see [Bistarelli et al., 1995], in these proceedings). The distri­ bution of valuations may be modified and the algorithm may fail to terminate. However, it is still an open question whether more drastic modifications of the algorithms/properties, or a weakening of the "equivalence" notion (as def. 9) would allow us to recover something related to arc-consistency.

4.2 Tree search

Following the works from [Shapiro and Haralick, 1981; Schiex, 1992; Freuder and Wallace, 1992; Dubois et al., 1993 ], we try to extend some traditional CSP algorithms to the binary VCSP framework to solve tl:le problem of finding a provenly optimal assignment. The class of algorithms which we are interested in are hybrid algorithms that combine backtrack tree-search with some level of local consistency enforcing at each node. These algorithms have been called look -ahead, prospective ur prophylactic algorithms. Some possible in­ stances have been considered in [Nadel, 1989]: Backtrack, Forward-Checking , Really Full Look Ahead. We consider here that such algorithms are described by the type of lo­ cal consistency enforcing maintained at each node: check­ backward, check forward, arc-consistency or more ...

In prospective algorithms, an assignment is extended un­ til either a complete assignment (a solution) is found, or the given local consistency property is not verified on the current assignment: backtrack occurs. The extension of such algo­ rithms to the VCSP framework, where the problem is now an optimization problem, relies on a transformation of the Back­ track tree search schema to a Depth First Branch and Bound algorithm. DFBB is a simple depth first tree search algorithm, which, like Backtrack, extend an assignment until either (1) a complete assignment is reached: a new "better" solution is found or (2) a given lower bound on the valuation of the best assignment that can be found by extending the current assignment exceeds the valuation of the current best solution found: backtrack occurs. The lower bound used defines the algorithm. Our aim is to derive a lower bound from any given local consistency property.

In classical CSP, seen as /1.-VCSP, the actual local consis­ tency property used gives the "lower bound": for example, in Really Full Look Ahead, the inexistence of an arc-consistent closure of the CSP guarantees that the valuation of any ex­ tension of the current assignment will be greater than T and therefore equal to T. However, as we pointed out earlier, no arc-consistency enforcing algorithm is available for strictly monotonic VCSP. We will therefore use classical local consis­ tency notions plus the notion of relaxation of a VCSP (which defines classical CSP) to define our class of bounds:

Property 1 Given a classical local consistency property L, a lower bound on the valuation of a given VCSP P is defined by the valuation of an optimal relaxation ofP among those that satisfy the "local consistency" property L used (consistency of the current assignment, absence of domain wipe-out after check-forward or arc-consistency enforcing ... ).

This valuation is a lower bound of the valuation of an optimal assignment since the valuation of an optimal assignment is also the valuation of an optimal consistent relaxation and all the relaxations where the "local consistency" property L is not verified are non consistent.

These lower bounds verify two interesting properties:

• they guarantee that the extended algorithm will behave as the original "classical" algorithm when applied to a classical CSP seen as a /1.-VCSP (a classical CSP seen as a /1.-VCSP has only one relaxation with a valuation lower than T: itself);
• a stronger local consistency property will define a better lower bound, leading to a tree search with less nodes but possibly more computation at each node.

4.3 Extending Backtrack

Backtrack uses the local inconsistency of the current partial assignment as the condition for backtracking. Therefore, the lower bound derived is the valuation of an optimal relaxation in which the current assignment is consistent. This is simply the relaxation which precisely rejects the constraints violated by the current assignment (these constraints have to be re­ jected or else local inconsistency will occur; rejecting these constraint suffices to restore the consistency of the current assignment in the relaxation). The lower bound is therefore simply defined by:

and is obviously computable in polynomial time.

The lower bound can easily be computed incrementally when a new variable Xi is assigned: the lower bound associ­ ated to the father of the current node is aggregated with the valuations of all the constraints violated by Xi using ® ..

The generic VCSP algorithm defined encompass all the "Branch and Bound" algorithms defined for Max-VCSP or :E­ VCSP in [Schiex, 1992; Freuder and Wallace, 1992; Fargier, 1994; Ruttkay, 1994]. Note that for Max-VCSP, thanks to idempotency, it is useless to test whether constraints whose valuation is lower than the lower bound associated to the father node have to be rejected since their rejection cannot influence the bound.

4.4 Extending Forward Checking

Forward-checking uses an extremely limited form of arc­ consistency: backtracking occurs as soon as all the possible extensions of the current assignment A on any uninstantiated variable are locally inconsistent: the assignment is said non forward-checkable. Therefore, the lower bound used is the minimum valuation among the valuations of all the relaxations that makes the current assignment forward-checkable.

A relaxation in which A is forward-checkable (1) should necessarily reject all the constraints violated by A itself and (2) for each uninstantiated variable Xi it should reject one of the sets C (Xi, v) of constraints that are violated if Xi is instan­ tiated with value v of its domain. Since ® is monotonic, the minimum valuation is reached by taking into account,for each variable, the valuation of the set C(xi, v) of minimum valua­ tion. The bound is again computable in polynomial time since it is the aggregation of ( 1) the valuations all the constraints violated by A itself (i.e., the bound used in the extension of the backtrack algorithm, see 4.3) and (2) the valuations of the constraint in all the C(xi, v). This computation needs less than (e.n.d) constraint checks and ® operations (e is the number of constraints); all the minimum valuation can be computed with less than (d.n) comparisons and aggregated with less than n ® operations. Note that the lower bound derived includes the bound used in the backtrack extension plus an extra component and will always be better than the "Backtrack" bound.

The lower bound may be incrementally computed by main­ taining during tree search, and for each value v of every unas­ signed variable Xi the aggregated valuation B(v, Xi) of all the constraints that will be violated if v is assigned to Xi given the current assignment. Initially, all B(v, Xi) are equal to . .L When the assignment A is extended to A' =Au {xi = J.t}, the B may be updated as follows:

that takes into account all the constraints between Xi and Xj that are necessarily violated if J.t is assigned to Xj· Upon backtrack, the B have to be restored to their previous values, as domains in classical Forward-checking. Note that the B offer a default value heuristic: choose the value with a minimum B.

The lower bound is simply obtained by aggregating, using ®, the valuations of all the constraints violated by the assign­ ment and all the minimum B(v, Xi) for each unassigned vari­ able. The aggregated valuation v(A'), A' = Au { Xj = J.t} ), of all the constraints violated by the assignment A' is eas­ ily computed by taking the valuation v (A) computed on the father node ®'ed with B(J.t, Xj ).

Additional sophistications include deleting values v of the domains of non instantiated variables if the aggregated valuation of v(A') and B(v, Xi) exceeds the upper bound (see [Freuder and Wallace, 1992]). The generic VCSP al­ gorithm defined encompass the forward-checking based al­ gorithm for Max-VCSP described in [Schiex, 1992] or the Partial Forward-checking algorithm defined for :E-VCSP in [Freuder and Wallace, 1992]. Note that for Max-VCSP, and thanks to idempotency, the updating of B can ignore con­ straints whose valuation is less than the B updated or than the current lower-bound.

4.5 Trying to extend Really Full Look Ahead

Really Full Look Ahead maintains arc consistency during tree search and backtracks as soon as the current assignment in­ duces a domain wipe-out: the CSP has no arc-consistent clo­ sure. For a VCSP, the bound which can be derived from arc-consistency will be the minimum valuation among the valuations of all the relaxations such that the current assign­ ment does not induces a domain wipe-out.

Let us consider any class ®- VCSP of the VCSP framework such that® is strictly monotonic and for any a1 bE E, a, b -< T, (a ® b) -< T. Let £ be any valuation different from T and .L The decision problem corresponding to the computation of the lower bound in this class can be formulated as:

Problem 1 (MAX-AC-CSP) Given such a ®-VCSP and a val­ uation v, is there a set C' C C such that the relaxation (X, D, C') has a non empty arc-consistent closure and a val­ uation lower than v?

Theorem 1 MAX-AC-CSP is strongly NP-complete.

Sketch of proof: The problem belongs to N P since computing the arc-consistent closure of a CSP can be done in polynomial time and we have supposed that ® and >- are polynomial in the size of their arguments.

We give the polynomial transformation from MA.X2SAT [Garey et al., 1976] to MAX-AC-CSP. An instance of MAx2SAT is defined by a set 41 of e 2-clauses and a positive integer k, the problem being the existence of a consistent subset of 41 of cardinality larger than k. Let T be the set of n propositional variables occurring in 41. We consider the binary CSP (X, D, C) which is composed of n + 2n. ( e + 1) variables: (1) the first n variables x 1 , ··· , Xn corresponds to the n variables of T and have a domain of cardinality two corresponding to the boolean values t and f; (2) the next 2n.(e+ 1) variables will have a domain of size 1, containing the only value *. This set of variables is composed of n sets of 2e + 2 variables { ti,l, ... , ti,e+l, /i,l, ... , /i,e+d associated to the original variable Xi.

The constraints that appear in C are composed of 3 sets: (1) a set of e constraint corresponding to the e clauses of 41 on the variables x1, ... , xn; (2) for each variable Xi and its associated e + 1 variables ti ,j , a set c; of e + 1 constraints which connect Xi with ti,j and allow only the tuple (t, * ); (3) for each variable Xi and its associated e+l variables /i,j, a set C} of e + 1 constraints which connect Xi with /i,j and allow only the tuple (!, *)· All the constraints have the valuation £.

For example, Figure 1 illustrates the micro-structure of the CSP built from the set 41 = {x1 V x2,x2 V x3,x1 V x3}. The trans­ formation is clearly polynomial. Furthermore, one may prove that the existence of a truth assignment that satisfies at least k clauses of 41 is equivalent to the existence of a relaxation with a non­ empty arc-consistent closure and a valuation lower than £ ® · · · ® f. with n. ( e + 1) + ( n - k) occurrences of £. This shows that MA.X2SAT ex MAX-AC-CSP. 0

Therefore, extending Really Full Look Ahead seems diffi­ cult since computing the lower bound itself is NP-complete. For idempotent VCSP, the bound may be computed using polynomial time algorithms for enforcing arc-consistency [Rosenfeld et al., 1976; Snow and Freuder, 1990].

4.6 Experimentations

The Forward-Checking algorithm has been coded and applied to random VCSP generated as follows: a classical random CSP with 16 variables, domains of size 9 is generated as in [Hubbe and Freuder, 1992]. A first possibilistic VCSP is obtained by randomly assigning a valuation t, ! , ~ or 1 to each constraint. A lexicographic VCSP is then bui1t simply by using the transformation from possibilistic to lexicographic CSP described in section 3. This VCSP is a strong refinement of the original possibilistic CSP.

Because of limited space, we only report mean number of constraint checks performed to find an optimal assign­ ment and prove optimality for a slice of the random CSP space (see Figure 2): constraint satisfiability is fixed to 60% and the constraint graph goes from tree structured CSP to a complete graph. At each point 50 classical, possibilistic and corresponding lexicographic CSP are solved with the following heuristics: the variable which minimizes the ratio do­ main/degree is chosen, the value that minimizes B is chosen. A first conclusion is that solving consistent CSP as VCSP, i.e., uselessly trying to anticipate a possible inconsistency, is relatively inexpensive, even for Lex-VCSP. On inconsis­ tent CSP, possibilistic CSP are not much harder than classical CSP, but the transition phase is apparently extended to the left. Last, but not least, lexicographic CSP are incredibly more difficult which again shows the computational com­ plexity of strictly monotonic ®: rationality seems expensive. Stronger argument could probably be obtained using recent developments in complexity theory, the transformations of Section 3.1 defining metric reductions between optimization problems [Krentel, 1988].

S Conclusion

The VCSP framework enables the expression of a large num­ ber of real constraint satisfaction/optimization problems. If idempotent VCSP have already received a lot of attention and most classical CSP algorithms/properties have been extended to this setting [Fargier, 1994], the case of non idempotent op­ erators, a desirable property as it has been shown, seems much harder to tackle and few CSP algorithms have been extended to this case [Freuder and Wallace, 1992].

Since local consistency enforcing algorithms are unavail­ able in this case, we have considered a general class of bounds, that could be used in a depth first branch and bound algorithm and which have been derived from classical local consistency properties. It appears that at the level of arc-consistency, the problem of computing the bound is as difficult as solving a VCSP itself and other types of bounds have to be considered.