Christophe Lecoutre
email: lecoutre@cril.fr

Olivier Roussel
email: roussel@cril.fr

Djamel E Dehani
email: dehani@cril.fr

WCSP Integration of Soft Neighborhood Substitutability

WCSP is an optimization problem for which many forms of soft local (arc) consistencies have been proposed such as, for example, existential directional arc consistency (EDAC) and virtual arc consistency (VAC). In this paper, we adopt a different perspective by revisiting the well-known property of (soft) substitutability. First, we provide a clear picture of the relationships existing between soft neighborhood substitutability (SNS) and a tractable property called pcost which allows us to compare the cost of two values (through the use of so-called cost pairs). We prove that under certain assumptions, pcost is equivalent to SNS but weaker than SNS in the general case since we show that SNS is coNP-hard. We also show that SNS preserves the property VAC but not the property EDAC. Finally, we introduce an algorithm to enforce pcost that benefits from several optimizations (early breaks, residues, timestamping). The practical interest of maintaining pcost together with AC*, FDAC or EDAC, during search. is shown on various series of WCSP instances.

Introduction

The Valued Constraint Satisfaction Problem (VCSP) [START_REF] Schiex | Valued constraint satisfaction problems: Hard and easy problems[END_REF] is a general optimization framework used to handle soft constraints, which has been successfully applied to many applications in Artificial Intelligence and Operations Research. A problem instance is modeled in this framework by means of a set of variables and a set of cost functions defined over a valuation structure. Each cost function determines a violation degree for each possible instantiation of a subset of variables. These degrees (or costs) can then be combined using the operator ⊕ of the valuation structure in order to obtain the overall cost of any complete instantiation. One can broadly classify the different VCSP instantiations according to the properties of the operator ⊕: those where ⊕ is idempotent (e.g., min) and those where ⊕ is monotonic (e.g., +).

Interchangeability is a general property of constraint networks introduced in [START_REF] Freuder | Eliminating interchangeable values in constraint satisfaction problems[END_REF]. Two values a and b for a variable x are interchangeable if for every solution I where x is assigned b, I x=a is also a solution, where I x=a means I with x set to a. Full interchangeability has been refined into several weaker forms such as neighborhood interchangeability, k-interchangeability, partial interchangeability, relational interchangeability and substitutability. Interchangeability and substitutability have been used in many contexts; see e.g. [START_REF] Haselbock | Exploiting interchangeabilities in constraint satisfaction problems[END_REF][START_REF] Choueiry | Abstraction by interchangeability in resource allocation[END_REF][START_REF] Cooper | Fundamental properties of neighbourhood substitution in constraint satisfaction problems[END_REF][START_REF] Lal | Neighborhood interchangeability and dynamic bundling for non-binary finite CSPs[END_REF]. A partial taxonomy of these two properties can be found in [START_REF] Karakashian | A partial taxonomy of substitutability and interchangeability[END_REF].

A generalization of interchangeability and substitutability for soft constraints has been given in [START_REF] Bistarelli | Interchangeability in soft CSPs[END_REF]. For example, a value a for a variable x is soft substitutable for another value b in the domain of x if for every complete instantiation I involving (x, a), the cost of I is less than or equal to the cost of I x=b . Observation of this property can be used to delete value b for x whereas preserving optimality. Identifying full substitutability is not tractable, but is is known [START_REF] Bistarelli | Interchangeability in soft CSPs[END_REF] that neighborhood substitutability, a limited form of substitutability where only constraints involving a given variable are considered, can be computed in polynomial time when ⊕ is idempotent (provided that the arity of constraints be bounded). However, when ⊕ is monotonic, as it is the case for the VCSP specialization called WCSP (Weighted CSP), there is no clear picture although dominance rules related to soft neighborhood substitutability have been used [START_REF] Koster | Frequency assignment: Models and Algorithms[END_REF][START_REF] De Givry | Singleton consistency and dominance for weighted CSP[END_REF].

In this paper, we focus on soft neighborhood substitutability (SNS) for WCSP. We introduce a property based on cost pairs, called pcost, that allows us to identify efficiently soft substitutable values. We prove that under certain assumptions, pcost is equivalent to SNS. However, in the general case, and especially when the WCSP forbidden cost k is not ∞, pcost is weaker than SNS. Actually, identifying a soft neighborhood value is coNP-hard. We also study the relationships between SNS and known soft arc consistency properties such as Existential Directional Arc Consistency (EDAC) [START_REF] De Givry | Existential arc consistency: Getting closer to full arc consistency in weighted CSPs[END_REF] and Virtual Arc Consistency (VAC) [START_REF] Cooper | Virtual arc consistency for weighted CSP[END_REF]. We prove that SNS preserves VAC but not necessarily EDAC. Finally, we develop a pcost algorithm that benefits from a very moderate best-case time complexity, and we show experimentally that it can be successfully combined with EDAC during search.

Technical Background

A constraint network (CN) P is a pair (X , C ) where X is a finite set of n variables, also denoted by vars(P ), and C is a finite set of e constraints. Each variable x has a (current) domain, denoted by dom(x), which is the finite set of values that can be (currently) assigned to x; the initial domain of x is denoted by dom init (x). The largest domain size will be denoted by d. Each constraint c S involves an ordered set S of variables, called the scope of c S , and represents a relation capturing the set of tuples allowed for the variables in S. A unary (resp., binary) constraint involves 1 (resp., 2) variable(s), and a non-binary one strictly more than 2 variables. An instantiation I of a set X = {x 1 , . . . , x p } of p variables is a set {(x 1 , a 1 ), . . ., (x p , a p )} such that ∀i ∈ 1..p, a i ∈ dom init (x i ); X is denoted by vars(I) and each a i is denoted by

I[x i ]. An instantiation I on a CN P is an instantiation of a set X ⊆ vars(P ) ; it is complete if vars(I) = vars(P ). I is valid on P iff ∀(x, a) ∈ I, a ∈ dom(x). I covers a constraint c S iff S ⊆ vars(I). I satisfies a constraint c S with S = {x 1 , . . . , x r } iff (i) I covers c S and (ii) the tuple (I[x 1 ], . . . , I[x r ]) ∈ c S .
An instantiation I on a CN P is locally consistent iff (i) I is valid on P and (ii) every constraint of P covered by I is satisfied by I. A solution of P is a complete locally consistent instantiation on P ; sols(P ) denotes the set of solutions of P .

A weighted constraint network (WCN) P is a triplet (X , W , k) where X is a finite set of n variables, as for CSP, W is a finite set of e weighted constraints, also denoted by cons(P ), and k > 0 is a natural integer or ∞. Each weighted constraint w S ∈ W involves an ordered set S of variables (its scope) and is defined as a cost function from l(S) to {0, . . . , k} where l(S) is the set of possible instantiations of S. When a constraint w S assigns the cost k to an instantiation of S, it means that w S forbids this instantiation. Otherwise, it is permitted with the corresponding cost (0 is completely satisfactory). Costs are combined with the specific operators ⊕ defined as: ∀a, b ∈ {0, . . . , k}, a ⊕ b = min(k, a + b).

For any instantiation I and any set of variables X, let I ↓X = {(x, a) | (x, a) ∈ I ∧ x ∈ X} be the projection of I on X. We denote by I x=a the instantiation I ↓X\{x} ∪ {(x, a)}, which is the instantiation obtained from I either by replacing the value assigned to x in I by a, or by extending I with (x, a). The set of neighbor constraints of x is denoted by Γ (x) = {c S ∈ cons(P ) | x ∈ S}. When Γ (x) does not contain two constraints sharing at least two variables, we say that Γ (x) is separable. If c S is a (weighted) constraint and I is an instantiation of a set X ⊇ S, then c S (I) will be considered to be equal to c S (I ↓S ) (in other words, projections will be implicit). If C is a set of constraints, then vars(C) = ∪ c S S is the set of variables involved in C; if I is an instantiation such that vars(C) ⊆ vars(I), then cost C (I) = ⊕ c S ∈C c S (I) is the cost of I obtained by considering all constraints in C. For a WCN P and a complete instantiation I of P , the cost of I is then cost cons(P ) (I) which will be simplified into cost(I). The usual (NP-hard) task of Weighted Constraint Satisfaction Problem (WCSP) is, for a given WCN, to find a complete instantiation with a minimal cost. CSP can be seen as specialization of WCSP (when only costs 0 and k are used) and WCSP [START_REF] Larrosa | Solving weighted CSP by maintaining arc consistency[END_REF] can be seen as a specialization of the generic framework of valued/semiring-based constraints [START_REF] Bistarelli | Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison[END_REF].

Many forms of soft arc consistency have been proposed during the last decade. We briefly introduce them in the context of binary WCNs. Without any loss of generality, the existence of a zero-arity constraint c ∅ (a constant) as well as the presence of a unary constraint c x for every variable x is assumed. A variable x is node-consistent (NC*) iff ∀a ∈ dom(x), c ∅ ⊕ c x (a) < k and ∃b ∈ dom(x) | c x (b) = 0. A variable x is arc-consistent (AC*) iff x is NC* and ∀a ∈ dom(x), ∀c xy ∈ Γ (x), ∃b ∈ dom(y) | c xy (a, b) = 0 (b is called a simple support of a). A WCN is AC* iff each of its variable is AC* [START_REF] Larrosa | Node and arc consistency in weighted CSP[END_REF][START_REF] Larrosa | Solving weighted CSP by maintaining arc consistency[END_REF]. A WCN is full directional arc-consistent (FDAC) [START_REF] Cooper | Reduction operations in fuzzy or valued constraint satisfaction[END_REF] with respect to an order < on the variables if it is AC* and

∀c xy | x < y, ∀a ∈ dom(x), ∃b ∈ dom(y) | c xy (a, b) = c y (b) = 0 (b is called a full support of a). A WCN is existential arc- consistent (EAC) [9] if it is NC* and ∀x ∈ vars(P ), ∃a ∈ dom(x) | c x (a) = 0 ∧ ∀c xy ∈ Γ (x), ∃b ∈ dom(y) | c xy (a, b) = c y (b) = 0 (a is called the existential support of x).
A WCN is existential directional arc-consistent (EDAC) with respect to an order < on the variables if it is EAC and FDAC with respect to <. For any WCN P , we can derive an associated CN Bool(P ) by considering constraint relations that only allow tuples with cost zero in P . P is virtual arc-consistent (VAC) [START_REF] Cooper | Virtual arc consistency for weighted CSP[END_REF] if the arc consistency closure of Bool(P ) does not involve a variable with an empty domain, denoted by AC(Bool(P )) = ⊥. A WCN is optimal soft arc-consistent (OSAC) if no SAC transformation (see [START_REF] Cooper | Soft arc consistency revisited[END_REF]) applied to it increases c ∅ . OSAC is stronger than VAC, which itself is stronger than EDAC, when comparing the values of c ∅ . We shall note φ(P ) the enforcement of property φ (e.g., AC, EDAC, . . .) on the (W)CN P .

In this section, we introduce soft neighborhood substitutability. Initially, interchangeability and substitutability are properties that have been introduced for CSP [START_REF] Freuder | Eliminating interchangeable values in constraint satisfaction problems[END_REF]. From now on, we consider given a (W)CN P . (x,c) are interchangeable and both are substitutable for (x, b). When only a single solution is sought, we can remove a value that is interchangeable with another value (or for which a value is substitutable). Such removal preserves the satisfiability of the problem instance but not the full set of solutions.

From now on, we shall focus on substitutability that has been generalized [START_REF] Bistarelli | Interchangeability in soft CSPs[END_REF] for WCSP as follows:

Definition 2. Let x ∈ vars(P ) and {a, b} ⊆ dom(x), (x, a) is soft substitutable for (x, b) on P iff for every complete instantiation I of P , cost(I x=a ) ≤ cost(I x=b ).
When (x, a) is soft substitutable for (x, b), b can be removed from dom(x) without changing the cost of the optimal solution(s) of P . Indeed, possible solutions of P with (x, b) are lost, but it is guaranteed that solutions with (x, a) are at least as good.

