João Moura-Pires

Henri Prade
email: henri.prade@irit.fr

Specifying fuzzy constraints interactions without using aggregation operators

A tuple of fuzzy constraints defined on a discrete satisfaction scale defines a lattice structure, called relaxation space, made of the tuples of level cuts of the fuzzy constraints, equipped with the partial order induced by the scale ordering. Then choosing a way of combining the fuzzy constraints has two joint effects: usually a completion of the ordering between tuples of levels, and possibly a simplification of the relaxation space (by eliminating subsumed tuples corresponding to the same level of global satisfaction). The paper investigates the possibility of specifying the ordering between tuples of level cuts constraints on a simplified relaxation space, without resorting to the use of explicit aggregation operations. The idea is to elicitate the preferences between the tuples of constraints representing various relaxations of the set of fuzzy constraints, directly from the user. How to express these preferences in a local manner is also discussed.

I. INTRODUCTION

Constraints in a satisfaction problem are sometimes flexible and can be conveniently modelled by fuzzy sets for expressing preferences between more or less acceptable choices.

Fuzzy constraint satisfaction problems (FCSP) are an extension of constraint satisfaction problems (CSP), where elastic constraints can replace crisp ones. In a FCSP a constraint is satisfied to a degree (rather than satisfied or not satisfied), and the acceptability of a potential solution w.r.t. an aggregated set of fuzzy constraints becomes a gradual notion [START_REF] Satoh | Formalizing soft constraint by interpretation ordering[END_REF][3] [START_REF] Dubois | Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty[END_REF]. FCSPs are naturally encountered in different areas such as structural design [START_REF] Guan | Extending constraint satisfaction problem solving in structural design[END_REF], or scheduling [START_REF] Fargier | Fuzzy scheduling: principles and experiments[END_REF] for instance.

In FCSPs, fuzzy constraints are usually aggregated by min operation. More recently, it has been shown [START_REF] Moura-Pires | Logical analysis of fuzzy constraint satisfaction problems[END_REF][13] that any monotonically increasing aggregation operators can be dealt with, in the framework of a level cut representation of the fuzzy constraints. This is handled by introducing more nodes (than with min) in the relaxation space made of relaxed problems constituted by sets of level cuts of the fuzzy constraints, when a finite scale is used.

In this paper, we pursue the idea briefly suggested in [START_REF] Moura-Pires | Fuzzy constraint problems with general aggregation operations under possibilistic logic form[END_REF] of taking advantage of the relaxation space [START_REF] Freuder | Partial constraint satisfaction[END_REF] for expressing how the levels of satisfaction of the fuzzy constraints interact in the global satisfaction level attached to a solution of a FCSP, without necessarily referring to the explicit use of some aggregation operator. Indeed this interaction, which may be compensatory or not, can be directly expressed by simple requirements which complete the ordering in the relaxation space. It may lead to simplify the relaxation space, which is exploited for finding a solution to the FCSP.

The paper is organized as follows. Section 2 recalls how a fuzzy constraint can be viewed as a weighted collection of crisp constraints. Section 3 defines the relaxation space associated with a set of fuzzy constraints. Section 4 discusses min ordering and its refinements, discrimin and leximin, on the relaxation space. Section 5 analyzes how aggregation modes between fuzzy constraints are associated with further specifications of the ordering on the relaxation space and possible simplifications of this space. Section 6 suggests how the ordering and the simplifications on the relaxation space can be directly specified through requirements, given by the user. Section 7 briefly addresses some computational issues.

II. FUZZY CONSTRAINTS

A fuzzy constraint C over a set of variables is represented by a fuzzy set on the Cartesian product of the domains of the variables involved. The membership degrees express preferences among solutions of the constraint by ranking the instantiations, which are more or less acceptable for the satisfaction of this flexible constraint C.

Fuzzy sets are defined on a finite linearly ordered valuation set, denoted L = {α 0 = 0 < α 1 < …< α L = 1}, where 0 and 1 denote the bottom and top elements. The order-reversing map of the scale is still denoted by 1 -(•).

A fuzzy constraint C can be viewed as a set of prioritized crisp constraints (see Fig. 1) [START_REF] Dubois | Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty[END_REF].

