Partial (Neighbourhood) Singleton Arc Consistency for Constraint Satisfaction Problems

Issue title: Special issue of the 25th RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion

Guest editors: Thomas Eiter, Marco Maratea and Mauro Vallati

Article type: Research Article

Authors: Wallace, Richard J.^{; *}

Affiliations: Insight Centre for Data Analytics Department of Computer Science, University College Cork, Cork, Ireland. richard.wallace@insight-centre.org

Correspondence: [*] Address for correspondence: Insight Centre for Data Analytics Department of Computer Science, University College Cork, Cork, Ireland

Abstract: Algorithms based on 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 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. Such consistencies, despite their partial character, are still well-characterized in that algorithms have unique fixpoints. Heuristic strategies for choosing an effective subset of variables are described and tested, the best being choice by highest degree and a more complex strategy of choosing by constraint weight after random probing. Experimental results justify the claim that these methods can be nearly as effective as the corresponding full version of the algorithm in terms of values discarded or problems proven unsatisfiable, while significantly reducing the effort required to achieve this.

DOI: 10.3233/FI-2020-1944

Journal: Fundamenta Informaticae, vol. 174, no. 3-4, pp. 311-344, 2020