SAC and neighbourhood SAC

Issue title: 19th RCRA International Workshop on “Experimental evaluation of algorithms for solving problems with combinatorial explosion”

Article type: Research Article

Authors: Wallace, Richard J.

Affiliations: Cork Constraint Computation Centre and Department of Computer Science, University College Cork, Cork, Ireland. E-mail: r.wallace@4c.ucc.ie

Abstract: This paper introduces a new kind of local consistency based on the general idea of singleton arc consistency (SAC). This is a reduced form of SAC that only considers neighbourhoods of a variable with a singleton domain; hence, the name “neighbourhood SAC” (NSAC). Like AC and SAC, NSAC has a unique fixpoint, so that NSAC algorithms will produce the same result when applied to a problem regardless of the order in which problem elements are processed. Although NSAC is, of course, dominated by full SAC, on many problems these algorithms produce almost as much filtering with significantly less cost. NSAC can also be incorporated into full search, as a maintained neighbourhood SAC algorithm. The implementation of NSAC has also inspired two new SAC algorithms. One is a full SAC algorithm that is somewhat more efficient than the classical SAC-1 algorithm on many problems and is much easier to code than more advanced versions of SAC. The other is a partial SAC procedure that performs almost as much domain reduction as full SAC, while requiring much less time than full SAC algorithm on some problems. It is, therefore, a possible alternative to restricted SAC-1. These new algorithms are evaluated in experimental tests, together with SAC-1 and three well-known advanced SAC procedures, on a variety of problem classes.

Keywords: Constraint satisfaction, arc consistency, singleton arc consistency

DOI: 10.3233/AIC-140635

Journal: AI Communications, vol. 28, no. 2, pp. 345-364, 2015