Let C j = (C) α j = {x | µ C (x) ≥ α j } be the α j -cut of C for j = 1, L. The priority attached to the crisp constraint C j is 1 -α j - 1 . C 1 ,
the support of C, is the crisp constraint with the highest priority, say 1 = 1α 0 ; C L , the core of C, has the lowest positive priority, 1α L -1 . A fuzzy constraint C expresses how C can be progressively relaxed. Letting µ C j (x) = 1 if x ∈ C j , and 0 otherwise, we have

µ C (x) = min j max (α j , µ C j (x)). (1)
A fuzzy constraint C is thus equivalent to the set of nested crisp constraints C 1 ⊇ C 2 ⊇ … ⊇ C L . C j = C j+1 is not forbidden. By convention, C 0 denotes the domain on which C is defined (C 0 ⊇ C 1 ). C 0 can be viewed as the most extreme relaxation of C, which is always satisfied.

1 -! 0 = 1.0 ! 1 = 0.2 ! 2 = 0.4 ! 3 = 0.6 ! 4 = 0.8 ! 5 = 1.0 C 5 C 2 ! 0 = 0.0 1 -! 3 = 0.4 1 -! 4 = 0.2 C 1 -! 1 = 0.8 C 3 C 1 1 -! 2 = 0.6 C 4
Fig. 1. α-cut view of a fuzzy constraint.

A fuzzy constraint C can be itself relaxed into C' by means of two elementary operations [START_REF] Moura-Pires | Fuzzy constraint problems with general aggregation operations under possibilistic logic form[END_REF]:

ρ-importance weighting:

µ C ' (x) = max (1 -ρ, µ C (x)).
(

) 2
It amounts to delete the most relaxed crisp constraints, from

C 1 to C k ,
where k is such that ρ = 1α k . In Fig. 1, for ρ = 0.6 (α k = 0.4 and thus k = 2) the two crisp constraints C 1 and C 2 are deleted.

θ-thresholding:

µ C ' (x) = θ → µ C (x), (3)

III. FUZZY CONSTRAINTS AS A RELAXATION SPACE

Let {C 1 , …, C K } be a set of fuzzy constraints with their associated crisp representatives C k j (with priority 1 α j-1 ). It defines a relaxation space made of a lattice structure between K-tuples of crisp constraints (C 1

j 1 , …, C k j k , …, C K j K
) equipped with a partial order < c (defined below). For the sake of simplicity the K-tuple (C 1

j 1 , …, C k j k , …, C K j K
,) will be represented by the K-tuple J = (j 1 , …, j k , …, j K ). Given two K-tuples J = (j 1 , …, j k , …, j K ) and I = (i 1 , …, i k , …, i K ), I is a relaxation of J, denoted by I ≤ c J, iff for all k from 1 to K, α i k ≤ α j k , and I is said to be a strict relaxation of J, denoted by I < c J, iff additionally there is a k such that α i k < α j k , and

C k i k ⊃ C k j k . When C k j k = C k i k
for all k from 1 to K, then I = c J, even if for some k, j k ≠ i k since C j = C j+1 is not forbidden.

Figure 2 shows the relaxation space associated with the set of three fuzzy constraints {A, B, C} with grades ranging on level scale L = {α 0 < α 1 < α 2 < α 3 }. This lattice structure reflects the tightness of the tuples of constraints. (A 3 , B 3 , C 3 ) made of the cores of the fuzzy constraints, is the hardest set of constraints, while (A 1 , B 1 , C 1 ), made of the supports, is the most relaxed set (where no constraint is completely forgotten).

It is worth stressing that it is not necessary that a relaxation space contain all possible K-tuples of level cuts of the fuzzy constraints. In fact, any subset of Ktuples of level cuts of the fuzzy constraints is a relaxation space. The number of nodes in the relaxation space is the result of the granularity required by the user. Actually, the relaxation space shown in Fig. 2 is a subset of the largest relaxation space associated to the set of fuzzy constraints {A, B, C}. Indeed, none of the K-tuples shown in Fig. 2 includes one of the trivial relaxations A 0 , B 0 or C 0 . This provides a first example of specification that can be obtained from the user. Is (s)he interested in relaxing constraints beyond the support, is it permitted to forget some constraints? If the answer is no, the domains C 1 0 , …, C K 0 are not considered in the relaxation space.

