Constraint Solving over Semirings

1 Introduction

Classical constraint satisfaction problems (CSPs) [Mon­ tanari, 1974; Mackworth, 1988] are a very expressive and natural formalism to specify many kinds of real­ life problems. In fact, problems ranging from map col­ oring, vision, robotics, job-shop scheduling, VLSI de­ sign, etc., can easily be cast as CSPs and solved using one of the many techniques that have been developed for such problems or subclasses of them [Freuder, 1978; 1988; Mackworth and Freuder, 1985; Mackworth, 1977; Montanari, 1974] .

However, they also have evident limitations, mainly due to the fact that they are not very flexible when trying to represent real-life scenarios where the knowledge is not completely available nor crisp. In fact, in such situations, the ability of stating whether an instantiation of values to variables is allowed or not is not enough or sometimes not even possible. For these reasons, it is natural to try to extend the CSP formalism in this direction.

For example, in [Rosenfeld et al., 1976; Dubois et al., 1993; Ruttkay, 1994] CSPs have been extended with the ability to associate to each tuple, or to each constraint, a level of preference, and with the possibility of com­ bining constraints using min-max operations. This ex­ tended formalism has been called Fuzzy CSPs (FCSPs). Other extensions concern the ability to model incomplete knowledge of the real problem [Fargier and Lang, 1993], to solve overconstrained problems [Freuder and Wallace, 1992], and to represent cost optimization problems.

In this paper we define a constraint solving framework where all such extensions, as well as classical CSPs, can be cast. However, we do not relax the assumption of a finite domain for the variables of the constraint prob­ lems. The main idea is based on the observation that a semiring (that is, a domain plus two operations satisfy­ ing certain properties) is all what is needed to describe many constraint satisfaction schemes. In fact, the do­ main of the semiring provides the levels of consistency (which can be interpreted as cost, or degrees of prefer­ ence, or probabilities, or others), and the two operations define a way to combine constraints together . Specific choices of the semiring will then give rise to different instances of our framework.

In classical CSPs, the so-called local consistency tech­ niques [Freuder, 1978; 1988; Mackworth, 1988; 1977; Montanari, 1974; Montanari and Rossi, 1991] have been proved to be very effective when approximating the solu­ tion of a problem. In this paper we study how to gener- · alize this notion to our framework, and we provide some sufficient conditions over the semiring operations which guarantee that such algorithms can be fruitfully applied also to our scheme. Here for being "fruitfully applica­ ble" we mean that 1) the algorithm terminates and 2} the resulting problem is equivalent to the given one and it does not depend on the nondeterministic choices made during the algorithm.

The advantage of our framework, that we call SCSP (for Semiring-based CSP}, is that one can just see his own constraint solving framework as an instance ofSCSP over a certain semiring, and can immediately inherit the results obtained for the general framework. In particu­ lar, in this case, one can immediately see whether a local consistency technique can be applied or not . This allows one also to justify many informally taken choices in exist­ ing constraint solving schemes. In this paper we study several known and new constraint solving frameworks, casting them as instances of SCSP, and for some of them we prove the possibility of applying k-consistency algo­ rithms.

Due to space limitations, some of the formal defini­ tions, theorems, and proofs have been omitted or just informally sketched.

2 C-semirings and their properties

We associate a semiring to the standard definition of con­ straint problem, so that different choices of the semir­ ing represent different concrete constraint satisfaction schemes. Such semiring will give us both the domain for the non-crisp statements and also the allowed oper­ ations on them. More precisely, in the following we will consider c-semirings, that is, semirings with additional properties of the two operations.

Definition 1 A semiring is a tuple (A,+, x, 0, 1) such that

• A is a set and 0, 1 E A;
• +, called the additive operation, is a closed {i.e., a, bE A implies a+ bE A}, commutative (i.e., a+ b = b +a) and associative {i.e., a+ (b +c)= (a+ b)+ c) operation such that a+ 0 =a= 0 +a (i.e., 0 is its unit element);
• x, called the multiplicative operation, is a closed and associative operation such that 1 is its unit element and a x 0 = 0 = 0 x a {i.e., 0 is its absorbing element);
• x distributes over+ (i.e., ax (b +c) = (ax b)+ (ax c)).

