Reducing Checks and Revisions in the Coarse-grained Arc Consistency Algorithms

TL;DRAbstract

Arc consistency algorithms are widely used to prune the search space of Constraint Satisfaction Problems (CSPs). Coarse-grained arc consistency algorithms like AC-3 and AC-2001 are efficient in establishing arc consistency on a given CSP. These algorithms repeatedly carry out revisions. Revisions require support checks for identifying and deleting all unsupported values from the domains. For difficult problems, many values find some support while revising domains. Indeed, many revisions are ineffective, that is 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). If the SC holds then it guarantees that a given value has some support. SCs reduce support checks while maintaining arc consistency during search. Second, we introduce the notion of a Revision Condition (RC). If the RC holds then it guarantees that all values of a given domain have some support. An RC a

Chat with Paper

AI Agents for this Paper