Because identifying substitutable values involves handling complete instantiations, this is subject to combinatorial explosion. However, there is a form of local substitutability, called neighborhood substitutability [START_REF] Freuder | Eliminating interchangeable values in constraint satisfaction problems[END_REF][START_REF] Bistarelli | Interchangeability in soft CSPs[END_REF], that may be helpful. Definition 3. Let x ∈ vars(P ) and {a, b} ⊆ dom(x), (x, a) is soft neighborhood substitutable for (x, b) on P iff for every complete instantiation

I of P , cost Γ (x) (I x=a ) ≤ cost Γ (x) (I x=b ).
We shall say that (x, b) is SNS-eliminable (on P ) when there exists a value (x, a) such that (x, a) is soft neighborhood substitutable for (x, b). It is rather immediate that soft neighborhood substitutability implies soft (full) substitutability (but the reverse is not true). Interestingly enough, soft (neighborhood) substitutability allows compensation between constraint costs. Such compensation is made possible by the presence of all intermediate costs in the valuation structure, that is to say, the costs different from 0 and k. A simple illustration is given by Figure 1. There are two binary constraints c xy and c xz and three trivial unary constraints (all unary costs are equal to 0). Binary costs are depicted as labeled edges, and zero costs are not shown. Note that (x, a) is soft substitutable for (x, b).

Definition 3 requires to consider each instantiation of vars(Γ (x)), which has a high computational cost. Considering each constraint individually allows to reduce this cost, but in this case, it is highly desirable to be able to identify cost compensations between constraints. One straightforward way to do this is to compute a sum of minimal cost differences over all constraints, as mentioned in [START_REF] Koster | Frequency assignment: Models and Algorithms[END_REF][START_REF] De Givry | Singleton consistency and dominance for weighted CSP[END_REF]. Unfortunately, these differences of costs introduce subtle problems when k = ∞. This is illustrated as follows:

Example 1. Consider the two families of constraints C i = {c i | i ∈ 1..n} and C ′ i = {c ′ i | i ∈ 1.
.n ′ } defined as:

x y i c i a c 0 b c 1 x z i c ′ i a d 1 b d 0 When n = k and n ′ = k + 1, (x, a
) and (x, b) are interchangeable because both are forbidden (i.e., have maximum cost k). However,

∀c i ∈ C i , cost ci (I x=b )-cost ci (I x=a ) = 1 and ∀c ′ i ∈ C ′ i , cost c ′ i (I x=b ) -cost c ′ i (I x=a ) = -1.
In the summation over the constraints in Γ (x) = C i ∪ C ′ i , the resulting value is -1 which would indicate that b has globally a lower cost than a, which is false since both a and b have a cost of k. To identify correctly this case of substitution when k = ∞, it is necessary to use a non commutative operator, which prevents us from using the usual -.

Computing Soft Substitutability

We now focus on soft neighborhood substitutability, and more precisely on the complexity of identifying SNS-eliminable values. We start with some related work. For the general framework VCSP, efficient algorithms for computing neighborhood substitutability exist [START_REF] Bistarelli | Interchangeability in soft CSPs[END_REF] when the aggregation operator of the VCSP valuation structure is idempotent. For the framework FCSP (Fuzzy CSP), the notion of fuzzy neighborhood substitutability is proposed in [START_REF] Cooper | Reduction operations in fuzzy or valued constraint satisfaction[END_REF]: it is shown that fuzzy neighborhood substitutable values can be identified efficiently when the aggregation operator of the FCSP valuation structure is strictly monotonic or when it is the operator max. More recently, the possibility of computing dominance forms weaker than soft neighborhood substitutability has been proposed in [START_REF] Koster | Frequency assignment: Models and Algorithms[END_REF]. However, no qualitative study was led. This is what we propose now for WCSP.

First, we introduce cost pairs as our basic computation mechanism (this is related to what has been proposed in [START_REF] Cooper | Reduction operations in fuzzy or valued constraint satisfaction[END_REF] for FCSP). Indeed, one way to circumvent the aforementioned problems with subtraction is to use only addition defined on pairs of costs. This method is analogous to the construction of integers as equivalence classes of ordered pairs of natural numbers where a pair (β, α) represents the integer βα. We define + (addition) on pairs of costs by (β, α) + (β ′ , α ′ ) = (β + β ′ , α + α ′ ) (this is the regular + and not ⊕) and the comparison of a pair of costs with zero by (β, α) ≥ 0 ⇔ β ≥ α. Pairs are ordered by the relation ≤ defined as

(β, α) ≤ (β ′ , α ′ ) ⇔ β -α < β ′ -α ′ ∨ (β -α = β ′ -α ′ ∧ α < α ′ ).
In a sense, the pair (β, α) conveys the difference βα but also the information min(β, α) which is lost when a simple subtraction is used. Computing cost pairs on each constraint separately is sufficient for identifying certain soft neighborhood substitutable values: it suffices to reason from (sum) minimum differences of costs. The converse of Proposition 1 is not true in the general case. One first case where it is false is when the scope of non-binary constraints intersect on more than one variable (non separable neighborhood). In this situation, constraints cannot be considered individually. So a first condition for the converse of Proposition 1 to hold it that Γ (x) be separable (which is the case of binary normalized networks).

Another case where the converse of Proposition 1 is false is when k = ∞. Considering the WCN of example 1 with n = k and n ′ = k + 1, we can observe that pcost(x : a → b) = (n, n ′ ) = (k, k + 1) ≥ 0. However, both (x, a) and (x, b) imply cost k and therefore (x, a) is substitutable for (x, b) (and conversely). On this example, it might seem a good idea to use ⊕ instead of + in the definition of the addition of pairs. However, Example 3 shows that this would lead to the incorrect identification of substitutable values.

Example 3. Consider the unary constraint c x and the family of binary constraints

C i = {c i | i ∈ 1.
.n} defined by:

x y i c i a a 2 a b 0 b a 1 b b 0 x c x a 1 b 0
Clearly, (x, a) is not substitutable for (x, b). With the sum of pairs defined with + and n = k, pcost(x, a → b) = (n, 2n + 1) ≥ 0. If the sum of pairs was defined with ⊕, we would obtain (k, k) ≥ 0. Note that even if (k, k) was interpreted as kk = 0 or as kk = k (absorbing element), the problem would remain: in both cases, we would have (k, k) ≥ 0.

Interestingly, there are some situations where, even when k = ∞, using cost pairs allows us to identify exactly neighborhood substitutable values. When pcost(x : a → b) = (β, α) with α ≥ k, deciding if (x, a) is soft neighborhood substitutable for (x, b) is much harder. Indeed, this problem is co-NP hard.

To prove this, we introduce the Multiple-choice Double Cost Problem (MCDP). We show that MCDP is NP-complete and exhibit a polynomial reduction of the MCDP problem to soft neighborhood substitutability.

Multiple-choice Double Cost Problem (MDCP)

Given m sets E 1 , E 2 , . . ., E m of objects such that each object o j ∈ E i has a cost value r ij ∈ Z + as well as a secondary cost value s ij ∈ Z + . Given a maximal cost C ∈ Z + , the MDCP problem consists in deciding if it is possible to choose one object from each set such that the sum of the costs of these selected objects does exceed C and does not exceed the sum of the secondary costs as well. This problem may be formulated as:

m i=1 j∈Ei r ij x ij ≤ C, m i=1 j∈Ei r ij x ij ≤ m i=1 j∈Ei s ij x ij , j∈Ei x ij = 1, i = 1, . . . , m, x ij ∈ {0, 1}, i = 1, . . . , m, j ∈ E i .

Proposition 3. The multiple-choice double cost problem is NP-complete.

Proof. Membership to NP is immediate. For NP-hardness, we reduce Multiple-choice Knapsack problem (MCKP known to be NP-hard [START_REF] Martello | Knapsack Problems: Algorithms and Computer Implementations[END_REF]) to Multiple-choice Double Cost Problem. For MCKP, we have also m sets, and each object is given a profit p ij ∈ Z + as well as a weight w ij ∈ Z + . Given a minimal profit P ∈ Z + and a maximal weight W ∈ Z + , the MCKP decision problem is formulated as:

m i=1 j∈Ei w ij x ij ≤ W , m i=1 j∈Ei p ij x ij ≥ P , j∈Ei x ij = 1, i = 1, . . . , m, x ij ∈ {0, 1}, i = 1, . . . , m, j ∈ E i .
To encode a MCKP instance into a MDCP instance, we keep the same structure (sets) and define:

C = qW -mP , r ij = qw ij -P, i = 1, . . . , m, j ∈ E i , s ij = mp ij + r ij -P, i = 1, . . . , m, j ∈ E i .
with q = 2mP . With such a value for q, one can show that all values C, r ij and s ij belong to Z + . The first MDCP equation can be transformed as follows:

m i=1 j∈Ei r ij x ij ≤ C ⇒ m i=1 j∈Ei (qw ij -P )x ij ≤ qW -mP ⇒ m i=1 j∈Ei qw ij x ij -mP ≤ qW -mP because exactly m variables x ij are set to 1 ⇒ m i=1 j∈Ei w ij x ij ≤ W .
The second MDCP equation can be transformed as follows:

m i=1 j∈Ei r ij x ij ≤ m i=1 j∈Ei s ij x ij , ⇒ 0 ≤ m i=1 j∈Ei (mp ij -P )x ij by simplifying r ij from both sides, ⇒ 0 ≤ m i=1 j∈Ei mp ij x ij -mP because exactly m variables x ij are set to 1, ⇒ P ≤ m i=1 j∈Ei p ij x ij . ⊓ ⊔
Proposition 2 states that pcost allows us to exactly identify soft neighborhood substitutable values when two conditions are verified: γ(x) is separable and pcost(x, a → b) = (β, α) with α < k. In the following proposition, by construction, we deal with instances such that γ(x) is separable. However, nothing is imposed on α, with the consequence that some SNS-eliminable values cannot be detected in polynomial time.

Proposition 4. Deciding if a value is soft neighborhood substitutable for another on a WCN

(X , W , k) where k = ∞ is coNP-hard.
Proof. Any MDCP instance can be reduced to the problem of deciding whether a value (x, a) is not soft substitutable for a value (x, b) on a WCN P . From the MDCP instance, we build the WCN P as follows. vars(P ) contains a variable x such that dom(x) = {a, b} and a variable y i for each set E i ; the domain of y i contains the objects o i1 , o i2 , . . . of E i . cons(P ) contains exactly m binary soft constraints w xyi : we have

w xyi ({(x, a), (y i , o ij )}) = s ij and w xyi ({(x, b), (y i , o ij )}) = r ij . k is set to C. Determining if (x, a) is not soft substitutable for (x, b) on P is equivalent to finding an instantiation I of vars(Γ (x)) such that cost Γ (x) (I x=a ) > cost Γ (x) (I x=b ) which is equivalent to c S ∈Γ (x) c s (I x=b ) < k ∧ c S ∈Γ (x) c s (I x=a ) > c S ∈Γ (x) c s (I x=b ).
The first (resp. second) condition encodes the first (resp. second) inequality of the MDCP. Since variables x ij of the MDCP instance correspond to the assignment of variables y i in the WCSP (x ij = 1 ⇔ y i = o ij ), the third equation of the MDCP instance is directly encoded in the WCSP instance.

⊓ ⊔

Relationships with Soft Arc Consistency

After introducing soft neighborhood substitutability closure, this section presents some results relating soft neighborhood substitutability to various forms of soft arc consistency.

Definition 5. The soft neighborhood substitutability closure (or SNS-closure) of a WCN P , denoted by SNS (P ), is any WCN obtained after iteratively removing SNS-eliminable values until convergence.

Since this operation is not confluent, SNS (P ) is not unique. When we use the pcost approach to identify SNS-eliminable values, we note PSNS (P ).

