Arc-Consistency in Dynamic CSPs Is No More Prohibitive Romuald Debruyne LIRMM 161 rue Ada F-34392 Montpellier Cedex 5 - France
[email protected]
Abstract Constraint satisfaction problems (CSPs) are widely used in Articial Intelligence. The problem of the existence of a solution in a CSP being NP-complete, ltering techniques and particularly arc-consistency are essential. They remove some local inconsistencies and so make the search easier. Since many problems in AI require a dynamic environment, the model was extended to dynamic CSPs (DCSPs) and some incremental arc-consistency algorithms were proposed. However, all of them have important drawbacks. DnAC-4 has an expensive worst-case space complexity and a bad average time complexity. ACjDC has a non-optimal worst-case time complexity which prevents from taking advantage of its good space complexity. The algorithm we present in this paper has both lower space requirements and better time performances than DnAC-4 while keeping an optimal worst case time complexity.
1. Introduction Constraint satisfaction problems (CSPs) occur widely in Articial Intelligence. They have shown their eciency in representing and solving problems in many areas such as design, scene labeling, planning, scheduling, temporal reasoning and natural language parsing. Their resolution being a NP-complete problem, ltering techniques are essential. They eliminate some local inconsistencies before or during the search, and so reduce the search space without modifying the set of solutions. Arc-consistency is the most used of these techniques 8]9]. It removes some values that cannot belong to any solution. The formalism was extended to dynamic CSPs (DCSPs) 5] to deal with applications that need to be expressed in a dynamic environment. For example,
to design peptide synthesis plans 7] or to create timetables, we may add constraints to further specify the problem or relax constraints when there are no more solutions. Although many problems are intrinsically dynamic, DCSPs are almost no more studied. However, incremental methods for DCSPs are essential. The determination of the secondary structures of RNA sequences shows the need of ecient arc-consistency algorithms for DCSPs 6]. This problem requires a strong interaction with the biologist. It is impossible to perform a complete search of solutions at each modication of the network because of its huge size. Then, each time the biologist adds or retracts a constraint, a simple arc-consistency step is performed, which in this application appears to be almost always sucient to ensure the existence of solutions in the network. A complete search is performed once the biologist has designed an acceptable conguration of the problem. Arc-consistency algorithms for static CSPs can easily be adapted to add constraints incrementally. However, they are ineective to relax a constraint because they are not able to determine the set of values that must be restored in the domain. So, to remove a constraint with these algorithms we have to reset the domains and add all the remaining constraints on the initial CSP. To avoid this drawback, Bessiere had proposed DnAC-4 2]. This arc-consistency algorithm stores a justication for each deleted value. It uses these justications to determine the set of values that have been removed because of the relaxed constraint and so can process relaxations incrementally. DnAC-4 being an adaptation of AC-4 10], it inherits its bad space and time complexities. Indeed, in spite of its optimal worstcase time complexity, AC-4 has a bad average running time 12] and its worst-case space complexity is O(ed2 + nd). Neveu and Berlandier proposed another approach to maintain arc-consistency in DCSPs. Their algorithm
called ACjDC 1] is based on the non-optimal arcconsistency algorithm AC-3 and needs no costly data structure. It has a really good space complexity but it is less ecient than DnAC-4 and its O(ed3 ) worst case time complexity prevents its use on large DCSPs. AC-4 performing more work than necessary to enforce arc-consistency, Bessiere has proposed AC-6 3] which works out the drawbacks of AC-4 while keeping an optimal worst case time complexity. The algorithm DnAC-6 presented in this paper adapts the ideas of AC-6 to DCSPs by using justications similar to those of DnAC-4. After some recalls on DnAC-4 in section 3 and on ACjDC in section 4, section 5 presents DnAC-6. Section 6 contains an experimental evaluation of DnAC-4 and DnAC-6. A conclusion is given in section 7.
2 Denitions and notations A \static" binary CSP P = (X dom C ) is a set X = f i j : : : g of n variables, each taking value in its respective nite domain domi domj : : : elements of dom and a set C of e binary constraints. d is the size
of the largest domain. A binary constraint Cij is a subset of the cartesian product domi domj that denotes the compatible pairs of values for i and j. We note Cij (a b) = true to specify that ((i a) (j b)) 2 Cij . We then say that (j b) is a support of (i a) on Cij . With each CSP we associate a labeled directed graph called constraint graph. In this graph nodes represent variables and there is an arc between i and j if a constraint Cij exists. For each arc (i j) labeled by Cij there exists an arc (j i) labeled by Cji such that for each a 2 domi and each b 2 domj Cij (a b) () Cji(b a). Two variables are not connected if there is the universal constraint between them (all the pairs of values are allowed). A value a for i is viable i it has at least one support in the domain of each variable j linked to i. The domain dom of P = (X dom C ) is arcconsistent if each value of dom is viable. The maximal arc-consistent domain of P = (X dom C ) is the union of all the arc-consistent domains included in dom. The aim of arc-consistency algorithms is to compute the maximal arc-consistent domain. A dynamic CSP (DCSP) 5] is a sequence of static CSPs P0 : : : P P+1 : : : each resulting from a restriction (a constraint is added) or a relaxation (a constraint is retracted) in the preceding one. Therefore, if we have P = (X dom C) P+1 is (X dom C+1) with C+1 = C Cij where Cij is a constraint. We assume the sequence to begin by P0 = (X dom ). In the following sections dom is
the initial domain dened by the user and D is the current domain. The algorithms studied in this paper keep in D the maximal arc-consistent domain of P that they compute.
3 DnAC-4 3.1 Introduction Arc-consistency algorithms for static CSPs need only few modications to become incremental for the addition of constraints. Nevertheless, they are unable to identify values which have to be put back during a relaxation. To relax a constraint with these algorithms it is necessary to restart the additions of all the remaining constraints on the initial problem P0. DnAC-4 2] stores the justication of each value deletion in order to be able to retract a constraint incrementally.
3.2 Bases of the algorithm To enforce arc-consistency we have to delete values that are not viable. As AC-4 10], DnAC-4 detects these values by counting the number of supports that the values have on each constraint. For each arc-value pair (i j) a], counter(i j) a] is the number of supports that (i a) has on Cij in D. A value has to be removed if there exists a constraint Cij with counter(i j) a] = 0. To update these counters, for each arc-value pair (i j) a] DnAC-4 stores in Sija the list of values of domj that are supported by (i a). These lists of values allow to determine counters that have to be updated when a value is removed or restored in D. These lists have another interest. DnAC-4 makes constraint checks only to create these lists of supported values. Each constraint check is therefore realized only once. These data structures inherited from AC-4 do not suce to process a relaxation eciently. Therefore, DnAC-4 justies each excluded value by the rst constraint met on which the value has no support. We have justifi a] = j if and only if (i a) has been removed because counter(i j) a] = 0. These justications allow to determine values whose deletion is due to the relaxed constraint. For this, they have to verify the following property :
Denition 3.1 A set of justications is
well-
i in each set E of retracted values, there exists a value (i a) with justifi a] = j such that no value of j compatible with (i a) on Cij is in E . founded
This property is true if justications have no \cycle". For example, if Cij (a b) is true, we cannot have
justifi a] = j and justifj b] = i. Indeed, justifi a] = j implies that (j b) was removed from D before (i a). Consequently, Cij cannot justify the deletion of (j b) since (i a) was still in the current domain. In order to keep the justications well-founded, DnAC-4 retracts a constraint in two steps. First, values whose deletion is directly or indirectly due to the relaxed constraint are put back in D. Then, values that have not at least one support on each constraint are removed. Justications could also be used to identify some of the constraints which are responsible of the deletion of a set of values (explanation of inconsistencies). We do not intend to deal with this last use in this paper but it is a real advantage.
3.3 Main features In problems composed of tight constraints (few pairs of values are allowed contrary to loose constraints), the lists of supported values are short and so the updates of counters are ecient. Nevertheless, the data structure S is very costly in space. It is responsible of the O(ed2 + nd) worst-case space complexity of the algorithm. The worst-case time complexity of DnAC-4 is O(ed2). This complexity is optimal but DnAC-4 inherits the bad average time complexity of AC-4. Indeed, maintaining the number of supports that values have on each constraints is an expensive work. Furthermore, the update of counters is not limited to values of the current domain. Consequently, the lists of supported values contain values which are not in D. DnAC-4 continues to work on excluded values to anticipate an hypothetic future relaxation. This work is maybe useless. Moreover, having to deal with dom instead of only processing values of D leads to low performances, especially when many values have already been deleted.
4.2 Bases of the algorithm The main idea is to perform relaxations using no other global data structure than those used for the representation of the problem. So, restrictions do not have to store data to improve future relaxations. Any arcconsistency procedure can perform restrictions providing that no global data structure is used. AC-4 and AC-6 would require an update of their data during relaxations. The values which are not viable are so removed by the classic AC-3 procedure 8]. As in DnAC-4, ACjDC relaxes a constraint Ckm in two steps. First, the set of values that have been ruled out because of the relaxed constraint is over-estimated. ACjDC begins to create this approximation by determining the values removed from Dk and Dm that have no support on Ckm (estimation of the values whose deletion is directly due to Ckm). Then, these value restorations are propagated to the other variables. The deleted values which have a support in the approximation are added in turn in the superset. In the second step, a ltering procedure based on AC-3 is used to remove from the estimation the values which are not arc-consistent with respect to the relaxed problem.
4.3 Main features ACjDC has better time performances than DnAC-4 only on small problems 4]. Indeed, ACjDC has a non-optimal worst-case time complexity of O(ed3 ) and so its performances decrease quickly when d grows. Moreover, ACjDC has bad performances on relaxations because of its rough estimation of the values that have to be restored. This superset contains many values which have not been removed because of Ckm . Since these values are not viable, their restoration is useless and furthermore it has to be undone by AC-3. ACjDC has a worst-case space complexity of O(e + nd). However, its O(ed3) worst-case time complexity prevents its use on large DCSPs and so reduces the interest of its space complexity.
4 AC DC
5 DnAC-6
4.1 Introduction
5.1 Introduction
When they realized ACjDC 1] , Neveu & Berlandier wanted to maintain arc-consistency in DCSPs with a better space complexity. However, the very good space complexity of ACjDC has a cost : an O(ed3) worst-case time complexity.
If DnAC-4 is inecient it is because it performs more work than necessary. It maintains the number of supports that each value has on each constraint. Let us remind that proving the arc-consistency of a domain consists in making sure that each value has at least one support on each constraint.
j
AC-6 3] takes advantage of this remark. It considers a total ordering on values. In order to determine if a value (i a) is viable it looks for the smallest support that this value has in D on each constraint Cij . This support is called the current support of (i a) on Cij . If we remove a value b from Dj , we have to look for another support in Dj for all values that b was currently supporting. Nevertheless, it is useless to check values smaller than b since it was the smallest support. DnAC-6 is an algorithm maintaining arc-consistency in DCSPs that draws prot from this idea. Its space complexity is in O(ed + nd) and its time performances are better than those of DnAC-4.
5.2 Bases of the algorithm The idea of AC-6 cannot directly be used in a DCSP. Indeed, constraints can be retracted. If we used a total ordering on values, we should have to update current supports each time a smaller support would be restored in D. To adapt the idea of AC-6, DnAC-6 uses presenti] and absenti] lists that contain respectively values of Di and values of domi nDi . For each value (i a) and each constraint Cij , DnAC-6 looks for the smallest support of (i a) in presentj]. Furthermore, if a value is put in presenti] or in absenti] it is placed at the end of the list. Thus, if we have to nd a new support for a value, only the successors of the current support have to be tested. We also use a table M of booleans to keep track of which values are in the current domain or not ( Mi a] = true () a 2 Di ). We use the following constant time functions and procedures to handle the current domain. rst(i) and last(i) return respectively the rst and the last value of presenti] if the list is not empty and return nil otherwise. If a 2 presenti]n last(i), next(i a) returns the successor of a in presenti] and returns nil otherwise. If a 2 absenti], restore((i a) D) assigns true to Mi a], removes a from absenti] and put a at the end of presenti]. If a 2 presenti], remove((i a) D) assigns false to Mi a], removes a from presenti] and put a at the end of absenti]. DnAC-6 uses a set of lists. The list Sjib contains values of domi for which b is the current support on Cij . For each value (i a) in D, DnAC-6 looks for the rst support b it has in presentj] for all Cij 2 C . If the search is a success, a is put in Sjib, otherwise (i a) is not viable. When a value (j b) is removed from D, values of Sjib \ D lose their current support on Cij . So,
for all Cij 2 C we have to make sure that each value in Sjib \ D is still viable. 1 We use justications in a similar way as in DnAC-4. justifi a] = j i (i a) was removed from D because it has no support in D on Cij . If (i a) 2 D, justifi a] = nil. A queue RL allows to propagate additions of values. (i j) a] is put in RL if justifi a] = j and we are retracting Cij or if justifi a] = j and a support of (i a) on Cij has been restored in D. In other words, (i j) a] is in RL if we have to restore (i a) because justifi a] can no longer justify its deletion. A stack SL controls the deletion of values along the constraints. (i j) a PofSupport LastTested] is placed in SL if (i a) 2 D has no support on Cij . The boolean PofSupport is true if it is possible that a support of (i a) has been restored in Dj after the addition of (i j) a PofSupport LastTested] in SL. During a restriction, P ofSupport is always false. On the other hand, if (i j) a PofSupport LastT ested] is placed in SL during the propagation of additions of values, PofSupport is true. In this case, LastT ested is the last value checked during the fruitless research of a support of (i a) on Cij if presentj] is not empty, and nil otherwise. Consequently, when LastT ested is dierent of nil, if a support of (i a) has been put back in Dj , it is a successor of LastTested in presentj]. Predecessors have already been tested. As long as (i j) a true b] is in SL, b has to remain in presentj]. Indeed, if b is no more in the current domain of j, we cannot determine which values in presentj] have already been tested during the research of a support of (i a) on Cij . It is for this reason that SL has to be a stack. Using a \Last In, First Out" order, this drawback is avoided. If P ofSupport = true and LastTested = nil, all values in presentj] can be supports of (i a).
5.3 The algorithm First of all, the procedure Init has to be called. It places all values of dom in D with nil as justication. DnAC-6 (see g.1) uses the procedure NextSupport to nd a new current support. NextSupport((i j) a b supported) is called with a 2 presenti]. If b 2 presentj], this procedure looks for the rst support c of (i a) in presentj] that is b or a successor of b. If the search is a success, NextSupport adds a in Sjic (c is the new current 1 Contrary to the version of 4], the lists of supported values can contain deleted values. When we exclude a value a from Di we do not remove it from the Sjib lists. This update required an additional data structure and it is expensive to clean up systematically these lists when it may be useless.
procedure Init() 1 for (i a) 2 dom do 2 put (i a) in D 3 justif ia] nil procedure Add( Cij : constraint) 1 C C f Cij g 2 SL 3 Init-Add((i j ) SL) 4 Init-Add((j i) SL) 5 Propag-Suppress(SL) procedure Init-Add( (i j ) : arc var SL : stack ) 1 for b 2 present j ] do Sjib 2 for a 2 present i] do 3 NextSupport((i j ) a rst(j ) supported ) 4 if not supported then 5 push (i j ) a false nil] in SL procedure Propag-Suppress( var SL : stack ) 1 while SL 6= do 2 (i j ) a PofSupport LastTested] pop(SL) 3 if (i a) 2 D then 4 supported false 5 if PofSupport then 6 if LastTested 6= nil then 7 b next(j LastTested) 8 else 9 b rst(j ) 10 NextSupport((i j ) a b supported) 11 if not supported then 12 for k= Cki 2 C do 13 for b 2 (Sika \ Dk ) do 14 NextSupport((k i) b next(i a) support) 15 if not support then 16 push (k i) b false nil] in SL 17 Sika 18 remove((i a) D) 19 justif i a] j
procedure NextSupport( (i j ) : arc a b : value var supported : boolean ) 1 while b 6= nil do 2 if Cij (a b) then 3 Sjib Sjib fag 4 supported true 5 return 6 else 7 b next(j b) 8 supported false procedure Relax( Ckm : constraint) 1 SL 2 Init-Propag-Relax( Ckm SL) 3 Propag-Suppress(SL) procedure Init-Propag-Relax( Ckm : constraint var SL : stack ) 1 RL 2 for a 2 absent k] do 3 if justif k a] = m then 4 put (k m) a] in RL justif k a] nil 5 for b 2 absent m] do 6 if justif m b] = k then 7 put (m k) b] in RL justif m b] nil 8 remove Ckm from C and destroy S structure between k and m 9 while RL 6= do 10 pick (i k) a] from RL 11 restore((i a) D) 12 for j 6= k= Cij 2 C do 13 supported false 14 NextSupport((i j ) a rst(j ) supported) 15 for c 2 absent j ] do 16 if justif j c] = i then 17 if Cij (a c) then 18 justif j c] nil 19 put (j i) c] in RL 20 Sija Sija fcg 21 if not supported then 22 push (i j ) a true last(j )] in SL
Figure 1. DnAC-6. support of (i a) on Cij ) and assigns true to supported. If no such support is found or if NextSupport is called with b = nil, NextSupport assigns false to supported.
5.3.1 The restrictions. To add a constraint Cij , the
procedure Add (g.1) begins by calling Init-Add. This procedure uses NextSupport to search for a support for each value in Di and Dj on Cij . Since it is a new constraint, the values of i and j have no current support on it and the search begins with the rst value of presentj] and presenti] respectively. Obviously, if (i a) (resp. (j b)) has no support on Cij in the current domain, it has to be removed with Cij as justication and so (i j) a false nil] (resp. (j i) b false nil]) is pushed on SL. Then, Propag-Suppress uses SL to delete values that are no longer viable because of Cij , and to propagate consequences of these suppressions. For each (i j) a false nil] in SL with (i a) 2 D, PropagSuppress looks for a new current support for each value that (i a) is currently supporting and removes (i a) from D with j as justication. If (i a) was the unique
support of (k b) in D, (k i) b false nil] is pushed on SL since Cki can justify the deletion of (k b). By this propagation we make sure that each value keeps at least one support in D on each constraint. Therefore, the resulting current domain is arcconsistent. Moreover, this domain is the maximal arcconsistent domain since a value is deleted only if there is a justication for its suppression i.e. a constraint on which the value has no support. Remark: During a restriction, no value is restored. Each (i j) a PofSupport LastTested] in SL has PofSupport = nil and so lines 5 to 10 of PropagSuppress are useless.
5.3.2 The relaxations. As in DnAC-4, relaxations
are made in two steps to keep the justications wellfounded. Init-Propag-Relax (g.1) begins by adding in RL the arc-value pairs (k m) a] (resp. (m k) b]) that correspond to values (k a) (resp. (m b)) justied by Ckm. Since we are retracting Ckm , these values lose the justication of their suppression. Then, for each
(i k) a] in RL, Init-Propag-Relax restores a in Di and makes sure that (i a) is viable. For each j linked to i with j 6= k, it looks for the rst support b of (i a) in presentj]. If this search is a success, a is added to Sjib , otherwise (i j) a true last(j)] is pushed on SL since Cij can justify the suppression of (i a) if no support of (i a) is added in Dj . Moreover, the restoration of (i a) is propagated. If (i a) is compatible with a value (j c) removed because of Cij , c is added in Sija and (j i) c] is placed in RL. Indeed, in such a case Cij cannot justify the deletion of (j c) and since this value is perhaps viable, we have to restore it. At the end of Init-Propag-Relax, the values that were retracted because of Ckm have been restored. Propag-Suppress is then called to make sure that restored values are viable. Contrary to restrictions, (i j) a PofSupport LastT ested] 2 SL does not mean that (i a) has no support on Cij in D. Indeed, (i j) a PofSupport LastTested] can have been pushed by Init-Propag-Relax during the phase of restoration of values. Therefore, when PropagSuppress pops (i j) a PofSupport LastTested] with PofSupport = true, it has to test if a support of (i a) on Cij has been restored in Dj . If LastTested 6= nil, only the successors of LastTested have to be checked because Init-P ropag-Relax has already tested the other values. If the search is fruitless or if PofSupport = false, (i a) must be deleted with Cij as justication. In this case, Propag-Suppress looks for another current support for each value (k b) that (i a) supports and if (i a) is the unique support of (k b) on Cki in D, (k i) b false nil] is pushed on SL.
5.4 Complexity Structures D and justif have a size of O(nd). Since in the worst case there is 2ed arc-value pairs, the number of current supports is bounded by 2ed and the size of the lists of supported values is in O(ed). The worstcase space complexity of DnAC-6 is so in O(ed + nd). The inner loop of Init-Add and Propag-Suppress is a call of NextSupport. This procedure looks for a support which is a successor of the current support in the list of present values. Therefore, for each arc-value pair, we check at most d values. The worst-case time complexity of a restriction is then in O(ed2 ). Let us show that the worst-case time complexity of a relaxation is also in O(ed2). As we have seen above, Propag-Suppress requires a time in O(ed2) and so we only have to examine Init-Propag-Relax. The initialisation step of Init-Propag-Relax is in O(d).
An arc-value pair (k m) a] can be put in RL only if justifk a] = m (lines 3, 6 and 16). Furthermore, when (k m) a] is added to RL, nil is assigned to justifk a] (lines 4, 7 and 18). Therefore, a value (i a) is put in RL at most once. For each arc-value pair (i k) a] in RL, (i a) is restored and for all j 6= k linked to i, we both search for a support of (i a) on Cij and determine values of absentj] which have to be put back in Dj because of the restoration of (i a). Therefore, in the worst case all the values have to be restored, the nd values are put in RL and for each of them we check O(d) values on each adjacent variable. The resulting time complexity of relaxations is so O(ed2 ).
6 Experimental results In this section, we use DnAC-4 as reference, ACjDC having lower performances 4]. DnAC-4 and DnAC-6 have been implemented using the same language and benchmarks have been run on the same computer. We call \number of constraint checks" the rst measure of performances. It represents in fact the number of classical constraint checks plus the number of list checks. This measure is well-adapted for DnAC-4 which makes constraint checks only to initially build its lists of supported values. The other measure used is cpu time.
6.1 The zebra problem The well known zebra problem 11] has been adapted to become a DCSP. In its static version, this problem is represented by 25 variables, each having 5 possible values and a set of constraints corresponding to 15 assertions. 6 other constraints have been added, each of the three last making the problem inconsistent. The DCSP used is inspired by the users' behavior. Constraints are added when the problem has many solutions and conversely, some constraints are removed when there is no more solutions. More precisely, line 1 (There are ve houses, each of dierent color and inhabited by men of dierent nationalities, with dierent pets, drinks and cigarettes.) being the basis of the problem, constraints corresponding to this line are rst added and never removed. At each step of the generation, if the DCSP has no empty domains, we add one of lines 2-21 which is not yet in the DCSP. Otherwise, a constraint is removed. For both restrictions and relaxations, the constraint is chosen with an uniform probability among the possible constraints. The process stops 40 modications after the rst relaxation.
Figure 2. The zebra problem and the additional assertions. DnAC-4 to DnAC-6 constraint check ratio DnAC-4 to DnAC-6 cpu time ratio
Execution 2,96
Restriction 2,93
Relaxation 2,96
2,1
1,75
2,24
Table 1. Results on the zebra problem. The results in table 1 are mean values obtained on 500 instances. All the restrictions of the execution (even those preceding the rst relaxation) have been considered to produce the mean values of the second column. The results are easy to read. DnAC-6 performs 3 times less constraints checks and list checks than DnAC-4 and is twice faster on this problem. We note that the ratio of cpu time required for an execution is close to that of relaxations. The same remark can be made on the number of constraint checks. This is explained by the fact that a relaxation requires almost 5 times more cpu time, constraint checks and list checks than a restriction. The results for a complete execution are so strongly in uenced by the performances on relaxations.
6.2 Randomly generated problems In order to study the behavior of DnAC-6 on a large spectrum of DCSPs, we used randomly generated problems. Restrictions and relaxations can be studied with a generator of static CSPs. P is generated and we
DnAC-4 to DnAC-6 cpu time ratio 12
p2=15% p2=50%
Execution
10
p2=85%
8
12 10
p2=15% p2=50% p2=85%
4
2
2
5
7
10 15 20 25 30 35 40 45 50 Size of initial domains p2=15% p2=50% p2=85%
Restriction
6 5 4 3 2 1
5
14 12 10 8 6 4 2 0
14
6
4
0
DnAC-4 to DnAC-6 constraint check ratio
8
6
0
Relaxation
1. There are ve houses, each of dierent color and inhabited by men of dierent nationalities, with dierent pets, drinks, and cigarettes. 2. The Englishman lives in the red house. 3. The Spaniard owns a dog. 4. Coee is drunk in the green house. 5. The Ukranian drinks tea. 6. The green house is immediatly to the right of the ivory house. 7. The Old-Gold smoker owns snails. 8. Kools are being smoked in the yellow house. 9. Milk is drunk in the middle house. 10. The Norwegian lives in the rst house on the left. 11. The Chestereld smoker lives next to the fox owner. 12. Kools are smoked in the house next to the house where the horse is kept. 13. The Lucky-Strike smoker drinks orange juice. 14. The Japanese smokes Parliament. 15. The Norwegian lives next to the blue house. 16. Milk is drunk in the red house. 17. Orange juice is drunk in the ivory house. 18. The Ukranian owns the horse. 19. Orange juice is drunk in the blue house. 20. Coee is not drunk in the house where the zebra is kept. 21. The Spaniard smokes Kools.
5
10 15 20 25 30 35 40 45 50 Size of initial domains
0
8 7 6 5 4 3 2 1 0
5
p2=15% p2=50% p2=85%
5
18 16 14 12 10 8 6 4 2 0 10 15 20 25 30 35 40 45 50 5 Size of initial domains
p2=15% p2=50% p2=85%
10 15 20 25 30 35 40 45 50 Size of initial domains
10 15 20 25 30 35 40 45 50 Size of initial domains p2=15% p2=50% p2=85%
10 15 20 25 30 35 40 45 50 Size of initial domains
Figure 3. Comparison of DnAC-6 and DnAC-4 on randomly generated problems. only look at the cost of the transition from P to P+1 . However, it is dicult to deduce from this snapshots the eective performances on a complete execution which involves many restrictions and relaxations. All transitions leading to P have to be studied. The DCSPs used are composed of both randomly generated constraints and arithmetic relations f
