(called domv) or together with *deg down* which is used in order to break ties
(called ddeg ◦domv). Moreover, they proposed the ratio *sat up/dom j up* (called domc*/dom*v) as a new heuristic. Regarding the variable-oriented variant, they adopted the domv and *ddeg* heuristics from [38] and proposed a new one called remv. This heuristic corresponds to the greatest proportion of removed values in a variable's domain. For the constraint-oriented variant they used domc(the smallest current domain size) and remc(the greatest proportion of removed values in a variable's domain). Experimental results showed that the variableoriented AC-3 implementation with the domvrevision ordering heuristic (simply denoted dom hereafter) is the most efficient alternative.

5.3. Revision ordering heuristics based on constraint weights The heuristics described in the previous subsection, and especially dom, improve the performance of AC-3 (and MAC) when compared to the classical queue or stack implementation of the revision list. This improvement in performance is due to the reduction in list additions and constraint checks. A key principle that can have a positive effect on the performance of the AC algorithms is the "ASAP principle" by Wallace and Freuder [38] which urges to "remove domain values as soon as possible". Considering revision ordering heuristics this principle can be translated as follows: When AC is applied during search (within an algorithm such as MAC), to reach as early as possible a failure (DWO), order the revision list by putting first the arc or variable which will guide you to early value deletions and thus, most likely, earlier to a DWO.

To apply the "ASAP principle" in revision ordering heuristics, we must use some metric to compute which arc (or variable) in the AC revision list is the most likely to cause failure. Until now, constraint weights have only been used for variable selection. In the next paragraphs we describe a number of new revision ordering heuristics for all three AC-3 variants. These heuristics use information about constraint weights as a metric to order the AC revision list and they can be used efficiently in conjunction with conflict-driven variable ordering heuristics to boost search.

The main idea behind these new heuristics is to handle as early as possible potential *DWO-revisions* by appropriately ordering the arcs, variables, or constraints in the revision list. In this way the revision process of AC will be terminated earlier and thus constraint checks can be reduced significantly. Moreover, with such a design we may be able to avoid many *redundant revisions*.

As will become clear, all of the proposed heuristics are lightweight (i.e. cheap to compute) assuming that the weights of constraints are updated during search.

Arc-oriented heuristics are tailored for the arc-oriented variant where the list of revisions Q stores arcs of the form (cij ,xi). Since an arc consists of a constraint cij and a variable xi, we can use information about the weight of the constraint, or the weight of the variable, or both, to guide the heuristic selection. These ideas are the basis of the proposed heuristics described below. For each heuristic we specify the arc that it selects. The names of the heuristics are preceded by an "a" to denote that they are tailored for arc-oriented propagation.