Proposition 5. Let P be an EDAC-consistent WCN. SNS (P ) is not necessarily EDACconsistent.

Proof. Consider the WCN P depicted in Figure 2(a). Note that P is EDAC-consistent w.r.t. the order w > x > z > y, and that (w, a) and (z, a) are respectively soft neighborhood substitutable for (w, b) and (z, b), since pcost(w, a → b) = (0, 0) and pcost(z, a → b) = (0, 0). There exists a unique SNS-closure of P , P ′ = SNS (P ), which is depicted in Figure 2 Proof. On the one hand, suppose that (x, b) is AC-consistent in Bool(P ). From the previous lemma, we know that (x, a) is neighborhood substitutable for (x, b) on Bool(P ), and so we have AC(Bool(P

)) = ⊥ ⇔ AC(Bool(P \ {(x, b)})) = ⊥. Because P is VAC-consistent, necessarily P \ {(x, b)} is VAC-consistent.
On the other hand, suppose that (x, b) is not AC-consistent in Bool(P ). Clearly we have AC(Bool(P )) = AC(Bool(P \ {(x, b)})), and so

P \ {(x, b)} is VAC-consistent (since P is VAC- consistent). ⊓ ⊔ Corollary 2. Let P be a WCN. If P is VAC-consistent then SNS (P ) is VAC-consistent.
The previous corollary also holds for OSAC (because OSAC is stronger than VAC).

In this section, we introduce an algorithm to enforce AC*+PSNS (that can be easily adapted to EDAC+PSNS, for example). The main idea is always to start identifying SNS-eliminable values from a WCN that is AC*-consistent. This allows us to reduce the computation effort by using early breaks and residues. The main procedure is Algorithm 1. As usual, we use a set, denoted by Q, to store the variables whose domain has been recently reduced. Initially, Q is initialized with all variables (line 4). Then, at line 6, a classical AC* algorithm, denoted here by W-AC*, is run (for example, this may be W-AC*2001 [START_REF] Larrosa | Solving weighted CSP by maintaining arc consistency[END_REF]), before soliciting a function called PSNS r . The calls to W-AC* and PSNS r are interleaved until a fixed point is reached (i.e., Q = ∅).

Function PSNS r , Algorithm 2, iterates over all variables in order to collect SNSeliminable values into a set called ∆. This set is initialized at line 1 and updated at lines 6 and 8. Let us imagine that all SNS-eliminable values (that can be identified by means of pcost) for a variable x have been deleted, and that the domains of all variables in the neighborhood of x remain the same (while possible reductions happen elsewhere). Clearly, there is no need to consider x again for seeking SNS-eliminable values. This is the point of line 3. Here, timestamps are used. By introducing a global counter time and by associating a time-stamp stamp[x] with every variable x as well as a time-stamp substamp with function PSNS r , it is possible to determine which variables should be considered. The value of stamp[x] indicates at which moment a value was most recently removed from dom(x), while the value of substamp indicates at which moment PSNS r was most recently called. Variables time, stamp[x] for each variable x and substamp are initialized at lines 1 to 3 of Algorithm 1. The value of time is incremented whenever a variable is added to Q (line 13 of Algorithm 2 and this must also be performed inside W-AC*) and whenever PSNS r is called (line 9). All SNS-eliminable values collected in ∆ are removed while updating Q for the next call to W-AC* (lines 10 to 12).

Algorithm 1: AC*-PSNS(P : WCN) Output: P , made AC*-consistent and PSNS-closed

1 time ← 0 ; 2 substamp ← -1 ; 3 stamp[x] ← 0, ∀x ∈ vars(P ) ; 4 Q ← vars(P ) ; 5 repeat 6 PSNS r (W -AC * (P, Q)) ; 7 until Q = ∅;
Algorithm 3 allows us to compute the pcost of (x, b) with respect to (x, a). Because we know that the WCN is currently AC*-consistent, we have the guarantee that the pcost of (x, b) with respect to (x, a) on any non-unary constraint c S where x ∈ S is less than or equal to 0. This means that we can never compensate a pair (β, α) s.t. 5 return pcst α > β with a pair (β ′ , α ′ ) s.t. α ′ < β (once the pair of unary costs has been taken into account). A strong benefit of that observation is the possibility of using early breaks during such computations. This is performed at lines 3, 6 and 13. Residues are another mechanism used to increase the performance of the algorithm. For every variable x, and every pair (a, b) of values in dom(x), we store in residues[x, a, b] the constraint c S which guarantees that (x, b) is not SNS-eliminable by (x, a), if it exists. The residual constraint takes priority (lines 4 to 6); this way, if it compensates the initial unary cost, we avoid unnecessary work. It is updated at lines 9-10. Note that we can initialize the array residues with any arbitrary constraints (not shown in the algorithm), and that Algorithm 4 necessarily returns a value less than or equal to 0 (this explains the initialization of pcst to (1, 0) at line 1).

We now discuss the complexity of PSNS r while assuming (for simplicity) that the WCN is binary. The space complexity is O(nd 2 ) due to the use of the structure residues. The time complexity of Algorithm 4 is O(d), and the time complexity of Algorithm 3 is O(1) in the best case (if it is stopped at line 3) and O(qd) in the worst case, where q = |Γ (x)|. Discarding line 3, the time complexity of Algorithm 2 is O(nd 2 ) in the best case and O(nd 3 e) in the worst-case. Of course, Algorithm 2 can be called several times at line 6 of Algorithm 1, so we obtain a worst-case time complexity in O(n 2 d 4 e). However, we have observed in our experiments that the number of successive calls to PSNS r is quite limited in practice (as we were predicting). Besides, imagine now that we call AC*-PSNS after the assignment of a value to a variable x (i.e., during search). In the best case (from a complexity point of view), no removal is made by W -AC * , and so, we just consider the neighbors of x, due to line 3 of Algorithm 2, which gives a best-case time complexity in O(qd 2 ). This last result leans us toward experimenting maintaining AC*-PSNS during search.

Experimental Results

To show the practical value of removing SNS-eliminable values, we have conducted an experimentation using the series of WCSP instances available at http://carlit. toulouse.inra.fr/cgi-bin/awki.cgi/BenchmarkS and a cluster of Xeon 3.0GHz with 1 GB of RAM under Linux. Our goal is to observe the relative efficiency of solving WCSP instances when maintaining AC*, AC*+PSNS, FDAC, FDAC+PSNS, EDAC, and EDAC+PSNS. For variable ordering during search, we use the simple static heuristic max degree which is independent of the pruning efficiency of the different algorithms, as in [START_REF] De Givry | Singleton consistency and dominance for weighted CSP[END_REF] where some experiments have been performed with a partial form of SNS enforced during a preprocessing stage.

Table 1 shows the average results obtained on various series. For each series, the number of considered instances (#inst) is given below the name of the series. We have discarded the instances that have not been solved by at least one of the algorithms, within 1,200 seconds. Here, a solved instance means that an optimal solution has been found and proved. In Table 1, the number (#sol) of instances solved within 1,200 seconds is given as well as the average CPU time over these solved instances. The average number (avg-sub) of SNS-eliminable values deleted during search (at each step) is also given (rounded to the nearest integer). On RLFAP instances (celar, scens, graphs), the benefit of using PSNS is rather erratic, but on planning (driver, mprime), coloring (myciel, geom), spot and warehouse instances, we can see a clear advantage of embedding PSNS. Overall, maintaining PSNS is cost-effective as it usually offers a benefit both in terms of solved instances (see last line of the table) and CPU time. Table 2 presents the results obtained on some representative instances. It is interesting to note that on the warehouse instances (here, cap101, cap111 and capmo1), enforcing PSNS does not entail a reduction of the size of the search tree (see the values of #nodes). However, PSNS permits to significantly reduce the size of the domains, making propagation of soft constraints quicker. On celar7-sub1, note that (maintaining) EDAC+PSNS is only about 50% faster than EDAC while the number of nodes has been divided by 10. This means that on such instances, PSNS is rather expensive, which maybe lets room for further improvements.

Conclusion

In this paper, we have investigated the property of soft neighborhood substitutability for weighted constraint networks, and have found a sufficient condition on substitutions that can be identified by an algorithm of reasonable complexity (restricted to the neighborhood and polynomial). We have proved that, even in simple cases, when k = ∞, the problem of deciding whether a value is soft neighborhood substitutable for another is coNP-hard. We have also given some properties linking substitutability and soft arc consistencies. Finally, we have proposed an algorithm that exploits early breaks and residues and shown experimentally that it can be helpful during search.

Definition 1 .

 1 Let x ∈ vars(P ) and {a, b} ⊆ dom(x), -(x, a) is (fully) substitutable for (x, b) on P iff for every solution I x=b of P , I x=a is also a solution of P ; -(x, a) is (fully) interchangeable with (x, b) on P iff (x, a) is substitutable for (x, b) and (x, b) is substitutable for (x, a). For example, consider a CN P such that vars(P ) = {x, y, z} and sols(P ) = {(a, a, a), (a, b, b), (b, a, a), (c, a, a), (c, b, b)}. The values (x, a) and

Fig. 1 .

 1 Fig. 1. (x, a) is soft substitutable for (x, b)

Definition 4 .

 4 Let x ∈ vars(P ) and {a, b} ⊆ dom(x), the cost pair of (x, b) w.r.t. (x, a) on c S ∈ Γ (x) is defined as pcost(c S , x : a → b) = min I∈l(S) {(c S (I x=b ), c S (I x=a ))}; the cost pair of (x, b) with respect to (x, a) on P is defined as pcost(x : a → b) = c S ∈Γ (x) pcost(c S , x : a → b). Proposition 1. Let x ∈ vars(P ) and {a, b} ⊆ dom(x). If pcost(x : a → b) ≥ 0 then (x, a) is soft neighborhood substitutable for (x, b) on P . Proof. For a constraint c S , let I cs be the instantiation of S -{x} which yields the minimal cost pair in min I∈l(S) {(c S (I x=b ), c S (I x=a ))}. By definition, pcost(c S , x : a → b) = (c S (I c S x=b ), c S (I c S x=a )). By definition of min on cost pairs, we have ∀I, ∀c S ∈ Γ (x), (c S (I x=b ), c S (I x=a )) ≥ (c S (I c S x=b ), c S (I c S x=a )). By summing up, we obtain ∀I, c S ∈Γ (x) (c S (I x=b ), c S (I x=a )) ≥ c S ∈Γ (x) (c S (I c S x=b ), c S (I c S x=a )). By hypothesis, we have pcost(x : a → b) ≥ 0, so c S ∈Γ (x) (c S (I c S x=b ), c S (I c S x=a )) ≥ 0, and consequently ∀I, c S ∈Γ (x) (c S (I x=b ), c S (I x=a )) ≥ 0. From definition of + and ≤ on cost pairs, we can derive ∀I, c S ∈Γ (x) c S (I x=b ) ≥ c S ∈Γ (x) c S (I x=a ) which implies ∀I, min(k, c S ∈Γ (x) c S (I x=b )) ≥ min(k, c S ∈Γ (x) c S (I x=a )). Since ∀a i ∈ {0, . . . , k}, a 1 ⊕ . . . ⊕ a n = min(k, a 1 + . . . a n }, we can conclude that ∀I, c S ∈Γ (x) c S (I x=b )) ≥ c S ∈Γ (x) c S (I x=a )). Hence, (x, a) is soft neighborhood substitutable for (x, b) on P . ⊓ ⊔

Example 2 .

 2 Let's consider four variables x, y, z t such that dom(x) = {a, b}, dom(y) = {c, d}, dom(z) = dom(t) = {e}, and two ternary constraints c xyz , c xyt defined by the following cost table:x y z t c xyz c xyt aIt is easily seen that (x, a) is soft neighborhood substitutable for (x, b) but pcost(c xyz , x, a → b) = pcost(c xyt , x, a → b) = (0, 1) and therefore pcost(x, a → b) = (0, 2) ≥ 0.

