Reducing Checks and Revisions in Coarse-grained MAC Algorithms

Abstract

Arc consistency algorithms are widely used to prune the search space of Constraint Satisfaction Problems (CSPs). Coarse-grained arc consistency algorithms like AC-3, AC-3d and AC-2001 are efficient when it comes to transforming a CSP to its arc-consistent equivalent. These algorithms repeatedly carry out revisions. Revisions require support checks for identifying and deleting all unsupported values from the domain of a variable. In revisions for difficult problems most values have some support. Indeed, most revisions are ineffective, i.e. they cannot delete any value and consume a lot of checks and time. We propose two solutions to overcome these problems. First we introduce the notion of a Support Condition (SC) which guarantees that a value has some support. SCs reduce support checks while maintaining arc consistency during search. Second we introduce the notion of a Revision Condition (RC) which guarantees that all values have support. A RC avoids a candidate revision and queue maintenance overhead. For random problems, SCs reduce the checks required by MAC-3 (MAC-2001) up to 90% (72%). RCs avoid at least 50% of the total revisions. Combining the two results in reducing 50% of the solution time.