
| random problems using variable oriented propagation. Best cpu time is in bold. Instance queue dom v wdeg v dom/wdeg frb30-15-1 t 22,3 20,9 29,3 14,1 c 16,5M 11,1M 16,4M 7,5M r 105626 70924 102724 46727 n 3863 3858 4138 2499 frb30-15-2 t 84,9 29,7 118,9 95 c 45,7M 21,8M 90M 68,9M r 311040 149119 624360 472124 n 15457 7935 25148 24467 frb35-17-1 t 125,8 193,7 118 250,9 c 93,9M 144M 89,7M 180,9M r 533694 836462 514258 1,03M n 18587 40698 19167 50611 rand-2-30-15 t 1240 74,4 98 108,1 c 114,5M 53M 72,5M 78,1M r 922251 443792 602582 642665 n 28725 19846 20192 28766 geo50-20-d4-75-2 t 226,1 401,8 34,8 39,5 c 191,8M 310,3M 28,2M 28,8M r 778758 1,3M 117241 124163 n 20069 60182 3735 5484   |
| |

structure do not in general consist of hard local subproblems. Thus, different decisions on which variables to revise first can lead to different DWO-revisions being discovered, which in turn can guide search tree to different parts of the search space with unpredictable results. Note that for structured problems only very few possible DWO-revisions are present in the revision list at each point in time, while for random ones there can be a large number of such revisions.

5.5. Dependency of conflict-driven heuristics on the revision ordering As we showed in the previous section, *dom/wdeg* is strongly dependent on the order in which the revision list is constructed and updated during constraint propagation. Looking at the results in Tables 9 - 12, we can see that there are cases where the differences in cpu performance between dom and v *dom/wdeg* can be up to 5 times. Hence, when *dom/wdeg* is used as DVO heuristic, we must carefully select a good revision ordering using for example one of the heuristics we have proposed in Section 5.3. In contrast, the conflict-driven DVO
heuristics "*alldel*" and "*fully assigned*" are not as amenable to the selection of revision ordering. To better illustrate this statement, let us consider the following example.

Example 2. Assume that we want to solve a CSP (*X, D, C*) with X: {x1, x2, x3, x4}, by using two different revision ordering heuristics R1 (lexicographic ordering) and R2 (reverse lexicographic ordering). For the revision of each xi
∈ X, we assume that the following hypotheses are true: a) The revision of x1 is fruitful and it causes the addition of the variable x3 in the revision list. b) The revision of x2 is fruitful and it causes the addition of the variable x4 in the revision list. c) The revision of x4 is fruitful and it causes the addition of the variable x3. We also assume the a DWO can only occur either d) in x4 after a sequential revision of x2 and x3 or e) in x3 after a sequential revision of x4 and