Partial (neighbourhood) singleton arc consistency for constraint satisfaction problems
Refereed Conference Meeting Proceeding
Algorithms based on the general idea of singleton arc consistency (SAC) show considerable promise for improving backtrack search algorithms for constraint satisfaction problems (CSPs). The drawback is that even the most efficient efficient of them is still comparatively expensive. Even when limited to preprocessing, they give overall improvement only when problems are quite difficult to solve with more typical procedures such as maintained arc consistency (MAC). The present work examines a form of partial SAC and neighbourhood SAC (NSAC) in which a subset of the variables in a CSP are chosen to be made SAC-consistent or neighbourhood-SAC-consistent. It is shown that, using the proper procedures, partial (N)SAC is associated with a unique fixpoint for any given subset of variables. Various heuristic strategies for choosing the designated subset are described and tested, in particular a strategy of choosing by constraint weight after random probing. Experimental results justify the claim that these methods can be nearly as effective as full (N)SAC in terms of values discarded while greatly reducing the effort required.
Thirty-first International Florida AI Research Society Conference (FLAIRS 2018)
Digital Object Identifer (DOI):
United States of America
National University of Ireland, Cork (UCC)
Open access repository: