It is well known that the order in which the elements of the revision list are processed affects the overall cost of the search [38, 7, 34]. This is true for solvers that implement variable or constraint based propagation as well as for propagator oriented solvers like Ilog Solver and Geocode. In general, revision ordering and variable ordering heuristics have different tasks to perform when used by a search algorithm like MAC. Prior to the emergence of conflict-driven heuristics there was no way to achieve an interaction with each other, i.e. the order in which the revision list was organized during the application of AC could not affect the decision of which variable to select next (and vice versa). The contribution of revision ordering heuristics to the solver's efficiency was limited to the reduction of list operations and constraint checks.

In this section we first show that the ordering of the revision list can affect the decisions taken by a conflict-driven DVO heuristic. That is, different orderings can lead to different parts of the search space being explored. Based on this observation, we then present a set of new revision ordering heuristics that use constraint weights, which can not only reduce the numbers of constraints checks and list operations, but also cut down the size of the explored search tree.

Finally, we demonstrate that some conflict-driven DVO heuristics, e.g. "*alldel*"
and "*fully assigned*", are less amenable to changes in the revision list ordering than others (e.g. *dom/wdeg*).

First of all, to illustrate the interaction between a conflict-driven variable ordering heuristic and revision list orderings, we give the following example.

Example 1. Assume that we want to solve a CSP (*X, D, C*), where X contains n variables {x1, x2*, ..., x*n}, using a conflict-driven variable ordering heuristic
(e.g. dom/wdeg), and that at some point during search and propagation the variables pending for revision are x1 and x5. Also assume that two of the constraints in the problem are x1 > x2 and x5 > x6, and that the domains of x1, x2, x5, x6 are as follows: D(x1) = D(x5) = {0, 1}, D(x2) = D(x6) = {2, 3}. Given these constraints and domains, the revision of x1 against x2 would result in the DWO of x1, and the revision of x5 against x6 would result in the DWO of x5. Independent of which variable is selected to be revised first (i.e. either x1 or x5), a DWO will be detected and the solver will reject the current variable assignment. However, depending on the order of revisions, the *dom/wdeg* heuristic will increase the weight of a different constraint. To be precise, if a revision ordering heuristic R1 selects to revise x1 first then the DWO of D(x1) will be detected and the weight of constraint c12 will be increased by 1. If some other revision ordering heuristic R2 selects x5 first then the DWO of D(x5) will be detected, but this time the weight of constraint c56 will be increased by 1. Since increases in constraint weights affect the subsequent choices of the variable ordering heuristic, R1 and R2 can lead to different future decisions for variable instantiation. Thus, R1 and R2 may guide search to different parts of the search space.

From the above example it becomes clear that the revision ordering can have an important impact on the performance of conflict-driven heuristics like