Neighbourhood SAC for Preprocessing and Search

ABSTRACT. This paper reports extensions and further analysis of a new form of singleton arc consistency, called neighbourhood SAC (NSAC), where a subproblem adjacent to the variable with a reduced domain (the "focal variable") is made arc consistent.

The first part of the paper presents two important extensions: (1) NSAC is generalized to k-NSAC, where k is the longest path between the focal variable and any variable in the subgraph. In this framework, the original NSAC becomes 1-NSAC; but in addition, we can have 2-NSAC, 3-NSAC, etc. up to a point where there is no difference from full SAC. In this work we will only consider the just-named forms. Obviously, there is an associated dominance hierarchy with respect to level of consistency, with k-NSAC < (k+1)-NSAC until full SAC is reached. (2) NSAC can be extended in a relatively straightforward way to handle n-ary constraints, although there are some subtleties, which are discussed.

The second part presents some studies of hybrid search techniques based on NSAC and SAC, using a variety of problems. Comparisons are made using the domain/degree and the domain/weighted degree variable ordering heuristics. In some cases, higher levels of consistency maintenance outperform MAC by several orders of magnitude, although with weighted degree the best tradeoff is obtained when SAC-based consistency is restricted to preprocessing.