A Study of Residual Supports in Arc Consistency

Abstract

In an Arc Consistency (AC) algorithm, a residual support, or residue, is a support that has been stored during a previous execution of the procedure which determines if a value is supported by a constraint. The point is that a residue is not guaranteed to represent a lower bound of the smallest current support of a value. In this paper, we study the theoretical impact of exploiting residues with respect to the basic algorithm AC3. First, we prove that AC3rm (AC3 with multi-directional residues) is optimal for low and high constraint tightness. Second, we show that when AC has to be maintained during a backtracking search, MAC2001 presents, with respect to MAC3rm, an overhead in O(med) per branch of the binary tree built by MAC, where m denotes the number of refutations of the branch, e the number of constraints and d the greatest domain size of the constraint network. One consequence is that MAC3rm admits a better worst-case time complexity than MAC2001 for a branch involving m refutations when either m > d^2 or m > d and the tightness of any constraint is either low or high. Our experimental results clearly show that exploiting residues allows enhancing MAC and SAC algorithms. URL: http://www.cril.univ-artois.fr/~lecoutre/research/publications/publications.html