IV. FUZZY CSP AND ORDERINGS

A FCSP is defined by a set of decision variables X = {X 1 , …, X N }, a set of domains D = {D 1 , …, D N } where D i is the finite domain of X i , and a set of fuzzy constraints C = {C 1 , …, C K }where C k is a fuzzy set defined over the Cartesian product of the domains of the variables involved in C k . A membership value is associated to each tuple of values of the variables in C k .

A solution to a FCSP, denoted by x, is a vector of values in D 1 x … x D N . The level of satisfaction of the constraints reached by x, denoted by sat(x), is defined by [START_REF] Bellman | Decision-making in a fuzzy environment[END_REF]: sat(x) = min k µ C k(x). It is the satisfaction degree of the least satisfied constraint. A min optimal solution is any x* such that sat(x*) = max x min k µ C k (x).

Since min-optimal solutions to a FCSP may be numerous, two refinements of the ranking of solutions have been proposed, the discrimin and leximin orderings [START_REF] Dubois | Refinements of the maximin approach to decision making in a fuzzy environment[END_REF] [START_REF] Dubois | Beyond min aggregation in multicriteria decision: (Ordered) weighted min, discri-min, leximin[END_REF], where not only the least satisfied constraint is taken into account, but the other satisfaction levels are also compared.

Discrimin ordering looks for the lowest satisfied constraint among the constraints that are not equally satisfied. Namely, let Δ(x, y) be the subset of constraints that are not equally satisfied by x and y, i.e., the C k such that µ C k(x) ≠ µ C k(y). Discrimin is a partial ordering defined by x > disc y iff

min C k ∈ Δ(x, y) µ C k(x) > min C k ∈ Δ(x, y) µ C k(y).
Let S x be the fuzzy set of constraints satisfied by x which associates to each constraint

C k its satisfaction level µ C k(x). (S x ) α = {C k ∈ C | µ C k (x) ≥ α}, the α-cut of S x ,
is the set of constraints of C that are satisfied at least at level α. The discrimin ordering can be interpreted in terms of inclusion of α-cuts. It consists in comparing the α-cuts of S x and of S y , from the lowest level to the greatest one, until reaching a level α such that (S x ) α ≠ (S y ) α . At this level if a strict inclusion (S x ) α ⊃ (S y ) α holds, then x > disc y. Otherwise, the solutions are incomparable.

The leximin ordering (e.g., [START_REF] Dubois | Refinements of the maximin approach to decision making in a fuzzy environment[END_REF]) is a refinement of min and discrimin orders. Let s x be an increasingly arranged vector of the satisfaction degrees in S x , i.e.,

s x = (s [1] , …, s [K] ), such that s [i] ≤ s [i+1] where s [i] = µ C [i]
(x) (the constraints are renumbered). Then, the leximin ordering is defined by:

x > leximin y ⇔ ∃i ∀ j < i s x [j] = s y [j] and s x [i] > s y [i] .
This corresponds to a lexicographic comparison of the vectors s x and s y . A solution x is leximin preferred to a solution y, if there is a threshold α such that for all β < α, the number of constraints satisfied by x at level at least β is equal to the number of constraints satisfied by y, and x satisfies more constraints than y at level α.

While these orderings are originally defined over the set of FCSP solutions they are equivalently defined in terms of the K-tuples on the relaxation space. The leximin ordering provides a refinement of the relaxation order < c . For instance, in Fig. 2 These two refined orderings take place on the same relaxation structure. The relaxation space associated with the min ordering is pictured in Figure 3. Note that it is a very simplified version of the one defined by < c in Fig. 2. It appears that two phenomena are at work: suppressing incomparabilities on the one hand, and simplifying the relaxation space on the other hand.

Clearly, there are many ways to get rid of incomparabilities (in agreement with < c ). Besides, it may be desirable to decouple the simplification of the relaxation space and the suppression of incomparabilities (which are mixed together by the use of the min operation).

It has been shown that the result of any monotonic combination of fuzzy constraints can be encoded as a set of prioritized crisp constraints, which can be syntactically obtained from the initial ones [14][13].

