Domain-Heuristics for Arc-Consistency Algorithms M.R.C. van Dongen

Abstract. Arc-consistency algorithms are widely used to prune the search-space of Constraint Satisfaction Problems (CSPs). They use support-checks (also known as consistency-checks) to find out about the properties of CSPs. They use arc-heuristics to select the next constraint and domain-heuristics to select the next values for their next support-check. We will investigate the effects of domain-heuristics by studying the average time-complexity of two arc-consistency algorithms which use different domain-heuristics. We will assume that there are only two variables. The first algorithm, called L, uses a lexicographical heuristic. The second algorithm, called D, uses a heuristic based on the notion of a double-support check. We will discuss the consequences of our simplification about the number of variables in the CSP and we will carry out a case-study for the case where the domain-sizes of the variables is two. We will present relatively simple formulae for the exact average time-complexity of both algorithms as well as simple bounds. As a and b become large L will require about 2a + 2b − 2 log(a) − 0.665492 checks on average, where a and b are the domain-sizes and log(·) is the base-2 logarithm. D requires an average number of support-checks which is below 2 max(a, b) + 2 if a + b ≥ 14. Our results demonstrate that D is the superior algorithm. Finally, we will provide the result that on average D requires strictly fewer than two checks more than any other algorithm if a + b ≥ 14