Proposition 2 .Corollary 1 .

 21 Let x ∈ vars(P ) and {a, b} ⊆ dom(x) such that Γ (x) is separable and pcost(x, a → b) = (β, α) with α < k. If (x, a) is soft neighborhood substitutable for (x, b) on P then pcost(x : a → b) ≥ 0.Proof. Since by hypothesis Γ (x) is separable, one can define the instantiation I min on vars(Γ (x)) \ {x} as the union for each constraint C s ∈ Γ (x) of the instantiationsI c S defined in the proof of Proposition 1. I min is such that pcost(c S , x : a → b) = (c S (I min x=b ), c S (I min x=a )). By hypothesis, ∀I, cost Γ (x) (I x=b ) ≥ cost Γ (x) (I x=a ) which can be rewritten as ∀I, c S ∈Γ (x) c S (I x=b ) ≥ c S ∈Γ (x) c S (I x=a ).This is especially true for I = I min therefore c S ∈Γ (x) c S (I min x=b ) ≥ c S ∈Γ (x) c S (I min x=a ), giving min(k, β) ≥ min(k, α) where β = c S ∈Γ (x) c S (I min x=b )) and α = c S ∈Γ (x) c S (I min x=a ). By definition, pcost(x : a → b) = (β, α) and therefore pcost(x : a → b) ≥ 0 iff β ≥ α. Now, if α < k, min(k, α) = α and min(k, β) ≥ min(k, α) ⇒ β ≥ α ⇒ pcost(x : a → b) ≥ 0 (this is true for both β < k and β ≥ k). Note that when α ≥ k, min(k, β) ≥ min(k, α) ⇒ β ≥ α, a counter example being β = k and α = k + 1. ⊓ ⊔ Let x ∈ vars(P ) and {a, b} ⊆ dom(x) such that Γ (x) is separable and pcost(x : a → b) = (β, α) with α < k. If (β, α) < 0 then (x, a) is not soft neighborhood substitutable for (x, b) on P .

Fig. 2 .Proposition 6 .

 26 Fig. 2. EDAC versus SNS

Algorithm 2 : 6 ∆

 26 PSNS r (P : WCN AC*-consistent)1 ∆ ← ∅ ; 2 foreach x ∈ vars(P ) do 3 if ∃y ∈ Γ (x) | stamp[y] > substamp then 4 foreach (a, b) ∈ dom(x) 2 | b > a do 5 if pcost(x, a → b) ≥ 0 then ← ∆ ∪ {(x, b)} ;

7 else 8 ∆ 12 Q 8 d

 78128 if pcost(x, b → a) ≥ 0 then ← ∆ ∪ {(x, a)} ; 9 substamp ← time++ ; 10 foreach (x, a) ∈ ∆ do 11 remove (x, a) from dom(x) ; ← Q ∪ {x} ; 13 stamp[x] ← time++ ; Algorithm 3: pcost(x, a → b): cost pair 1 pcst ← (cx(b), cx(a)) ; 2 if pcst < 0 then 3 return pcst 4 pcst ← pcst + pcost(residues[x, a, b], x, a → b) ; 5 if pcst < 0 then6 return pcst 7 foreach cS ∈ Γ (x) | cS = residues[x, a, b] do ← pcost(cS, x, a → b) ; 9 if d < (cx(a), cx(b)) then 10 residues[x, a, b] ← cS ; 11 pcst ← pcst + d ; 12 if pcst < 0 then 13 return pcst 14 return pcst Algorithm 4: pcost(c S , x : a → b): cost pair 1 pcst ← (1, 0) ; 2 foreach I ∈ l(S \ {x}) do 3 if (cS(I x=b ), cS(Ix=a)) < pcst then 4 pcst ← (cS(I x=b ), cS(Ix=a)) ;

Table 1 .

 1 Mean results obtained on various series (a time-out of 1,200 seconds was set per instance).

	Series		AC*	AC*	FDAC	FDAC	EDAC	EDAC
				+PSNS		+PSNS		+PSNS
	celar	#sol (cpu)	5 (337)	4 (231)	6 (316)	6 (341)	6 (344)	7 (461)
	#inst=7	avg-sub	0	3	0	6	0	4
	driver	#sol (cpu) 18 (103)	18 (52) 19 (39.3) 19 (19.7) 19 (68.5) 19 (56.8)
	#inst=19	avg-sub	0	1	0	1	0	1
	geom	#sol (cpu)	5 (37.4) 5 (12.4) 5 (18.8) 5 (11.0) 5 (21.0) 5 (12.0)
	#inst=5	avg-sub	0	0	0	1	0	0
	mprime	#solv (cpu) 4 (9.82) 8 (17.4) 4 (11.6) 8 (12.0)	5 (206) 8 (21.0)
	#inst=8	avg-sub	0	1	0	1	0	1
	myciel	#sol (cpu)	3 (122) 3 (77.0) 3 (72.9) 3 (34.3) 3 (80.4) 3 (37.8)
	#inst=3	avg-sub	0	2	0	3	0	3
	scens+graphs #sol (cpu)	1 (20.4)	3 (113)	8 (242)	7 (186)	6 (266) 5 (19.8)
	#inst=9	avg-sub	0	8	0	8	0	8
	spot5	#sol (cpu)	0	0 3 (20.5) 3 (12.6) 3 (20.1) 3 (11.4)
	#inst=3	avg-sub	0	0	0	0	0	0
	warehouse #sol (cpu) 12 (286) 12 (46.2) 18 (166) 24 (139) 28 (53.2) 29 (79.8)
	#inst=34	avg-sub	0	4	0	7	0	27
		#solved	48	53	66	75	75	79

Acknowledgments

This work has been supported by both CNRS and OSEO within the ISI project 'Pajero'.

Instances


Éric Grégoire
email: eric.gregoire@cril.fr

Jean-Marie Lagniez
email: jean-marie.lagniez@jku.at

Bertrand Mazure
email: bertrand.mazure@cril.fr

Relax!

This paper is concerned with a form of relaxation of constraint networks. The focus is on situations where additional constraints are intended to extend a nonempty set of preexisting solutions. These constraints require a specific treatment since merely inserting them inside the network would lead to their preemption by more restrictive ones. Several approaches to handle these additional constraints are investigated from conceptual and experimental points of view.

Introduction

CSPs (Constraints Satisfaction Problems) have emerged as one of the most fertile research fields of applied Artificial Intelligence (see for example as major conferences, journals and handbook in the domain [START_REF]Principles and Practice of Constraint Programming -CP 2011 -17th International Conference, CP 2011[END_REF][START_REF] Beldiceanu | Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems -9th International Conference[END_REF][START_REF] Pesant | [END_REF][START_REF]Handbook of Constraint Programming[END_REF]). A CSP concerns a constraint network that models a problem through a set of constraints linking various variables, each variable exhibiting its own instantiation domain. The CSP might consist in verifying whether the set of constraints exhibits solutions or not. In the positive case, it can consist in computing one solution.

In this paper, the focus is on relaxing non-empty sets of solutions of constraint networks when an additional, more permissive, constraint C must be taken into account in such a way that C prevails over the more restrictive pre-existing ones.

Assume for example that a complex constraint network determines under which circumstances some specific retirement benefits can be claimed and delivers as solutions all situations where the applicant is the parent of at least 3 children. These solutions are not necessarily explicit in the network but can result from the interaction of several constraints. Now assume that the legislation has changed and that a more permissive rule is adopted allowing these benefits to be claimed by parents of at least two children. If this new constraint is merely inserted as an additional one within the initial network then it will be preempted by the constraints requiring at least three children. Being the parent of two children would still not allow the aforementioned benefits. Indeed, since solving the network will try to satisfy all constraints together, the additional solution translated by the new more permissive rule will be subsumed in the process by the more restrictive ones: having at least two children is satisfied whenever having at least three children is satisfied. Accordingly, we investigate several approaches to handle in an adequate way additional constraints that, at the same time, are more permissive and must prevail.

The paper is organized as follows. In the next section, basic concepts about CSP are recalled. Section 3 briefly presents the MUC (Minimal Unsatisfiable Core) and MSS (Maximal Satisfiable Sub-network) concepts, which are central in this study. Relaxing a constraint network is defined more formally in section 4. In sections 5 and 6, several approaches to address this issue are investigated. In section 7, experimental results are presented about the practical efficiency of the approaches whereas the application of the technique in other circumstances is discussed in section 8. The conclusive section elaborates on promising perspectives for further research.

Constraints networks

A constraint network P is a pair (X , V) where X a finite set of m constraints over a finite set V of discrete variables. Each variable V ∈ V has its own instantiation domain, denoted dom(V ).

Each constraint C ∈ X involves a subset of variables of V, called scope and noted var(C). A relation, de-noted rel(C), contains the set of tuples that C allows for the variables in var(C) and is called the support of C. In a dual way, the relation f or(C) exhibits the set of tuples of values forbidden by C.

Example 1. Let the constraint (x < y -1) with dom(x) = {0, 1} and dom(y) = {1, 2, 3}, we have: var(x < y -1) = {x, y}, rel(x < y -1) = {(x = 0, y = 2), (x = 0, y = 3), (x = 1, y = 3)} and f or(x < y -1) = {(x = 0, y = 1), (x = 1, y = 1), (x = 1, y = 2)}.

A solution to a constraint C is any partial assignment that instantiates all the variables occurring in C in such a way that C is satisfied. A solution to a constraint C is an element of rel(C).

A solution to P is an assignment of a value to each variable such that all the constraints are satisfied. A constraint network is said satisfiable iff it admits at least one solution.

The Constraint Satisfaction Problem (CSP) is the NP-hard task of determining whether a given constraint network is satisfiable or not. It can also consist in computing one solution in the positive case.

Example 2. Let P = (X , V) with V = {i, j, k, l, m}, dom(i) = dom(j) = dom(k) = dom(l) = dom(m) = {1, 2, 3} and C = {(j < k), (k < i), (k = l), (j ≥ l), (m = l + 1), (m + i < 5)}. This constraint network is satisfiable: {i = 3, j = 1, k = 2, l = 1, m = 1}
is an assignment that satisfies all constraints of X .

Let P = (X ∪{(i < j)}, V). This constraint network has no solution; it is unsatisfiable.

MUC and MSS

Although the focus is on satisfiable constraint networks, the following concept related to unsatisfiability will be central in this paper.

Any unsatisfiable constraint network P = (X , V) involves at least one MUC (Minimal Unsatisfiable Core), also called core. A MUC is a subset of constraints of X that, at the same time, is unsatisfiable and that is such that each proper subset is satisfiable. A MUC is thus a smallest subset of constraints that cannot be accommodated together.

Example 3. P defined in the previous example admits only one MUC, namely {(j < k), (k < i), (i < j)}.

In a dual way, a Maximal Satisfiable Sub-network (MSS) of P = (X , V) is defined as any satisfiable P = (X , V) such that ∀C ∈ X \ X , the constraint network (X ∪ {C}, V) is unsatisfiable.

Example 4. In the Example 2, P is a maximal satisfiable sub-network of P .

Checking whether a constraint belongs to a MUC or not is in Σ P 2 [START_REF] Eiter | On the complexity of propositional knowledge base revision, updates, and counterfactuals[END_REF]. In the worst case, the number of MUCs can be exponential in the number m of constraints (it is in O(C m/2 m )). Since MUCs can intersect, the concept of cover of MUCs has been introduced to alleviate the possible high number of MUCs, at least to some extent [START_REF] Grégoire | Must: Provide a finer-grained explanation of unsatisfiability[END_REF]. Despite those bad worst-case complexity results, in many real-life situations, the number of MUCs can remain of a manageable size and both MUCs and MSSes can be computed in realistic time (see for example approaches in [START_REF] Grégoire | Must: Provide a finer-grained explanation of unsatisfiability[END_REF] and [START_REF] Grégoire | On finding minimally unsatisfiable cores of csps[END_REF]).