A c-semiring is a semiring such that + is idempotent, x is commutative, and 1 is the absorbing element of+. 0

The idem potence of the + operation is needed in order to define a partial ordering ~s over the set A, which will enable us to compare different elements of the semiring. Such partial order is defined as follows: a ~s b iff a+ b = a. Intuitively, a ~s b means that a is "better" than b .. This will be used later to choose the "best" solution in our constraint problems. It is important to notice that both + and x are monotone on such ordering.

The commutativity of the x operation is desirable when such operation is used to combine several con­ straints. In fact, were it not commutative, it would mean that different orders of the constraints give different re­ sults.

If 1 is also the absorbing element of the additive oper­ ation, then we have that 1 ~s a for all a. Thus 1 is the minimum (i.e., the best) element of the partial ordering. This implies that the x operation is extensive, that is, that a < a x b. This is important since it means that combin~g more constraints leads to a worse (w.r.t. the ::;s ordering) result. The fact that 0 is the unit element of the additive operation implies that 0 is the maximum element of the ordering. Thus, for any a E A, we have 1 ::;sa ~s 0.

In the following we will sometimes need the x op­ eration to be closed on a certain finite subset of the c-semiring. More precisely, given any c-semiring S = (A,+, x,O, 1), consider a finite set I~ A. Then, xis !-closed if, for any a, bE J, (ax b) E I.

3 Constraint systems and problems

A constraint system provides the c-semiring to be used, the set of all variables, and their domain D. Then, a constraint over a given constraint system specifies the involved variables and the "allowed" values for them. More precisely, for each tuple of values of D for the in­ volved variables, a corresponding element of the semiring is given. This element can be interpreted as the tuple weight, or cost, or level of confidence, or else. ~inally, a constraint problem is then just a set of constramts over a given constraint system, plus a selected set of vari­ ables. These are the variables of interest in the problem, i.e., the variables of which we want to know the possible assignments compatibly with all the constraints.

Definition 2 A constraint system is a tuple CS = (S, D, V), where S is a c-semiring, D is a finite set, and V is an ordered set of variables. Given a constraint sys­ tem CS = (S,D, V), where S =(A,+, x,0,1), a con­ straint over CS is a pair (def, con), where con~ V and it is called the type of the constraint, and def : D"' - A (where k is the size of con, that is, the number of vari­ ables in it), and it is called the value of the constraint. Moreover, a constraint problem P over C S is a pair P = (C, con), where C is a set 1 of constraints over CS and con~ V. 0

