Finally, the constraint-oriented heuristic c *wcon* selects a constraint cij from the AC revision list having the highest weight among all constraints in Q. The call to this heuristic can be attached to line 4 of Algorithm 5. One can devise more complex constraint-oriented heuristics by aggregating the weighted degrees of the variables involved in a constraint. However, we have not yet implemented such heuristics.

5.4. Experiments with revision ordering heuristics In this section we experimentally investigate the behavior of the new revision ordering heuristics proposed above on several classes of real world, academic and random problems. We only include results for the two most significant arc consistency variants: arc and variable oriented. We have excluded the constraintoriented variant since this is not as competitive as the other two [7].

We compare our heuristics with dom, the most efficient previously proposed revision ordering heuristic. We also include results from the standard *fifo* implementation of the revision list which always selects the oldest element in the list
(i.e. the list is implemented as a queue). In our tests we have used the following measures of performance: cpu time in seconds (t), number of visited nodes (n),
number of constraint checks (c) and the number of times (r) a revision ordering heuristic has to select an element in the propagation list Q.

Tables 9 and 10 show results from some real-world RLFAP instances. In the arc-oriented implementation of AC-3 (Table 9), heuristics a *wcon*, mainly, and a *dom/wcon*, to a less extent, decrease the number of constraint checks and list revisions compared to dom. However, the decrease is not substantial and is rarely leads into a decrease in cpu times. The notable speed-up observed for problem s11-f6 is mainly due to the reduction in the number of visited nodes offered by the two new heuristics. a *wdeg* and a *dom/wdeg* are less competitive, indicating that information about the variables involved in arcs is less important compared to information about constraints.

The variable-oriented implementation (Table 10) is clearly more efficient than the arc-oriented one. This confirms the results of [7]. Concerning this implementation, heuristic v *dom/wdeg* in most cases is better than dom and *queue* in all the measured quantities (number of visited nodes, constraint checks and list revisions). Importantly, these savings are reflected on notable cpu time gains making the variable-oriented heuristic v *dom/wdeg* the overall winner. Results also show that as the instances becomes harder, the efficiency of v *dom/wdeg* compared to dom increases. The variable-oriented v *wdeg* heuristic in most cases is better than dom but is clearly less efficient than v *dom/wdeg*.

In Table 11 we present results from structured instances belonging to benchmark classes *langford* and *driver*. As the variable-oriented AC-3 variant is more efficient than the arc-oriented one, we only present results from the former.

Results show that on easy problems all heuristics except *queue* are quite competitive. But as the difficulty of the problem increases, the improvement offered by the v *dom/wdeg* revision heuristic becomes clear. On instance driverlogw-09 we can see the effect that weight based revision ordering heuristics can have on search. v *dom/wdeg* cuts down the number of node visits by more than