This includes noticeable particular cases such as the product, or the average of fuzzy constraints. This also allows for the use of different operations for combining more than two constraints (e.g., a weighed average of A with the min combination of B and C), thus modeling different types of interactions between constraints such as tradeoffs or pure conjunctive aggregations. However, such an approach has some limitations although it can accommodate any practical aggregation mode. First, as in the case of min, the simplification of the relaxation space and the suppression of incomparabilities cannot be controlled separately.

Second, it is not always easy to capture all the possible aggregation modes by means of a set of combination operations. In the following, a more flexible way of specifying the interactions between fuzzy constraints is proposed.

V. IMPLICIT AGGREGATION IN THE RELAXATION SPACE

In this section we consider the case of the interaction between two fuzzy constraints A and B defined using the same scale L = {α 0 = 0 < α 1 < …< α L = 1}. We assume that if some thresholding or importance weighting takes place, the result of these elementary modifications is already integrated in the constraint. As already said the relaxation space does not specify all the preferences between pairs of crisp constraints (A i , B j ) and (A k , B l ). If A i (resp. B j ) is satisfied, at least the satisfaction level α i (resp α j ) is reached. What < c reflects is a partial Pareto order on the pairs of valuations (α i , α j ), namely (α 0 , α 0 ) < c (α 0 , α 1 ) < c (α 1 , α 1 ) < c … < c (α L-1 , α L ) < c (α L , α L ). For notational simplicity we shall write (0, 0) < (0, 1), etc. Since the constraints are assumed to play symmetrical roles, pairs (i, j) and (j, i) are equivalent and by convention when we write (i, j) it is assumed that i ≤ j. More generally, we have (i, j) < (k, l) as soon as i ≤ k and j < l, or i < k and j ≤ l. What remains to specify is the ordering between pairs (i, j) and (k, l) such that i > k and j < l.

The situation is pictured in Fig. 4, for two constraints, and L = {α 0 = 0 < α 1 < α 2 < α 3 = 1}. The orderings remaining to specify are pictured in dotted lines. Such a refinement of < c will be denoted by < p (preference ordering). For instance, from Fig. 4, (1, 3) < c (2, 3) and (2, 2) < c (2, 3), while (2, 2) is < c -incomparable to [START_REF] Bellman | Decision-making in a fuzzy environment[END_REF][START_REF] Bowen | Fuzzy semantics and fuzzy constraint networks[END_REF] and to (0, 3). Moreover, the specifications should obey the transitivity requirement, for instance the user cannot enforce both (1, 3) < p (2, 2) and (2, 2) < p (0, 3). Additionally the user may consider some pairs as equally good. For instance, (0, 2) = p (1, 2), or even (2, 3) = p [START_REF] Benferhat | Toward a possibilistic logic handling of preferences[END_REF][START_REF] Benferhat | Toward a possibilistic logic handling of preferences[END_REF]. Such equalities can eventually simplify the relaxation space as we will explain later.

Figure 5 exhibits the leximin linearization of < c . Note that it corresponds to the following requirements: a) (2, 2) > p (1, 3) (which implies that (2, 2) > p (0, 3)); b) (1, 2) > p (0, 3) (which could be deduced from the previous requirement assuming similar preferences along the satisfaction scale); c) (1, 1) > p (0, 3) (which implies that (1, 1) > p (0, 2)). Figure 6 shows a different linearization, which can be interpreted as an average refined by the min. The necessary requirements to reach this linearization are similar to the previous ones except for the requirement c) replaced by c'): (0, 3) > p (1, 1) and the additional requirement, d) (1, 1) > p (0, 2). Figure 7 shows a possible combination mode, which is more difficult to interpret in terms of known aggregation operators. However, it can be specified using simple requirements as in the previous cases: a) (2, 2) > p (1, 3) (which implies that (2, 2) > p (0, 3)); b) (0, 3) > p (1, 2) (which implies that (0, 3) > p (1, 1)); c) (0, 2) > p (1, 1) (which could be deduced from the previous requirements assuming similar preferences along the satisfaction scale). It is worth stressing that in the three previous examples < p has no ties and the number of global satisfaction levels uses a scale with 10 elements (from (0, 0) to (3, 3)). There are 12 different linearizations of < c without ties for two constraints and L = 3, and the relaxation space is always the same, differing only on the preferred nodes.