One specific well-studied problem about MSS is called WCSP (as Weighted CSP) which consists in delivering one MSS of a constraint network following a priority scale between constraints. Each constraint is given a numerical value and constraints with the higher values are preferred candidates for belonging to the resulting MSS. More on MUC and MSS can be found in [START_REF] Bakker | Diagnosing and solving over-determined constraint satisfaction problems[END_REF][START_REF] Han | Deriving minimal conflict sets by cs-trees with mark set in diagnosis from first principles[END_REF][START_REF] Jussien | Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems[END_REF][START_REF] Junker | Quickxplain : Conflict detection for arbitrary constraint propagation algorithms[END_REF][START_REF] Petit | A general conflictset based framework for partial constraint satisfaction[END_REF][START_REF] Junker | Quickxplain : Preferred explanations and relaxations for over-constrained problems[END_REF][START_REF] Hemery | Extracting mucs from constraint networks[END_REF][START_REF] Grégoire | Must: Provide a finer-grained explanation of unsatisfiability[END_REF][START_REF] Grégoire | On finding minimally unsatisfiable cores of csps[END_REF].

Relaxing satisfiable networks

From now on, we assume that the constraint network P = (X , V) is satisfiable and that a constraint C over variables from V is the additional more permissive one that must prevail.

First, let us define what more permissive and prevail mean in this study. Remember that, on the one hand, a solution to a constraint C is any partial assignment that instantiates all the variables occurring in C in such a way that C is satisfied. On the other hand, a solution to P is any assignment of all the variables of V that satisfies all constraints in X . Definition 1. A constraint C is more permissive than a constraint network P iff 1. there exists at least one solution to C that cannot be extended into an a solution to P, and 2. any solution to P restricted to the scope of C is a solution to C. Definition 2. A constraint C prevails in P iff all solutions to C can be extended into solutions to P. Thus, relaxing P by a more permissive constraint C must lead to a new network P such that any solution to C has been extended into a solution to P . Definition 3. A constraint network P = (X , V) is a relaxed network of P = (X , V) by C iff any solution to C can be extended into a solution to P .

Note that forcing all solutions of C to be adopted might lead to the existence of additional solutions related to variables outside the scope of C through a domino effect within P. Hence, P can exhibit new solutions about variables not occurring in C in addition to those provided by P. For a similar reason, we cannot require in the general case that any solution of P is a solution of P .

MUC-based solutions

Several constraints in P can prevent solutions to C from prevailing in P. A first approach provides the user will a full-fledged explanation of the reasons for this, under the form of the minimal sets of constraints that cause the problem. It is based on MUC-finding algorithms and the main idea is intuitively as follows.

Whenever a single element of rel(C) is introduced as a new constraint in P and when this leads to an unsatisfiable network P , this means that P does not authorize rel(C). Accordingly, we compute and exhibit MUCs in P . A least one constraint per MUC is expelled (or relaxed) from P. This is iterated until the network P becomes satisfiable. The whole process is then iterated for all elements of rel(C). Thereafter, the constraint C is just safely added since we are sure that all its solutions can be now accommodated. When we know which elements of rel(C) cannot be extended into solutions to P, it is sufficient for the procedure to consider these elements, only.

Accordingly, any detected MUC provides a minimal set of constraints preventing an additional solution given by C from prevailing in P. Algorithm relaxMUC describes the skeleton of an iterative approach finding out and "breaking" in an automatic way MUCs iteratively, until no MUC remains. Note that the depicted algorithm does not return the set of detected MUCs but expels one constraint per MUC and simply delivers the final resulting relaxed constraint network. Note that since MUCs can intersect, a cover of MUCs can be delivered and amended as an alternative approach.

MSS-based solutions

When not all MUCs must be exhibited to the user. the dual concept of Maximal Satisfiable Sub-networks (MSS) can also be used. Note that MUCs and MSSes can be easily computed one from the other, or be computed separely using their own specific algorithmic paradigms [START_REF] Bailey | Discovery of minimal unsatisfiable subsets of constraints using hitting set dualization[END_REF].

Definition 4. A constraint network P = (X ∪{C}) is a MSS-relaxed network of P = (X , V) by C iff X ⊂ X Function relax-MUC((X , V), C): (X , V)
input : P = (X , V): a constraint network, C: the new constraint output: (X , V): a relaxed constraint network of P by C X ← X ; Indeed, a MSS-relaxed network can depend both on the order according to which the solutions of rel(X) are considered and on the actual selection of constraints that are dropped. For example, dropping a constraint that belongs to the intersection of several MUCs (each of them related to a different solution of rel(X)) conducts larger MSS-related networks to be generated.

1 foreach t ∈ rel(C) do 2 C t ← {t} with dom(C t ) = dom(C) ; 3 while (X ∪ {C t }, V) is unsat do 4 (X , V ) ← MUC((X ∪ {C t }}, V)); 5 select one constraint C in X s.t. C = C t ; 6 X ← X \ {C } ;
The relax-MSS algorithm describes such a function computing one MSS-relaxed network of P by C. Note that the computation of one MSS can be performed though WCSP.

Relax in other circumstances, too

Interestingly, we can apply this relaxation technique when the new constraint C is not more permissive. In this case, the technique simply leads to add C into P.

Also, it can be applied to unsatisfiable networks as well. In this case, it does not only restore consistency but also enforces C as a more permissive constraint. Note that in such a case the computed MUCs do not necessarily contain the enforced constraint made of one Function relax-MSS((X ,V), C): (X , V) input : P = (X , V): a constraint network, C: the new constraint output: (X , V): a relaxed constraint network of P by C X ← X ;

1 foreach t ∈ rel(C) do 2 C t ← {t} with dom(C t ) = dom(C) ; 3 X ← MSS((X ∪ {C t }, V)) ; 4 X ← X \ {C t } ; 5 end 6 X ← X ∪ {C}; 7 return (X , V); 8
value of rel(C). Similarly, constraints not included in a MSS need not belong to a MUC containing this additional constraint. Also note that WCSP, which can be used to compute MSSes, can take into account an a priori preference ordering between constraints through numerical coefficients. Accordingly, it allows to respect a preference among constraints in order to designate the ones to be dropped.

Experimental results

All experimental results presented in this section have been obtained on a Quad-core Intel XEON X5550 with 32Gb of memory. The CPU time was limited to 7200 seconds. We have implemented our algorithms on top of the CSP-solving platform Abscon http://www. cril.univ-artois.fr/ ~lecoutre/software.html

We have run our algorithms on more than 600 instances taken from the satisfiable benchmarks of the last CSP competitions http://cpai.ucc.ie/08/ et http://cpai.ucc.ie/09/. In the Tables we present results for 53 instances from the 204 ones that were not time-out for neither of our approaches (the full tables are available from https://www.dropbox.com/ sh/q579823oyfr0g9z/66RxbrNYCC).

We generated the additional constraints in the following random way so that they were necessarily more permissive ones. One constraint of the instance was selected in an random fashion; its allowed and forbidden tuples computed. Then, a random number of forbidden tuples changed of status and became allowed. The same data have been submitted to both relax-MUC and relax-MSS.

The columns from Tables 1 and2 provide the following information. The Tables illustrate the practical feasibility of the approaches for complete methods computing MUCs and MSSes. Let us stress on some lessons from these experimentations.

Relax-MSS allows to compute a minimal number of constraints to be expelled so that the instance is relaxed with respect to the additional constraint C. Consequently, the number of constraints expelled by this method is always lower or equal to the number of constraints expelled by relax-MUC. However, relax-MUC provides results that exhibit a number of constraints that is often close to this minimal number (although exceptions exist: see for example instance e64-b).

On the other hand, this minimization is computationally costly: in this respect, it is not a surprise to see that relax-MUC is generally more time efficient (although exceptions exist: see for example instance e64-b again). Relax-MUC allowed 72 additional instances to be relaxed. Technically, this is due to the fact that computing a MSS delays branches-pruning decisions in the search trees (the descent is not stopped when a constraint is falsified but only when a specific number of constraints are falsified). In this respect, one possible improvement w.r.t. the MSS-computation would consist in running a local search procedure to find out one "good" first boundary.

The average computing time for relax-MUC is 780 secs when only the successfully relaxed instances are taken into account whereas it is 691 secs for relax-MSS when only the solved instances by this method were considered. This apparently better result in favor of relax-MSS is due to the fact this method mainly solved the simple instances and did not solve a large number of instances where a large number of constraints need be expelled.

Conclusion

Some past research efforts in the CSP research community have already concerned the problem of constraint relaxation in the framework of unsatisfiable constraint networks [START_REF] Jussien | Maintien de déduction pour la relaxation de contraintes[END_REF][START_REF] Georget | Constraint retraction in clp(fd): Formal framework and performance results[END_REF][START_REF] Amilhastre | Consistency restoration and explanations in dynamic csps-application to configuration[END_REF][START_REF] Nordlander | Constraint relaxation techniques to aid the reuse of knowledge bases and problem solvers[END_REF]. Quite surprisingly, to the best of our knowledge, this issue has not been investigated so far in the context of satisfiable networks that must accommodate an additional constraint whose solutions must not be lost. This study is a first contribution to fill this gap. We believe that more research efforts should be devoted about the dynamics of networks. In particular, the problem investigated in this paper is even more crucial and ubiquitous when several networks need to be merged.

Several paths for further extensions of this study can be envisioned. First, instead of expelling constraints, we may want to amend constraints that forbid additional solutions to C from being extendable into solutions to P. Also, instead of considering computationally costly complete techniques computing MUCs and MSSes we might want to build and experiment approximate methods that attempt to provide, for example, a superset of a MUC that would normally not be significantly larger than the MUC itself.

This study also sheds light on the necessity to distinguish between several forms of constraints in the following sense. Usually, all constraints are restrictive in the sense that each of them can restrict the space of possible solutions provided by other constraints. As illustrated in this paper, we can also need to represent permissive constraints instead of restrictive ones. Permissive constraints appear as hard constraints that must be satisfied in all circumstances. Moreover, a permissive constraint translates solutions that cannot be lost due to other (restrictive) constraints. Considering permissive constraints in the traditional algorithms for solving CSPs opens new exciting and very substantial perspectives.

We believe that these are promising paths for further research.

7 end 8 end 9 XProposition 1 .Proposition 2 .

 78912 ← X ∪ {C}; 10 return (X , V); 11 and (X ∪ {t}, V) is satisfiable for every t in rel(C). Definition 5. A MSS-relaxed constraint network P = (X ∪{C}) of P by C is maximal iff there does not exist any other MSS-relaxed network P" = (X " ∪ {C}) of P by C such that X ⊂ X ". Every MSS-relaxed network of P by C is a relaxed network of P by C. Not all MSS-relaxed networks are maximal in the general case.

•

  name: instance name • #V: number of variables of the instance • #C: number of constraints of the instance • |rel(C)|: size of the support of the additional constraint • #ns: number of tuples of rel(C) to be relaxed, i.e., the number of tuples of rel(C) that are forbidden by other constraints of the instance (this information is not an input of the algorithms) • |var(C)|: size of scope of the additional constraint • #rc: number of expelled constraints • #rc avg : average number of constraints per tuple to be relaxed • T 1 : average CPU time to relax one tuple • T 2 : total CPU time to relax all tuples • T 3 : total CPU time for the method