In the following we will consider a fixed constraint sys­ tem CS = (S,D,V), where S = (A,+,x,0,1). Note that when all variables are of interest, like in many approaches to classical CSP, con contains all the vari­ ables involved in any of the constraints of the problem. This set will be denoted by V(P) and can be recovered by looking at the variables involved in each constraint: V(P) = u(def,con')EC con'.

In the SCSP framework, the values specified for the tuples of each constraint are used to compute corre­ sponding values for the tuples of values of the variables in con, according to the semiring operations: the multi­ plicative operation is used to combine the values of the tuples of each constraint to get the value of a tuple for all the variables, and the additive operation is used to obtain the value of the tuples of the variables of interest. More precisely, we can define the operations of combi­ nation ( 0) and projection ( .U.) over constraints. Anal­ ogous operations have been originally defined for fuzzy relations in [Zadeh, 1975], and have then been used for fuzzy CSPs in [Dubois et al., 1993]. Our definition is however more general since we do not consider a specific c-semiring but a general one.

Definition 3 Given two constraints c1 = (defi, con1) and c2 = (de/2, con2) over CS, their combination, c1® c2 , is the constraint c = (de/, con) with con = con1 Ucon2 and def(t) = defi(t !~~~,) x deh(t !~~~,), where, for any tuple of values t for the variables in a set I, t Lf, denotes the projection oft over the variables in the set I'. Moreover, given a constraint c = (de/, con) over CS, and a subset w of con, its projection over w, written c .O.w, is the constraint {def', con'} over C S with con' = w and def'(t') = E{tlt!~"=t'}def(t). 0

1 Note that, if x is not idempotent, it is necessary to see C as a multiset, and not as a set.

Using such operations, we can now define the notion of solution of a SCSP.

Definition 4 Given a constraint problem P = {C, con} over a constraint system CS, the solution of P is a constraint defined as Soi(P) = (Q9 C) .O.con 1 where Q9 C is the obvious extension of the combination operation to a set of constraints C. 0

In words, the solution of a SCSP is the constraint in­ duced on the variables in con by the whole problem. Such constraint provides, for each tuple of values of D for the variables in con, an associated value of A. Some­ times, it is enough to know just the best value associated to such tuples. In our framework, this is still a constraint (over an empty set of variables), and will be called the best level of consistency of the whole problem, where the meaning of "best" depends on the ordering $s defined by the additive operation.

Definition 5 Given a SCSP problem P = {C, con}, we define the best level of consistency of P as blevei(P) = (Q9C) .O.e- If blevei(P) = {blev,0}, then we say that P is consistent if blev <s 0. Instead, we say that P is a-consistent if blev =a. 0

Informally, the best level of consistency gives us an idea of how much we can satisfy the constraints of the given problem. Note that blevei(P) does not depend on the choice of the distinguished variables, due to the associative property of the additive operation. Thus, since a constraint problem is just a set of constraints plus a set of distinguished variables, we can also apply function blevel to a set of constraints only. Also, since the type of constraint blevei(P) is always an empty set of variables, in the following we will just write the value of blevel.

Another interesting notion of solution, more abstract than the one defined above, but sufficient for many pur­ poses, is the one that provides only the tuples that have an associated value which coincides with (the def of) blevei(P). However, this notion makes sense only when $s is a total order. In fact, were it not so, we could have an incomparable set of tuples, whose sum (via +) does not coincide with any of the summed tuples. Thus it could be that none of the tuples has an associated value equal to blevei(P) .

By using the ordering $s over the semiring, we can also define a corresponding partial ordering on con­ straints with the same type, as well as a preorder and a notion of equivalence on problems.

Definition 6 Consider two constraints c1, c2 over CS, and assume that con1 = con2 . Then we define the constraint ordering !;;;s as the following partial or­ dering: Ct !;;;s c2 if and only if, for all tuples t of values from D, deft(t) $s deh(t) . Notice that, if c1 !;;;s c2 and c2 !;;;s c1, then c1 = c2. Consider now two SCSP problems P1 and P2 such that P1 = {C1, con} and P2 = {C2, con}. Then we define the problem pre­ order !;;;p as: P1 !;;;p P2 if Soi(Pl) !;;;s Soi(P2). If P1 !;;;p P2 and P2 !;;;p P1, then they have the same solu­ tion. Thus we say that P1 and P2 are equivalent and we write P1 = P2. D

The notion of problem preorder can also be useful to show that, as in the classical CSP case, also the SCSP framework is monotone: (C, con) !;;;p (CUC', con) . That is, if some constraints are added, the solution (as well as the blevel) of the new problem is worse or equal than that of the old one.

4 Local Consistency

Computing any one of the previously defined notions (like the best level of consistency and the solution) is an NP-hard problem. Thus it can be convenient in many cases to approximate such notions. In classical CSP, this is done using the so-called local consistency techniques. Such techniques can be extended also to constraint solv­ ing over any semiring, provided that some properties are satisfied. Here we define what k-consistency [Freuder, 1978; 1988; Kumar, 1992] means for SCSP problems. In­ formally, an SCSP problem is k-consistent when, taken any set W ofk-1 variables and any k-th variable, the con­ straint obtained by combining all constraints among the k variables and projecting it onto W is better or equal (in the ordering !;;;s) than that obtained by combining. the constraints among the variables in W only.

Definition 7 Given a SCSP problem P = {C, con} we say that P is k-consistent if, for all W ~ V(P) such that size(W)= k-1, and for all x E (V(P)-W), ((®{c; I c; E C /\con;~ (W U {x})}) .O.w) !;;;s (®{c; I c; E C /\con;~ W)}, where c; =(de/;, con;} for all c; E C. D

Note that, since x is extensive, in the above formula for k-consistency we could also replace !;;;s by =s . In fact, the extensivity of X assures that the formula always holds when 2s is used instead of ~s-

Making a problem k-consistent means explicitating some implicit constraints, thus possibly discovering in­ consistency at a local level. In classical CSP, this is crucial, since local inconsistency implies global incon­ sistency. This is true also in SCSPs. But here we can be even more precise, and relate the best level of consistency of the whole problem to that of its subproblems.

Theorem 8 Consider a set of constraints C over CS, and any subset C' of C. If C' is a-consistent, then C is /3-consistent, with a $s /3.

Proof: If C' is a-consistent, it means that ®C' .O.t= {a, 0} . Now, C can be seen as C' ® C" for some C". By extensivity of x, and the monotonicity of+, we have that /3 = ®(C' ® C") .ij. 0 ~s ®(C) .ij. 0 =a. D

If a subset of constraints of P is inconsistent (that is, its blevel is 0), then the above theorem implies that the whole problem is inconsistent as well.

We now define a generic k-consistency algorithm, by extending the usual one for classical CSPs [Freuder, 1978; Kumar, 1992]. We assume to start from a SCSP problem where all constraints of arity k-1 are present. If some are not present, we just add them with a non­ restricting definition. That is, for any added constraint c = (def, con), we set def(t) = 1 for all con-tuples t . This does not change the solution of the problem, since 1 is the unit element for the x operation.

The idea of the (naive) algorithm is to combine any constraint c of arity k-1 with the projection over such k-1 variables of the combination of all the constraints connecting the same k-1 variables plus another one, and to repeat such operation until no more changes can be made to any (k-1)-arity constraint.

In doing that, we will use the additional notion of typed locations. Informally, a typed location is just a location (as in ordinary imperative programming) which can be assigned to a constraint of the same type. This is needed since the constraints defined in Definition 2 are just pairs (de/, con), where def is a fixed function and thus not modifiable. In this way, we can also assign the value of a constraint to a typed location (only if the type of the location and that of the constraint coincide), and thus achieve the effect of modifying the value of a constraint .

Definition 9 A typed location is an object I : con whose type is con . The assigment operation I := c, where c is a constraint (de/, con), has the meaning of associat­ ing, in the present store, the value def to I. Whenever a typed location appears in a formula, it will denote its value. 0

Definition 10 Consider an SCSP problem P = (C, con} and take any subset W ~ V(P) such that size(W) = k - 1 and any variable x E (V(P) - W) . Let us now consider a typed location I; for each con­ straint Ci = (defi, coni} E C such that li : coni. Then a k-consistency algorithm works as follows .

1. Jnizialize all locations by performing li := Ci for each Ci E C.
2. Consider
3. li : W,
4. A(W) = ® {li I coni~ (W U {x})} J.). W , and
5. B(W) = ® {li I coni~ .W} .

Then, if A(W) !bs B(W), perform li := li ®A(W) .

1. Repeat step 2 on all W and x until A(W) !;;; B(W) for all W .

Upon stability, assume that each typed location li : coni has eval(li) = defi. Then the result of the algorithm is a new SCSP problem P' = k-cons{P) = (C', con} such that C' = Ui (de/I,coni)· 0