If we relax the requirement of strict preference specification and allows ties then other combinations would be obtained. Note that these other combination schemes take place on other relaxation spaces, which are simplified versions of the initial one. Whenever the user defines equalities between < c -comparable tuples the relaxation space becomes more simplified, i.e., some relaxation graph nodes are removed .

Figure 8 shows the relaxation space corresponding to the average aggregation. Here, the average is not refined by the min (or by any other way) and ties are exhibited. Suppose that (A 1 , B 3 ), (A 2 , B 2 ) and (A 3 , B 1 ) are maximally consistent. While in the case of Fig. 6 (A 2 , B 2 ) would be the preferred one, here any of those three pairs are considered equally satisfactory. Fig. 8. Average. Figure 9 exhibits a complete order, which can be viewed as an aggregation by the product. Note that in this case the number of relaxation space nodes is smaller than in the previous examples. In fact due to the ties from (0, 0) to (0, 3) the relaxation space is simplified by keeping only the more relaxed pair(s) from the pairs within a tie. It is worth stressing that simplified relaxation spaces can also be specified without the explicit use of aggregation operators. Figure 10 shows a relaxation space which is specified through the following requirements: a) (1, 3) > p (2, 2); b) it is not acceptable to relax any constraints beyond its support. Fig. 10. A simplified specified relaxation space.

VI. SPECIFICATION OF CONSTRAINT INTERACTIONS

The previous section has shown, in the particular case of the combination of two fuzzy constraints, how the refinements of the ordering on the relaxation space and the simplification of the space are reflecting aggregation modes. Indeed, we can directly take advantage at the computational level of the specification of any refinement of the ordering < c on the relaxation space, or of the simplification of this space. Simplifying the relaxation space enforces that tuples of level cut constraints (constituting crisp representatives of the original fuzzy constraint satisfaction problem) have an equal level of satisfaction from the user point of view, and amounts to eliminate subsumed tuples (just keeping the easiest set of constraints). It may be interesting to start with a rather simplified relaxation space, and depending on what set of constraints in this space reveals to be feasible or infeasible, to later specify a partial refinement of the ordering leading to a local unfolding of the relaxation space, once a maximal consistent satisfaction problem has been identified.

Let us now suggest how requirements on the ordering between the tuples of crisp level cut constraints can be expressed. While it is easy to express the relative position in the ordering of e.g., (0,2) with respect to (1,1), it may be much more tedious to express the direct assessment of orderings between K-tuples with K larger than 2 or 3. What might be more natural is to reconstruct the ordering from partial comparisons of levels of satisfaction of small subsets of constraints. This will also enable the expression of tradeoffs between some constraints, while others are combined in a pure conjunctive style for instance. All such requirements contribute to a partial specification of an ordering complementing < c . The consistency of requirements can be checked. Requirements and simplifications can be expressed progressively as mentioned at the beginning of this section. Note also that requirements provided through examples might be generalized, i.e., extrapolated into generic requirements. For instance if we state that (…, 0, …, 2, …) > p (…, 1, …, 1, …), it might be extrapolated into (…,0 + x, …, 2 + x, …) > p (…, 1 + x, …, 1 + x, …).

VII. CONCLUSIONS: COMPUTATIONAL ISSUES

This paper advocates the idea that preferences between potential solutions of a set of fuzzy constraints can be expressed through examples based on generic requirements, which can be directly exploited on the relaxation space, rather than through the use of explicit aggregation operations. This should enables a more flexible and local representation of preferences, as also recently discussed in [START_REF] Benferhat | Toward a possibilistic logic handling of preferences[END_REF] in a multiple criteria aggregation setting.

The control of the relaxation space through the requirements, which are entered by the user, has also some computational interest. Given a relaxation space the user intends to find one or all < c -maximal consistent K-tuples in the relaxation space. Note that all maximal consistent problems are < c -incomparable. Once a refinement < p is provided the task is then to find one or all < p -maximal consistent problems, which are generally less than the number of < c -maximals. In general, the determination of consistency of a set of crisp constraints is a NP-complete problem [START_REF] Mackworth | Consistency in networks of relations[END_REF]. Solving a min-FCSP, whose relaxation space is pictured in Fig. 3, amounts to solve, in the worst case, L sets of crisp constraints, L being the number of positive levels of the satisfaction scale. Min-optimal solutions for FCSP can be obtained by solving a logarithmic number of CSP's [START_REF] Cooper | Computational complexity of fuzzy constraint satisfaction[END_REF].

