Neighbourhood SAC: Extensions and new algorithms

Abstract

Neighbourhood singleton arc consistency (NSAC) is a type of singleton arc consistency (SAC) in which the subproblem formed by variables adjacent to a variable with a singleton domain is made arc consistent. This paper describes two extensions to neighbourhood SAC. The first is a generalization from NSAC to k-NSAC, where k is the maximum length of the shortest path between the singleton variable and any variable in the subgraph. The second is an extension of k-NSAC to problems with n-ary constraints, which retains the basic definition of a k-neighbourhood subgraph. To establish such consistencies a suite of algorithms is considered based on various SAC algorithms including SAC-1, SACQ, SAC-SDS, and SAC-3. In analyzing these different algorithms it was found useful to distinguish between “light-weight” and “heavy-weight” SAC algorithms, based on the complexity of data structures and procedures needed to carry out the task of establishing (N)SAC. Under this classification, SAC-1 and SACQ are light-weight; the other two (and SAC-2) are heavy-weight. It was found that only light-weight algorithms can be readily and effectively transformed into efficient NSAC algorithms. In contrast, because of their specialized procedures, it was necessary to modify heavy-weight algorithms significantly, which also compromised performance. Extensive experimental analysis shows that with a spectrum of neighbourhood consistencies and attendant algorithms, one can finesse the fundamental tradeoff between efficiency and effectiveness across a greater range of problems than with SAC and NSAC algorithms alone. This work serves to enlarge the scope of SAC-based consistency maintenance as well as defining the various niches that light-weight and heavy-weight algorithms are best suited for.