Assuming the termination of such algorithm (we will discuss such issue later) , it is obvious to show that the problem obtained at the end is k-consistent . This is a very naive algorithm, whose efficiency can be improved easily by using the methods which have been adopted for classical k-consistency.

In classical CSP, any k-consistency algorithm enjoys some important properties. We now will study these same properties in our SCSP framework, and point out the corresponding properties of the semiring operations which are necessary for them to hold. The desired prop­ erties are as follows: that any k-consistency algorithm returns a problem which is equivalent to the given one;

that it terminates in a finite number of steps; and that the order in which the (k-1)-arity subproblems are se­ lected does not influence the resulting problem.

Theorem 11 Consider a SCSP problem P and a SCSP problem P' = k-cons{P ) . Then, P = P' {that is, P and P' are equivalent) if x is idempotent.

Proof: Assume P = (C,con) and P' = (C',con}. Now, C' is obtained by C by changing the definition of some of the constraints (via the typed location mechanism). For each of such constraints, the change consists of combin­ ing the old constraint with the combination of other con­ straints. Since the multiplicative operation is commuta­ tive and associative (and thus also®), ®C' can also be written as (®C)®C", where ®C" !;;;s ®C. If xis idem­ potent, then ((®C) ® C") =(®C) . Thus (®C)= (®C '). Therefore P :: P'. 0

Theorem 12 Consider any SCSP problem P where CS = (S, D, V} and the set AD= U(def,con)ec R(de!) , where R(de!) ={a l3t with def(t) =a} . Then the ap­ plication of the k-consistency algorithm to P terminates in a finite number of steps if AD is contained in a set I which is finite and such that + and x are !-closed.

Proof: Each step of the k-consistency algorithm may change the definition of one constraint by assigning a dif­ ferent value to some of its tuples. Such value is strictly worse (in terms of 5s) since x is extensive. Moreover, it can be a value which is not in AD but in I- AD. If the state of the computation consists of the definitions of all constraints, then at each step we get a strictly worse state (in terms of ~s ). The sequence of such compu­ tation states, until stability, has finite length, since by assumption I is finite and thus the value associated to each tuple of each constraint may be changed at most size( I) times. 0

An interesting special case of the above theorem oc­ curs when the chosen semiring has a finite domain A. In fact , in that case the hypotheses of the theorem hold with I = A. Another useful result occurs when + and x are AD-closed. In fact , in this case one can also com­ pute the time complexity of the k-consistency algorithm by just looking at the given problem. More precisely, if this same algorithm is O(nk) in the classical CSP case [Freuder , 1978; 1988; Mackworth and Freuder, 1985; Mackworth, 1977], then here it is O(size(AD) x nk) (in [Dubois et a/. , 1993] they reach the same conclusion for the fuzzy CSP case) .

No matter in which order the subsets W of k-1 vari­ ables, as well as the additional variables x, are chosen during the k-consistency algorithm, the result is always the same problem. However, this holds in general only if x is idempotent.

Theorem 13 Consider a SCSP problem P and two dif­ ferent applications of the k-consistency algorithm to P , producing respectively P' and P". Then P' = P" if x is idempotent. 0

5 Instances of the framework

We will now show how several known, and also new, frameworks for constraint solving may be seen as instances of the SCSP framework. More precisely, each of such frameworks corresponds to the choice of a spe­ cific constraint system (and thus of a semi ring). This means that we can immediately know whether one can inherit the properties of the general framework by just looking at the properties of the operations of the chosen semiring, and by referring to the theorems in the pre­ vious section. This is interesting for known constraint solving schemes, because it puts them into a single uni­ fying framework and it justifies in a formal way many informally taken choices, but it is especially significant for new schemes, for which one does not need to prove all the properties that it enjoys (or not) from scratch. Since we consider only finite domain constraint solving, in the following we will only specify the semiring that has to be chosen to obtain a particular instance of the SCSP framework.

5.1 Classical CSPs

A classical CSP problem [Montanari, 1974; Mackworth, 1988] is just a set of variables and constraints, where each constraint specifies the tuples that are allowed for the involved variables. Assuming the presence of a subset of distinguished variables, the solution of a CSP consists of a set of tuples which represent the assignments of the distinguished variables which can be extended to total assignments which satisfy all the constraints.

Since constraints in CSPs are crisp, we can model them via a semiring with only two values, say 1 and 0: allowed tuples will have the value 1, and not allowed ones the value 0. Moreover, in CSPs, constraint combination is achieved via a join operation among allowed tuple sets. This can be modelled here by taking as the multiplica­ tive operation the logical and (and interpreting 1 as true and 0 as false). Finally, to model the projection over the distinguished variables, as the k-tuples for which there exists a consistent extension to an n-tuple, it is enough to assume the additive operation to be the logical or. Therefore a CSP is just an SCSP where the c-semiring in the constraint system CS is Scsp = {{0, 1}, V, /\, 0, 1). The ordering ~s here reduces to 1 ~s 0. As predictable, all the properties related to k-consistency hold. In fact, 1\ is idempotent . Thus the results of Theorems 11 and 13 apply. Also, since the domain of the semiring is finite, the result of Theorem 12 applies as well.

5.2 Fuzzy CSPs

Fuzzy CSPs (FCSPs) [Rosenfeld et al., 1976; Dubois et al., 1993; Ruttkay, 1994; Schiex, 1992] extend the no­ tion of classical CSPs by allowing non-crisp constraints, that is, constraints which associate a preference level to each tuple of values. Such level is always between 0 and 1, where 1 represents the best value (that is, the tuple is allowed) and 0 the worst one (that is, the tu­ ple is not allowed). The solution of a fuzzy CSP is then defined as the set of tuples of values which have the maximal value. The value associated to n-tuple is obtained by minimizing the values of all its subtuples. Fuzzy CSPs are already a very significant extension of CSPs. In fact, they are able to model partial constraint satisfaction [Freuder and Wallace, 1992], so to get a solu­ tion even when the problem is overconstrained, and also prioritized constraints, that is, constraints with different levels of importance [Borning et al., 1989].

Fuzzy CSPs can be modelled in our framework by choosing the c-semiring SFcSP = {{x I x E [0, 1]}, max, min, 0, 1) . The ordering ~s here reduces to the ~ ordering on reals. The multiplicative opera­ tion of SFcSP (that is, min) is idempotent. Thus The­ orem 11 and 13 can be applied. Moreover, min is AD­ closed for any finite subset of [0,1]. Thus, by Theorem 12, any k-consistency algorithm terminates. Thus FC­ SPs, although providing a significant extension to classi­ cal CSPs, can exploit the same kind of local consistency algorithms. An implementation of arc-consistency, suit­ ably adapted to be used over fuzzy CSPs, is given in [Schiex, 1992] (although no formal properties of its be­ haviour are proved).

5.3 Probabilistic CSPs

Probabilistic CSPs (PCSPs) [Fargier and Lang, 1993] have been introduced to model those situations where each constraint c has a certain independent probability p(c) to be part of the given real problem. This allows one to reason also about problems which are only partially known. The probability of each constraint gives then, to each instantiation of all the variables, a probability that it is a solution of the real problem. This is done by associating to an n-tuple t the probability that all constraints that t violates are in the real problem. This is just the product of all1- p(c) for all c violated by t. Finally, the aim is to get those instantiations with the maximum probability.

The relationship between PCSPs and SCSPs is compli­ cated by the fact that PCSPs contain crisp constraints with probability levels, while SCSPs contain non-crisp constraints. That is, we associate values to tuples, and not to constraints. However, it is still possible to model PCSPs, by using a transformation which is similar to that proposed in [Dubois et al., 1993] to model priori­ tized constraints via soft constraints in the FCSP frame­ work. More precisely, we assign probabilities to tuples. instead of constraints: consider any constraint c with probability p(c), and lett be any tuple of values for the variables involved in c; then we set p(t) = 1 if t is al­ lowed by c, otherwise p(t) = 1- p(c). The reasons for such a choice are as follows: if a tuple is allowed by c and c is in the real problem, then t is allowed in the real problem; this happens with probability p(c); if in­ stead c is not in the real problem, then t is still alowed in the real problem, and this happens with probability 1-p( c). Thus t is allowed in the real problem with prob­ ability p(c) + 1 - p(c) = 1. Consider instead a tuple t which is not allowed by c. Then it will be allowed in the real problem only if c is not present; this happens with probability 1- p(c).

To give the appropriate value to ann-tuple t, given the values of all the smaller k-tuples, with k ~ n and which are subtuples oft (one for each constraint), we just per­ form the product of the value of such subtuples. By the way values have been assigned to tuples in constraints, this coincides with the product of all 1 - p(c) for all c violated by t. In fact, if a subtuple violates c, then by construction its value is 1 - p(c); if instead a subtuple satisfies c, then its value is 1. Since 1 is the unit element of x, we have that 1 x a = a for each a. Thus we get II(1- p(c)) for all c that t violates.

As a result, the c-semiring corresponding to the PCSP framework is Sprob =({xI x E [0, 1]}, max, x,O, 1}, and the associated ordering ~s here reduces to ~ over reals. Note that the fact that P' is a-consistent means that in P there exists an n-tuple which has probability a to be a solution of the real problem.

The multiplicative operation of Sprob (that is, x) is not idempotent . Thus neither Theorem 11 nor Theorem 13 can be applied. Also, x is not closed on any superset of any non-trivial finite subset of [0,1]. Thus Theorem 12 cannot be applied as well . Therefore, k-consistency algorithms do not make much sense in the PCSP frame­ work, since none of the usual desired properties hold. However, the fact that we are dealing with a c-semiring implies that, at least, we can apply Theorem 8: if a PCSP problem has a tuple with probability a to be a solution of the real problem, then any subproblem has a tuple with probability at least a to be a solution of a subproblem of the real problem. This can be fruitfully used when searching for the best solution in a branch­ and-bound search algorithm.

5.4 Weighted CSPs

While fuzzy CSPs associate a level of preference to each tuple in each constraint, in weighted CSPs (WCSPs) tu­ ples come with an associated cost. This allows one to model optimization problems where the goal is to min­ imize the total cost (time, space, number of resources, . .. ) of the proposed solution. Therefore, in WCSPs the cost function is defined by summing up the costs of all constra_ints (intended as the cost of the chosen tuple for each constraint). Thus the goal is to find the n-tuples (where n is the number of all the variables) which min­ imize the total sum of the costs of their subtuples (one for each constraint) .

According to this informal description of WCSPs, the associated c-semiring is SwcsP = (n+, min,+, +oo, 0), with ordering ~s which reduces here to~ over the reals. This means that a value is preferred to another one if it is smaller.

The multiplicative operation of Swcsp (that is, +) is not idempotent. Thus the k-consistency algorithms cannot be used (in general) in the WCSP framework, since none of the usual desired properties hold. However, again, the fact that we are dealing with a c-semiring implies that, at least, we can apply Theorem 8: if a WCSP problem has a best solution with cost a, then the best solution of any subproblem has a cost smaller than a . This can be convenient to know in a branch­ and-bound search algorithm.

5.5 Egalitarianism and Utilitarianism: FCSP + WCSP

The FCSP and the WCSP systems can be seen as two different approaches to give a meaning to the notion of optimization. The two models correspond in fact, re­ spectively, to two definitions of social welfare in utility theory [Moulin, 1988]: egalitarianism, which maximizes the minimal individual utility, and utilitarianism, which maximizes the sum of the individual utilities.

In this section we show how our framework allows also for the combination of these two approaches. In fact, we construct an instance of the SCSP framework where the two approaches coexist, and allow us to dis­ criminate among solutions which otherwise would result indistinguishable. More precisely, we first compute the solutions according to egalitarianism (that is, using a max-min computation as in FCSPs), and then discrim­ inate more among them via utilitarianism (that is, using a max- sum computation as in WCSPs). The result­ ing c-semiring is Sue = ( { (/, k) I /, k E [0, 1]}, max, min, (0, 0), {1, 0)), where max and min are defined as follows:

That is, the domain of the semiring contains pairs of values: the first element is used to reason via the max­ min approach, while the second one is used to further discriminate via the max-sum approach. More precisely, given two pairs, if the first elements of the pairs differ, then the max - min operations behave like a normal max- min, otherwise they behave like max-sum. This can be interpreted as the fact that, if the first element coincide, it means that the max-min criteria cannot dis­ criminate enough, and thus the max - sum criteria is used.

Since min is not idempotent, k-consistency algorithms cannot in general be used meaningfully in this instance of the framework.

A kind of constraint solving similar to that consid­ ered in this section is the one presented in [Fargier et a/., 1993], where Fuzzy CSPs are augmented with a finer way of selecting the preferred solution. More precisely, they employ a lexicographic ordering to improve the discrim­ inating power of FCSPs and avoid the so-called drawing effect. This approach can be rephrased in our frame­ work as well, yielding an instance where k-consistency algorithms can be applied.

6 Conclusions

In some of the instances considered, we have shown that the sufficent conditions for the application of k­ consistency algorithms do not hold. However, this does not mean that problems defined according to such schemes are not easily solvable in some special cases. In fact, one can show that our general framework is always compatible with the notion of dynamic programming, which, in the case of classical CSPs with a thick-tree structure, reduces to that of perfect relaxation [Monta­ nari and Rossi, 1991].

We plan to extend our framework in order to take into account several dimensions of "preference". In fact, in practice one could want, for example, to minimize cost and time, while maximizing the level of confidence and some notion of probability. Each of these desires could be cast in one c-semiring as shown in this paper, and then the combination of the four c-semirings (which is again a c-semiring) can be used to model the entire solving scheme. However, more attention has to be put now in the choice of the "best" solutions, since the presence of several dimensions obviously increases the probability of tuple incomparability.