The flexibility which is introduced in min-FCSPs has a computational price that is controllable by the user, through the number of satisfaction levels in the satisfaction scale. In other words, a greater granularity of the relaxation space provides a greater flexibility at the expense of some computational price.

The idea of a tradeoff between granularity and computational price can be considered for any relaxation space. The hardness of finding one < p -best maximal consistent K-tuple in the relaxation space grows with the number of nodes in the relaxation space.

As said before, ties in < p can produce simplified versions of the relaxation spaces. Starting with a preference relation < p with many ties will provide a small relaxation space, for which a solution can be found. Successive redefinitions of < p breaking ties will locally unfold the relaxation space and will provide solution refinements. Another way to produce simplified relaxation spaces is by θ-thresholding all the fuzzy constraints. Similar ideas for solving Valued-CSP by successive approximations can be found in [START_REF] Degivry | Optimum anytime bounding for constraint optimization problems[END_REF].

  where a → b is Gödel implication (a → b = 1 if a ≤ b, a → b = b if a > b). It amounts to erase the hardest crisp representatives of C, from C L to C m , where m is such that θ = α m-1 . In Fig. 1, for θ = 0.8 the crisp constraint C 5 is deleted.

Figure 2 .

 2 Figure 2. The relaxation space associated with the set of fuzzy constraints {A, B, C}.Actually, the relaxation space shown in Fig.2is a subset of the largest relaxation space associated to the set of fuzzy constraints {A, B, C}. Indeed, none of the K-tuples shown in Fig.2includes one of the trivial relaxations A 0 , B 0 or C 0 . This provides a first example of specification that can be obtained from the user. Is (s)he interested in relaxing constraints beyond the support, is it permitted to forget some constraints? If the answer is no, the domains C 1 0 , …, C K 0 are not considered in the relaxation space.

  , (A 3 , B 3 , C 2 ) is < cincomparable to {A 2 , B 2 , C 3 } while {A 3 , B 3 , C 2 } >leximin {A 2 , B 2 , C 3 }. It also induces ties: {A 2 , B 2 , C 3 }, {A 2 , B 3 , C 2 }, {A 3 , B 2 , C 2 } are leximin equivalent.With the leximin refinement all the tuples of constraints become comparable. This is not the case with discrimin, which offers a less strong refinement. For instance {A 3 , B 3 , C 2 } and {A 2 , B 2 , C 3 } remain discrimin-incomparable, while {A 2 , B 1 , C 3 } is discrimin preferred to {A 3 , B 1 , C 1 } although they are < c -incomparable.

Fig. 3 .

 3 Fig. 3. Relaxation space of min-FCSP.

Fig. 4 .

 4 Fig. 4. Refinements of Pareto ordering .

Fig. 5 .

 5 Fig. 5. Leximin.

Fig. 6 .

 6 Fig. 6. Average refined by min.

Fig. 7 .

 7 Fig. 7. A non classical aggregation.

Fig. 9 .

 9 Fig. 9. Product.

  Generally speaking, a (partial) ordering, refining < c , between K-tuples (α 1 , …, α K ), where α k ∈ L, can be specified through different types of requirements:-(partial) examples of preferences such as, e.g., (α 1 ,…, α k-1 , 0, …, α m-1 , 2, …, α K ) is not preferred to (α 1 , …, α k-1 , 1, …, α m-1 , 1, …, α K )for any pair k ≠ m; -preferences between reduced tuples of global satisfaction levels of subsets of constraints, assuming that each subset is aggregated using some standard combination operation; -generic preferences expressing, for instance, statements about the relative importance of criteria, e.g., "k is as important m":(…., α k , …, α m , …) ≅ p (…., α m , …, α k , …) for all α k and α m , the other α i being identical in both tuples; "k is more important than m" (….,α k , …, α m , …) > p (…., α m , …, α k , …) for α k > α m .generic statements expressing preferential independence between sets of criteria I and I c , i.e., (α I , α I c) > p (β I , α I c) ⇔ (α I , β I c) > p (β I , β I c) where I is a subset of {1, …, K} and I c its complement and α I stands for the vector of the α i 's where i ∈ I.