Preserving Partial Solutions While Relaxing Constraint Networks

1 Introduction

The study of CSPs (Constraint Satisfaction Problems) has long been a fertile research domain in Artificial Intelligence (see for example [Milano, 2012; Beldiceanu et al., 2012; Pesant, 2012; Rossi et al., 2006] 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.

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

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.

2 Constraint Networks andMUCs

Definition 1 (Constraint network) A constraint network P is a pair 〈X , C〉 where

(1) X = {x1, . . . , xn} is a finite set of variables s.t. any variable xi is given a finite domain written dom(xi)

1. C = {c1, . . . , cm} is a finite set of constraints s.t. every ci ∈ C is defined by a pair (var(ci), rel(ci)) where
2. var(ci) is the set of variables {xi1 , . . . , xini } ⊆ X occurring in ci,
3. rel(ci) is a subset of the cartesian product ∏ni j=1 dom(xij ) of the domains of the variables of var(ci) representing the tuples of values allowed for ci (i.e., satisfying ci).

Without loss of generality, we will often interpret sets of variables or constraints as tuples of variables or constraints. Note that rel(ci) is sometimes given in intentional form. Also, for(ci) represents the set of forbidden tuples by ci, which is defined by rel(ci) ∪ for(ci) = ∏ni j=1 dom(xij ).

Definition 2 (Instantiation of a constraint network) Let P = 〈X, C〉 be a constraint network. An instantiation A of P assigns to each variable xi of X a value from dom(xi). A partial instantiation A of P w.r.t. a set Y of variables assigns to each variable yi of Y a value from dom(yi).

• 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. AMUC 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 ΣP2 [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´egoire et al., 2007; 2008]). 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; Jussien and Barichard, 2000; Junker, 2001; Petit et al., 2003; Junker, 2004; H´emery et al., 2006; Gr´egoire et al., 2008; Marques-Silva and Lynce, 2011; Belov and Marques-Silva, 2011; Janota and Marques-Silva, 2011; Belov and Marques-Silva, 2012].

3 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 cA be the constraint s.t. var(cA) = var(A) and 3 rel(cA) = A ; while (X ′ , C ′ ∪ {cA}) is unsat do 4 〈X ′ , C ′′ 〉 ← MUC(X ′ , C ′ ∪ {cA}) ; 5 if ∃c′′ ∈ C ′′ s.t. c′′ ̸= cA 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 cA. While 〈X ′ , C′ ∪{cA}〉 is unsatisfiable, one MUC is extracted and some of its constraints (different from both c and cA) 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.

4 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.

5 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 ct s.t. rel(ct) = {⃗t} and var(ct) = var(c) ; 3 while 〈X ′ , C ′ ∪ {ct}〉 is unsat do 4 〈X ′ , C ′′ 〉 ← MUC(X ′ , C ′ ∪ {Ct}); 5 select one constraint c′′ in C ′′ s.t. c′′ ̸= ct ; 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 xi occurring in var(c), all its occurrences in P are renamed by a new additional variable yi (l. 1-7). The idea is then to enforce all partial solutions related to the variables xi's of var(c) through an additional constraint cnew (l. 8). cnew also ensures adequate connections between values of xi's and yi's. Whenever a partial solution (i.e., a tuple of rel(c)) can be extended into a solution of P, xi's and yi's are pairwise assigned identically using this partial solution, and the resulting tuple is added within rel(cnew) (l. 10-12). Whenever the partial solution cannot be extended into a solution to P, a series of correspondences are created between the tuple of values for the variables xi's that forms the partial solution, and all the tuples of solution values for the variables yi's in P. The resulting tuples of values for (x1, . . . , xm, y1, . . . , ym) are added as new tuples within rel(cnew) (l. 13-15). Note that although the algorithm is depicted as manipulating tuples, cnew 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.

Example 1 Let P = 〈X, C〉 a constraint network such that X = {x1, x2, x3} with dom(x1) = dom(x2) = dom(x3) = {1, 2} and C = {(x1 = x2), (x1 = x3), (x2 = x3)} and a more permissive constraint c = (x1 ≤ x2). The transformed network is P ′ = 〈X ′ , C ′ 〉 where X = {x1, x2, x3, y1, y2}, dom(y1) = dom(y2) = {1, 2} and C = {(y1 = y2), (y1 = x3), (y2 = x3), cnew} with var(cnew) = {x1, x2, y1, y2} and rel(cnew) = {(1, 1, 1, 1), (2, 2, 2, 2), (1, 2, 1, 1), (1, 2, 2, 2)}.

Algorithm 3: Relax-and-Preserve

10

11 12 13 14 15

input: P = 〈X , C〉 a constraint network ; a constraint c with var(c) = {x1, . . . , xm} ; 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 ∪ {y1, . . . , ym} where dom(yi) = dom(xi); 1 C ′ ← ∅; 2 foreach cj ∈ C do 3 if var(cj) ∩ {x1, . . . , xm} = ∅ then 4 C ′ ← C ′ ∪ {cj}; 5 else 6 C ′ ← C ′ ∪ {c′j } where c′j is obtained from cj by 7 replacing every occurrence of the variable xi by yi for all xi in var(cj) ∩ {x1, . . . , xm}; Let cnew s.t. var(cnew) = {x1, . . . , xm, y1, . . . , ym} ; 8 rel(cnew) ← ∅; 9 foreach ⃗t ∈ rel(c) do if ⃗t can be extended into a model of P then rel(cnew) ← rel(cnew) ∪ {(⃗t, ⃗t)}; else foreach ⃗t1 ∈ S(P,X) do rel(cnew) ← rel(cnew) ∪ {(⃗t, ⃗t1)}; C ′ ← C ′ ∪ {cnew}; return P ′ ← 〈X ′ , C ′ 〉 ;

Interestingly, the concept of partial solution allows forms of subsumption and equivalence modulo a set of variables between networks to be defined.

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 cS(P,X) be the constraint s.t. 3 var(cS(P,X) ) = var(S(P,X)) and rel(cS(P,X) ) = {A|A ∈ S(P,X)} ; C ′ ← {cS(P,X) , c} ; X ′ ← X ∪ var(c) ; 4 return 〈X ′ , C ′ 〉; 5

models A1 of P ′ there exists a model A2 of P" such that A1(X ∩ X ′ ∩ X") ⊆ A2(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-PreserveNaive 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.

6 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 https://www.cril.univartois.fr/∼mazure 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. Time-out ("TO") was set to 30 mins. The full table is also available from https://www.cril.univ-artois.fr/∼mazure. 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 cnew 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, Relax-and-Preserve-Naive appears often intractable from a practical point of view. Relaxand-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 [Jussien and Boizumault, 1996; Georget et al., 1999; Amilhastre et al., 2002; 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.