Table 1 . Results for relax-MUC

 1

	Instance			New constraint		MUC	Time in seconds
	name	#V	#X |rel(C)| #ns |var(C)| #rc #rcavg	T 1	T 2	T 3
	9symml	651	1648	22	2	6	-	-	-	-	-
	C17	15	20	4	1	3	1	1.00	.58	.585	2
	aim-100-1-6-4	200	260	8	2	4	2	11.00	3.86	7.720	14
	aim-100-2-0-3	200	300	8	2	4	2	54.50	35.06	70.124	77
	aim-100-3-4-4	200	440	8	2	4	10 184.20 244.22 2442.238 2451
	aim-200-1-6-4	400	520	4	2	3	2	60.50	57.02 114.042 144
	aim-200-2-0-4	400	600	8	2	4	2	33.00	52.07 104.153 219
	aim-50-1-6-4	100	130	4	2	3	2	52.50	29.50	59.013	62
	aim-50-2-0-4	100	150	8	2	4	2	11.00	3.73	7.475	11
	aim-50-3-4-1	100	220	8	3	4	6	73.00	33.15 198.917 204
	aim-50-6-0-4	100	350	8	3	4	14	57.78	24.14 338.075 345
	b1	24	45	8	1	4	1	1.00	.69	.694	4
	blast-floppy1-4	237	196	8	2	4	67	1.00	.93	62.671	123
	blast-floppy1-6	719	592	1	1	4	-	-	-	-	-
	c8	239	523	4	1	3	1	1.00	1.68	1.684	5
	cc	133	219	2	0	3	0	0.00	0.00	0	1
	cm42a	99	185	8	1	4	1	1.00	.99	.997	5
	cmb	304	670	4	1	3	1	1.00	2.57	2.571	7
	e64-b	607	1022	22	1	8	807	1.00	1.87 1510.178 1696
	elf-rf6	67	131	4	4	3	70	2.07	.79	55.999	72
	enigma	100	42	5	1	11	2	1.00	1.99	3.995	19
	fpga-10-9	135	118	22	1	11	1	18.00	49.47	49.477	77
	g-100x100	10000 10000	22	1	6	1	1.00	20.49	20.494	123
	graceful-K3-P2	15	60	48	5	3	25	41.04	6.98	174.590 197
	graceful-K4-P2	24	164	169	4	3	41 131.36 86.92 3563.927 3670
	haystacks-05	25	54	18	2	3	2	21.00	6.66	13.321	21
	ii-32e2	534	3013	4	1	3	1	1.00	7.01	7.010	241
	lseu	89	28	22	1	8	1	1.00	1.15	1.151	14
	mod008	319	6	22	0	197	0	0.00	0.00	0	48
	mps-p0282	282	221	4	1	3	1	1.00	3.62	3.622	15
	os-taillard-5-100-9	25	100	1531	4	3	8	44.87 374.56 2996.515 5546
	os-taillard-5-105-9	25	100	1678	3	3	3	2.66	6.77	20.335 3135
	os-taillard-5-95-9	25	100	1391	9	3	16	31.06 141.30 2260.807 4245
	p0033	33	15	8	1	4	1	1.00	.70	.705	4
	p0201	195	133	14	3	10	-	-	-	-	-
	p0282	282	221	4	1	3	1	1.00	3.28	3.286	15
	par-8-1-c	128	318	8	4	4	8	74.87	30.96 247.751 254
	par-8-5-c	150	373	8	4	4	7	74.71	32.76 229.353 235
	pk1	86	60	4	1	3	1	1.00	1.24	1.247	4
	primes-15-20-3-5	100	20	450	2	5	3	1.00	3.59	10.797	595
	primes-15-40-3-1	100	40	417	1	5	7	2.00	1.50	10.526	342
	primes-15-60-2-1	100	60	331	2	4	5	1.00	.74	3.705	156
	primes-15-80-2-1	100	80	295	2	3	8	1.87	.95	7.619	147
	radar-10-10-4.5-0.95-100 435	500	4	1	3	1	1.00	1.36	1.364	4
	radar-10-20-4.5-0.95-100 934	1062	4	1	3	-	-	-	-	-
	radar-8-30-3-0-14	180	64	41	4	13	6	1.00	272.82 1636.930 2106
	ruler-34-8-a3	36	434	365	7	3	195 24.77	6.30 1228.791 1509
	sao2-b	372	765	22	1	10	-	-	-	-	-
	scen2	200	1235	483	1	3	1	1.00	2.77	2.772	398
	scen6-w1-f2	200	319	345	4	3	5	7.00	2.77	13.853	194
	scen7-w1-f5	400	660	270	4	3	9	6.33	2.81	25.331	206
	stein27	27	118	13	5	28	52	1.00	.55	29.049	46
	stein45	45	331	8	1	4	1	1.00	1.00	1.005	5

Acknowledgements

This work has been supported in part by the Conseil Régional du Nord/Pas-de-Calais , the EC through a FEDER grant and FWF, NFN Grant S11408-N23 (RiSE). We thank C. Lecoutre for making Abscon available and for his help in programming it.


Éric Grégoire
email: gregoire@cril.fr

Jean-Marie Lagniez

Bertrand Mazure
email: mazure@cril.fr

Preserving Partial Solutions while Relaxing Constraint Networks *

This paper is about transforming constraint networks to accommodate additional constraints in specific ways. The focus is on two intertwined issues. First, we investigate how partial solutions to an initial network can be preserved from the potential impact of additional constraints. Second, we study how more permissive constraints, which are intended to enlarge the set of solutions, can be accommodated in a constraint network. These two problems are studied in the general case and the light is shed on their relationship. A case study is then investigated where a more permissive additional constraint is taken into account through a form of network relaxation, while some previous partial solutions are preserved at the same time.

Introduction

The study of CSPs (Constraint Satisfaction Problems) has long been a fertile research domain in Artificial Intelligence (see for example [Milano, 2012;[START_REF] Beldiceanu | [END_REF][START_REF] Pesant | [END_REF][START_REF] Rossi | [END_REF] as major current conferences, journals and handbooks). In this paper, we are concerned with CSPs about constraint networks that model problems through a set of constraints linking various variables where each variable is provided with a finite instantiation domain. A solution to a constraint network P is an assignment of values to all variables occurring in P such that all constraints of P are satisfied. A CSP is an NP-hard problem that consists in checking whether P exhibits solutions or not, and in computing one solution in the positive case.

In this paper, we are not directly concerned with the problems of finding out a solution to a constraint network or showing that no solution exists. Instead, we are concerned with how a network must be transformed in order to accommodate an additional constraint in such a way that some specific objectives can be met.

The usual, simplest and most direct way to accommodate an additional constraint c consists in inserting c inside the network, which is enlarged to include possible additional variables occurring in c, and then in checking previous solutions or re-starting the search for solution(s) while reusing previous computations as much as possible. Although such a direct insertion and treatment of c often matches the user's intended goal, there exist however circumstances where this approach is not the right one. In this paper, several such situations are investigated.

Preserving some partial solutions. Assume that a manager needs to take decisions based on all solutions provided by a network P that models constraints guiding the allocation of resources among several tasks. She has to investigate how an additional task of less importance could also be performed under the constraint that this would not restrict the range of current solutions for the most important tasks. At the extreme, she might want to consider the case where all current solutions about all variables are to be preserved when the possible additional task is taken into account.

A solution to P being an assignment of values to all the variables occurring in P and satisfying all constraints of P, she thus wants to preserve some partial solutions, namely the tuples of values assigned by global solutions to some given variables of P. These variables express the allocation of resources for the most important tasks. Assume that c represents the constraints about the additional task. Clearly, inserting c inside P would not always provide the intended result as some previous solutions to P and partial solutions about the most important tasks might be lost in this way. Indeed, inserting an additional constraint c can decrease the set of solutions. Note that rank ordering constraints and assigning a lower priority to c would not solve the issue in the general case: previous solutions to P that conflict with c would still be dismissed. Introducing one or several additional constraints to represent and handle the partial solutions to be preserved must make sure that each one (vs. at least one) of these solutions which are mutually incompatible takes part in at least one solution of the resulting network that will include c. In decision-support systems, the structure and form of the CSP must often be modified as less as possible when an additional constraint is handled: for example, transforming the CSP into a set of tuples that solve the new problem would be a conceptually simple -but inappropriate-approach. Indeed, the specifications of the CSP might further evolve and the constraints must be available for possible additional subsequent evolutions of the system, which must be well-understood and explainable in terms of the constraints, which can be written in intentional form.

Accommodating more permissive constraints. We also consider circumstances where an additional constraint is intended to be more permissive and allow for more solutions. Obviously, inserting an additional constraint inside a network P to form a new network P cannot enlarge the set of possible solutions from P that will take part in the solutions to P . In the above resource allocation problem, this coincided with relaxing some resource availability. When it is easy to locate the constraints or domain variables that forbid the additional solutions, the problem is straightforward. However, it happens that this relaxation of the problem specifications is to be performed among dispersed constraints and variable domains in interaction that are not easy to pinpoint. Let us illustrate the issue through a simpler example from another CSP application domain. Consider a complex constraint network P in the legal domain that models, among other things, under which circumstances some specific parental benefits can be claimed. For this issue, it delivers as solutions all situations where the applicant is the parent of at least 3 children. This constraint is not necessarily explicit in P but can result from the interaction of several other ones. Now assume that the legislation changes and that a more permissive rule is adopted allowing these benefits to be claimed by parents of at least two children. If this new constraint is merely inserted as an additional one within P then it will be preempted by the constraints requiring at least three children. Being the parent of two children would still not allow the aforementioned benefits. Indeed, since solving P will try to satisfy all constraints together, the additional solution translated by the new more permissive rule will be subsumed in the process by the more restrictive ones: having at least two children is satisfied whenever having at least three children is satisfied. More generally, whenever a new constraint c is intended to enlarge a set of solutions of a given constraint network, it cannot be merely inserted within the network. A form of network relaxation should take place instead. Locating constraints and domain variables to be relaxed is not always a straightforward issue: specific methods and tools are required to that end. Investigating this second issue is another goal of the paper.

Combining both issues.

In the resource allocation problem, we can also be faced with situations were both problems are intertwined and in mutual influence. Especially, we can be asked to enforce all additional solutions encoded by a new constraint that are more permissive than the current network. Locating where this relaxation can be done in the network is not always straightforward. At the same time, the process can be required to have a limited impact on the current model of the problem. Especially, this can occur when the model is a large-scale incomplete one and when we do not want to lose any of all its current possible solutions. More precisely, we might not want the new constraint to impact solutions outside some variables (in particular, variables not mentioned in the additional constraint). A similar issue can be raised in the legal domain example. As the CSP can only be a rough and incomplete approximation of the existing huge set of fiscal rules, the relaxation process (e.g., about the parental benefits) can then required to be local in the sense that it has to be circumscribed to a given set variables and have no impact on solution values for other variables about other fiscal issues implemented in the system.

In the paper, we investigate the three issues successively and propose several methods and algorithms. Experimental results for the last two issues are also provided. As CSP emerge as a technology in the real-word for large-scale applications, we believe that these problems that concern the transformation of constraint networks in order to take evolving specifications into account can only become of increasing interest.

Constraint Networks and MUCs

Definition 1 (Constraint network) A constraint network P is a pair X , C where (1) X = {x 1 , . . . , x n } is a finite set of variables s.t. any variable x i is given a finite domain written dom(

x i ) (2) C = {c 1 , . . . , c m } is a finite set of constraints s.t. every c i ∈ C is defined by a pair (var(c i ), rel(c i )) where • var(c i ) is the set of variables {x i1 , . . . , x in i } ⊆ X oc- curring in c i , • rel(c i ) is a subset of the cartesian product ni j=1 dom(x ij )
of the domains of the variables of var(c i ) representing the tuples of values allowed for c i (i.e., satisfying c i ).

Without loss of generality, we will often interpret sets of variables or constraints as tuples of variables or constraints. Note that rel(c i ) is sometimes given in intentional form. Also, f or(c i ) represents the set of forbidden tuples by c i , which is defined by rel

(c i ) ∪ f or(c i ) = ni j=1 dom(x ij ).
Definition 2 (Instantiation of a constraint network) Let P = X , C be a constraint network. An instantiation A of P assigns to each variable x i of X a value from dom(x i ). A partial instantiation A of P w.r.t. a set Y of variables assigns to each variable y i of Y a value from dom(y i ).

Y ⊆ X is not required: we allow a partial instantiation to instantiate variables not occurring in the network. The tuple of values assigned by A to the variables of Y (resp. to the variables occurring in c) is noted A(Y) (resp. A(c)). Definition 3 (Solution to a constraint network) A solution A to a constraint network P = X , C is an instantiation A of P such that for all c in C we have A(c) belongs to rel(c). We say that A satisfies P and that A is a model of P. When P possesses at least one model, P is said satisfiable. Otherwise P is said unsatisfiable.

Unless explicitly indicated, the constraint network P in which a new constraint c need be inserted is assumed satisfiable. However, so-called MUCs and MSSes concepts that are related to unsatisfiable networks are of importance here. Any unsatisfiable constraint network P = X , C involves at least one MUC (Minimal Unsatisfiable Core), in short core. A MUC is a subset of constraints of C that, at the same time, is unsatisfiable and that is such that every one of its strict subsets is satisfiable. In a dual way, a Maximal Satisfiable Sub-network (MSS) of P = X , C is defined as any satisfiable P = (X , C ) where X (resp. C ) is a subset of X (resp. C) and such that for all c in C \ C , X ∪ var(c), C ∪ {c} is unsatisfiable. Checking whether a constraint belongs to a MUC or not belongs to Σ P 2 [Eiter and Gottlob, 1992]. In the worst case, the number of MUCs can be exponential in the number m of constraints (it is in O(C m/2 m )). Despite bad worst-case complexity results, in many real-life situations, the number of MUCs can remain of a manageable size and both MUCs and MSSes can be computed in realistic time (see for example results in [Grégoire et al., 2007;[START_REF] Grégoire | [END_REF]). One specific well-studied problem about MSS is called WCSP (as Weighted CSP) which consists in delivering one MSS of a constraint network obeying a priority scale between constraints. Each constraint is given a numerical value and constraints with the higher values are preferred candidates for belonging to the resulting MSS. More on MUC and MSS can be found in e.g., [Bakker et al., 1993;Han and Lee, 1999;[START_REF] Jussien | Narendra Jussien and Vincent Barichard. The PaLM system: explanation-based constraint programming[END_REF]Junker, 2001;Petit et al., 2003;Junker, 2004;Hémery et al., 2006;[START_REF] Grégoire | [END_REF][START_REF] Imbert | [END_REF][START_REF] Belov | Accelerating MUS extraction with recursive model rotation[END_REF][START_REF] Janota | cmMUS: A tool for circumscription-based MUS membership testing[END_REF][START_REF] Belov | MUSer2: An efficient MUS extractor[END_REF].

Preserving Partial Solutions

Let us go back to the first issue raised in the introduction, where some given partial solutions to a network P are to be preserved while a new constraint c is to be added. First, let us define a concept of partial solution to a constraint network. Definition 4 (Partial solution to a constraint network) A partial solution A to a constraint network P = X , C w.r.t. a set of variables X is a partial instantiation of P w.r.t. X such that A can be extended into a model of P.

Let X be a set of variables. Consider a set S (P,X ) of partial solutions A to P with respect to X and assume that these partial solutions must be preserved. In the example, the values assigned to variables of X express some possible allocations of resources to the most important tasks so that a global solution involving all tasks could be reached. P should be transformed into a network P such that (1) any solution to P satisfies c, (2) any solution to P extends at least one solution to P, and (3) any element of S (P,X ) can be extended into a solution to P .

Obviously, when c is incompatible with P = X , C in the sense that X ∪ var(c), C ∪ {c} possesses no solution, the above transformation problem exhibits no solution: in the example, the new task cannot be accommodated together with the other ones. Note that even when X ∪ var(c), C ∪ {c} possesses solutions, it might not be possible to handle c in the above way: in the example, this coincides with situations where the new task can only be accommodated in a way that narrows the space of solutions for the most important tasks.

Algorithm 1: Insert-and-Preserve input: P = X , C : a constraint network ; c: the additional constraint ; S (P,X ) : a set of partial solutions of P to preserve ; output: X , C : a constraint network where S (P,X ) is preserved and c inserted ;

C ← C ∪ {c} ; X ← X ∪ var(c) ; 1 foreach A ∈ S (P,X ) do 2 Let c A be the constraint s.t. var(c A ) = var(A) and 3 rel(c A ) = A ; while (X , C ∪ {c A }) is unsat do 4 X , C ← MUC(X , C ∪ {c A }) ; 5 if ∃c ∈ C s.t. c = c A and c = c then 6 C ← C \ {c } ; 7 else return ∅, ∅ ; 8 return X , C ; 9
To some extent, partial solutions appear as a form of integrity constraints that must be taken into account when a constraint network is enriched by some additional constraints. They express sets of values for some given variables leading to solutions that must be kept when the network evolves. In the general case, there is no direct way to implement them as a new constraint in the network so that the structure of the network is preserved as much as possible. For example, a constraint made of the disjunction of the partial solutions to preserve would not ensure that any of its disjuncts remains a partial solution.

Insert-and-Preserve is a direct algorithm to preserve a set S (P,X ) of partial solutions A while inserting c within P. First, c is inserted within P to yield P = X = X ∪ var(c), C = C ∪ {c} . If P is unsatisfiable then no solution exists. Otherwise, each partial solution A from S (P,X ) is considered successively and rewritten as a constraint c A . While X , C ∪ {c A } is unsatisfiable, one MUC is extracted and some of its constraints (different from both c and c A ) is expelled from P . When a MUC just made of both c and A is found then no solution exists. In parallel to the possible high cost of computing enough MUCs to restore satisfiability, one major factor influencing the time-efficiency of the algorithm clearly depends on the number of partial solutions to be preserved. Note that a dual algorithm based on MSSes can be proposed, too.

Handling more Permissive Constraints

A formal definition of more permissive constraints is:

Definition 5 (More permissive constraint) Let P be a constraint network. A constraint c is more permissive than P iff (1) there exists a partial instantiation of P that satisfies c and cannot be extended into a model of P, and (2) every model of P satisfies c.

In the parental benefits issue, a more permissive constraint need to prevail in the network. Formally: Definition 6 (Prevailing constraint) A constraint c prevails in a constraint network P = X , C iff any partial instantiation of P with respect to var(c) that satisfies c can be extended into a model of P.

Thus, relaxing P by a more permissive constraint c must lead to a network P such that any solution to c has been extended into a solution to P .

Definition 7 (Relaxed constraint network) A network P = X , C is a relaxed network of P = X , C by c iff any solution to c can be extended into a solution to P .

Note that requiring all solutions of c to be solutions of P can lead to the existence of additional solutions related to variables outside the scope of c through a domino effect about relaxation within P. Hence, P can exhibit new solutions about variables not occurring in c in addition to those provided by P. For a similar reason, we cannot require in the general case that any solution of P is a solution of P .

Several constraints in P can prevent solutions to c from prevailing in P. A first approach provides the user will a fullfledged explanation of the reasons for this, under the form of the minimal sets of constraints that cause the problem. It is based on MUC-finding algorithms. The idea is as follows.

Whenever a single element of rel(c) is introduced as a new constraint in P and when this leads P to be unsatisfiable, this means that P does not authorize rel(c). Accordingly, we compute and exhibit MUCs in P . A least one constraint per MUC is expelled (or relaxed) from P. This is iterated until P becomes satisfiable. The whole process is then iterated for all elements of rel(c). Thereafter, c is just safely added since we are sure that all its solutions can be now accommodated. When we know which elements of rel(c) cannot be extended into solutions to P, it is sufficient for the procedure to consider these elements, only.

Accordingly, any detected MUC provides a minimal set of constraints preventing an additional solution given by c from prevailing in P. The algorithm Relax-MUC describes the skeleton of an iterative approach finding out and "breaking" in an automatic way MUCs iteratively, until no MUC remains. Note that the depicted algorithm does not return the set of detected MUCs but expels one constraint per MUC and simply delivers the final resulting relaxed constraint network.

A dual algorithm relying on the computation of MSSes was also experimented. However, it often proved less efficient than Relax-MUC, since search does not stop when a falsified constraint is found but only when a given number of falsified constraints is reached.

Combining both Situations

We consider now situations where more permissive constraints must be introduced in P, while some previous partial solutions must be preserved at the same time. Relax-MUC does this job: it enlarges the set of solutions of P and thus preserves all of them, including thus all partial ones.

By expelling constraints Relax-MUC can enlarge the sets of partial solutions related to the variables occurring in the additional constraint c. Note that it can also enlarge sets of partial solutions related to variables not occurring in c. In Algorithm 2: Relax-MUC input: P = X , C : a constraint network ; c: the additional constraint ; output: X , C : a relaxed network of P by c ;

C ← C ; X ← X ∪ var(c) ; 1 foreach t ∈ rel(c) do 2 Let c t s.t. rel(c t ) = { t} and var(c t ) = var(c) ; 3 while X , C ∪ {c t } is unsat do 4 X , C ← MUC(X , C ∪ {C t }); 5 select one constraint c in C s.t. c = c t ; 6 C ← C \ {c } ; 7 C ← C ∪ {c} ; 8 return X , C ;
9 some situations this is acceptable, provided that the user is given the full explanation of this phenomenon. In the resource allocation problem, the manager might need to approve the choice of constraints that are to be expelled or amended to enforce all partial solutions of c. She has to be made aware that by relaxing P in this way, the problem is transformed into a new one that possibly could give rise to new solutions about variables outside var(c).

In other situations, the user might require the more permissive constraint c to have a more limited impact on P: specifically, it must not enlarge the sets of partial solutions that are not directly related to variables occurring in c. Let us go back to the parental benefits issue. As explained in the introduction, P there translates complex fiscal rules. Enforcing a new legal rule relaxing the conditions allowing for the parental benefits could also have an impact on other variables of P, linked to other fiscal issues. However, it might be the case that the new rule has been envisioned as having no impact on any other fiscal issue. In these circumstances, it is not acceptable to allow the possibility of enlarging sets of partial solutions (e.g., increase other possible benefits) outside the relaxed rule. In other words, in some situations, we only want to extend the range of partial solutions for some given variables. Specifically, in the example, these partial solutions must only concern the values for the variable expressing the number of children and the variable expressing whether or not the person is entitled to get the parental benefits. On the contrary, we do not want any other aspects of P to be changed. In technical words, this amounts to enforce a more permissive constraint c, while safely keeping the set of all partial solutions to variables not occurring in c and not enlarging it.

Relax-and-Preserve performs that task. For each variable x i occurring in var(c), all its occurrences in P are renamed by a new additional variable y i (l. 1-7). The idea is then to enforce all partial solutions related to the variables x i 's of var(c) through an additional constraint c new (l. 8). c new also ensures adequate connections between values of x i 's and y i 's. Whenever a partial solution (i.e., a tuple of rel(c)) can be extended into a solution of P, x i 's and y i 's are pairwise assigned identically using this partial solution, and the resulting tuple is added within rel(c new ) (l. 10-12). Whenever the partial solution cannot be extended into a solution to P, a se-ries of correspondences are created between the tuple of values for the variables x i 's that forms the partial solution, and all the tuples of solution values for the variables y i 's in P. The resulting tuples of values for (x 1 , . . . , x m , y 1 , . . . , y m ) are added as new tuples within rel(c new ) (l. 13-15). Note that although the algorithm is depicted as manipulating tuples, c new can be recorded and inserted in intentional form within C (l.16). Accordingly, the additional partial solutions introduced by c do not alter the behavior of the network with respect to any variable occurring in P, except those occurring in c. Let us give an example. Interestingly, the concept of partial solution allows forms of subsumption and equivalence modulo a set of variables between networks to be defined.

Example 1 Let P = X , C a constraint network such that X = {x 1 , x 2 , x 3 } with dom(x 1 ) = dom(x 2 ) = dom(x 3 ) = {1, 2} and C = {(x 1 = x 2 ), (x 1 = x 3 ), (x 2 = x 3 )} and a more permissive constraint c = (x 1 ≤ x 2 ). The transformed network is P = X , C where X = {x 1 , x 2 , x 3 , y 1 , y 2 }, dom(y 1 ) = dom(y 2 ) = {1, 2} and C = {(y 1 = y 2 ), (y 1 = x 3 ), (y 2 = x 3 ), c new } with var(c new ) = {x 1 , x 2 , y 1 , y 2 } and rel(c new ) = {(1, 1, 1, 1), (2, 2, 2, 2), (1, 2, 1, 1), (1, 2, 2, 2)}.
Definition 8 (Subsumption between constraint networks) Let P = X , C , P" = X ", C" and X a set of variables. P subsumes P" modulo X (noted P |= X P") iff for all Algorithm 4: Relax-and-Preserve-Naive input: P = X , C : a constraint network, c a constraint output: X , C : a constraint network s.t. the partial solutions to P w.r.t. X \ var(c) are preserved and c inserted S ← AllSolutions (P) ; 1 Let S (P,X ) be the set of partial solutions obtained from 2 S w.r.t. X \ var(c) ; Let c S (P,X ) be the constraint s.t.

3 var(c S (P,X ) ) = var(S (P,X ) ) and rel(c S (P,X ) ) = {A|A ∈ S (P,X ) } ; C ← {c S (P,X ) , c} ; X ← X ∪ var(c) ; 4 return X , C ; 5 models A 1 of P there exists a model A 2 of P" such that A 1 (X ∩ X ∩ X ") ⊆ A 2 (X ∩ X ").

Definition 9 (Equivalence between constraint networks) Let P = X , C , P" = X ", C" and X a set of variables. P is equivalent to P" modulo X (noted P ≡ X P") iff P |= X P" and P" |= X P .

Accordingly, we have that:

Property 1 When Relax-and-Preserve is run on P = X , C with c being the more permissive constraint to enforce, it delivers P = X , C s.t. P ≡ (X ∩X )\var(c) P and var(c), {c} ≡ var(c) P .

We also provide a naive algorithm Relax-and-Preserve-Naive that computes solutions in extension and delivers them as forming P . As explained earlier, it does not meet our goal since a set of tuples is delivered and the structure of the problem under the form of constraints is lost for further explanations or possible evolutions of the network. Besides, it proved intractable on many instances, as it requires all complete solutions of P to be computed. Note that in its depicted form, Relax-and-Preserve creates a constraint in extension within P : however, this is a local phenomenon within P and it can be rewritten in intention.

Experimental Computational Results

All results below have been obtained on a Quad-core Intel XEON X5550 32Gb. Relax-MUC, Relax-and-Preserve and Relax-and-Preserve-Naive are available from http://www. cril.univ-artois.fr/publications/relax.zip together will the experimental data. They have been run on 986 instances taken from the satisfiable benchmarks of the CSP competitions repository http://cpai.ucc.ie/08/ and http://cpai.ucc.ie/ 09/. In Table 1, a sample of typical results is provided. Timeout ("TO") was set to 30 mins. The full table is also available from http://www.cril.univ-artois.fr/publications/fulltab. pdf. Although Relax-MUC has a slightly different general scope, we compared the three algorithms on the same instances. Columns of Table 1 provide the name of the instances P and their numbers of constraints and variables, successively. Then, it lists the number of variables and tuples of the additional constraint c. c was generated as follows: var(c) was randomly selected as a subset of the variables X from P. The cardinality of this subset ranged from 2 to 4. rel(c) contained all tuples from the cartesian product of the domain of the variables of var(c) that can be extended into solutions of P, together with an additionally 25% of tuples selected randomly amongst the tuples from that cartesian product that cannot be extended into solutions of P. When less than 4 tuples from the cartesian product were already satisfied, no new tuple was added and Relax-MUC did not remove any constraint (an interesting conclusion could however be drawn about the benchmark when all tuples in the cartesian product were satisfied: no variable in any pair of concerned variables does restrict the range of solutions for the other one). Finally, the computing time to deliver P is listed for each method, as well as the number of constraints dropped (#rm) by Relax-MUC and the number of variables and tuples of c new introduced by Relax-and-Preserve. Again, let us stress that the algorithms address different problems and the computational results are just intended to illustrate the actual viability of the approaches. Not surprisingly, Relaxand-Preserve-Naive appears often intractable from a practi-cal point of view. Relax-and-Preserve is more efficient than Relax-MUC for most instances. In this respect, let us stress that Relax-MUC has been built in a way that it should be used in a step-by-step and interactive mode, giving the user the full-fledged knowledge and freedom of decision about the choice of constraints that will be dropped or weakened.

Conclusion

In the CSP-related literature, relaxation is a transformation paradigm to recover satisfiability for unsatisfiable networks [START_REF] Jussien | [END_REF]Georget et al., 1999;[START_REF] Amilhastre | Consistency restoration and explanations in dynamic CSPs-application to configuration[END_REF]Nordlander et al., 2003]. To the best of our knowledge, relaxation and preserving partial solutions have not been studied so far in the context of evolving satisfiable networks. This contribution is an attempt to fill this gap. More generally, we believe that the dynamics of constraint networks is an issue of importance that needs further practical and theoretical studies. As a promising perspective, we also believe that many concepts introduced in this paper could be reused for addressing the problem of merging constraint networks.

Algorithm 3 :C

 3 Relax-and-Preserve input: P = X , C a constraint network ; a constraint c with var(c) = {x 1 , . . . , x m } ; output: P = X , C a constraint network s.t. the partial solutions to P w.r.t. X \ var(c) are preserved and P extends any solution of c ; X ← X ∪ {y 1 , . . . , y m } where dom(y i ) = dom(x i ); c j ) ∩ {x 1 , . . . , x m } = ∅ then 4 ∪ {c j } where c j is obtained from c j by 7 replacing every occurrence of the variable x i by y i for all x i in var(c j ) ∩ {x 1 , . . . , x m }; Let c new s.t. var(c new ) = {x 1 , . . . , x m , y 1 , . . . , y m } ; 8 rel(c new ) ← ∅; 9 foreach t ∈ rel(c) do 10 if t can be extended into a model of P then 11 rel(c new ) ← rel(c new ) ∪ {( t, t)}; new ) ← rel(c new ) ∪ {( t, t 1 )}; 15 C ← C ∪ {c new }; 16 return P ← X , C ; 17

Table 1 :

 1 Relax-MUC, Relax-and-Preserve, Relax-and-Preserve-Naive results

	Instance			constraint c	Relax-MUC		Relax-and-Preserve		Relax-and-Preserve-Naive
	name	#C	#X	#var(c)	#rel(c)	time (secs.)	#rm	time (secs.)	#var(cnew)	#rel(cnew)	time (secs.)
	aim-200-2-0-sat-2-ext	382	200	4	4	104.74	2	0.97	8	4	3.86
	air04	1646	8904	3	8	483.51	0	487.9	6	8	TO
	bdd-21-133-18-78-9-ext	133	21	4	5	TO	-	30.09	8	8	12.82
	bf-0432-007-ext	1943	970	4	10	8.01	3	0.07	8	24	TO
	bmc-ibm-02-08	14493	2810	4	1028	712.09	10	25.01	8	7154	TO
	bqwh-15-106-53-ext	596	106	3	14	29.74	2	0.72	6	56	2.25
	bqwh-15-106-82-ext	600	106	3	35	TO	-	2.35	6	243	11.83
	circ-4-3	764	144	4	13	TO	-	0.23	8	24	5.77
	composed-25-10-20-6-ext	620	105	4	5630	40.97	10	40.45	8	6726920	TO
	crossword-m1c-lex-vg4-7-ext	11	28	3	4459	7.1	4	56.61	6	380451	23.21
	crossword-m1-lex-15-02	944	191	2	187	488.01	6	71.63	4	4075	TO
	david-11	406	87	3	1331	2.32	0	2.07	6	1331	TO
	domino-800-100	800	800	2	2504	32.53	1	28.11	4	194000	1.15
	driverlogw-05c-sat-ext	6173	351	3	21	TO	-	0.67	6	120	TO
	e0ddr2-10-by-5-6	265	50	2	15654	62.95	2	151.37	4	1168500	TO
	fapp01-0200-8	2053	200	2	5019	TO	-	TO	-	-	TO
	frb30-15-1-ext	284	30	2	57	TO	-	1.2	4	112	1.89
	games120-9	638	120	4	6014	18.1	1	19.04	8	1067256	TO
	geo50-20-d4-75-47-ext	383	50	4	159481	TO	-	376.31	8	37264032	TO
	geo50-20-d4-75-88-ext	354	50	4	158878	TO	-	598.69	8	135424854	TO
	graceful-K4-P2	164	24	2	198	107.89	6	17.4	4	5208	72.96
	graph2-f24	2245	400	3	1555	39.46	1	25.38	6	586240	TO
	hanoi-3-ext	5	6	2	14	0	2	0	4	14	0.34
	ii-32e1	1408	444	4	13	3.78	1	12.63	8	24	TO
	jean-10	254	80	4	10000	9.27	0	8.87	8	10000	TO
	jnh210-ext	799	100	4	5	90.85	1	0.12	8	8	188.30
	jnh213-ext	797	100	4	7	1782.02	4	0.04	8	16	3.10
	langford-2-8	128	16	3	1084	0.82	5	0.71	6	80400	1.07
	lard-88-88	3828	88	2	7854	648.9	85	117.41	4	15422176	TO
	mknap-1-0	11	6	4	4	0	7	0	8	4	0.35
	mps-p0033	15	33	4	13	0.62	1	0.15	8	24	3.83
	mps-p0033	15	33	4	13	0.62	1	0.15	8	24	3.83
	myciel5-6	236	47	4	1134	0.63	1	0.71	8	59400	TO
	os-taillard-4-100-6	48	16	2	6289	10.57	4	8.95	4	447696	436.64
	par-16-1-c	1581	634	3	2	TO	-	4.78	6	2	55.39
	primes-10-80-2-7	80	100	2	196	TO	-	27.57	4	196	1.37
	qcp-10-67-5-ext	822	100	2	1	0	0	0.01	4	1	TO
	queens-5-5-5-ext	160	25	4	261	29.02	34	0.13	8	17080	0.91
	qwh-15-106-4-ext	607	106	4	22	TO	-	0.19	8	60	2.54
	qwh-15-106-4-ext	2324	225	4	63	29.97	7	3.25	8	495	3.90
	radar-30-70-4.5-0.95-98	12471	10990	4	16	136.59	0	110.08	8	16	TO
	radar-8-30-3-0-32	64	180	4	199	67.51	2	29.56	8	3600	TO
	ramsey-25-4	2300	300	3	64	1.84	0	1.73	6	64	TO
	rand-2-40-16-250-350-36-ext	250	40	3	2907	1156.32	3	736.78	6	1825747	17.51
	rand-2-30-15-306-230-23-ext	221	30	2	57	1412.45	12	0.76	4	57	3.23
	renault-mod-36-ext	154	111	3	12	2.37	2	0.82	6	40	TO
	route	24492	72	2	51	TO	-	254.35	4	420	TO
	ruler-34-8-a4	350	8	2	307	1741.85	17	6.46	4	612	9.13
	s3-3-3-4	616	228	3	3	TO	-	43.45	6	4	107.92
	scen2-f24	1235	200	3	7084	43.17	1	43.07	6	134254	TO
	scen5	2598	400	2	326	TO	-	20.36	4	972	TO
	series-9	72	17	4	1063	1.14	14	0.56	8	53583	2.54
	ssa-7552-158-ext	1985	1363	3	3	56.42	1	0.04	6	4	TO
	super-jobShop-enddr1-10	845	100	2	6904	123.17	3	401.68	4	7889700	TO
	tsp-20-2-ext	230	61	2	5010	113.07	3	36.67	4	35028	3.23
	will199GPIA-7	7065	701	4	2401	205.43	0	196.62	8	2401	TO

* This work has been partially supported by FWF, NFN Grant S11408-N23 (RiSE), an EC FEDER grant and the Conseil Régional du Nord/Pas-de-Calais.