Variable-Oriented Adaptive Singleton Consistency

Abstract

Singleton consistency significantly reduces the search space of backtracking search for solving constraint satisfaction problems (CSP). However, it is too expensive to be used throughout the search, and it has not been successfully applied in solving general CSPs. In this paper, we propose a variable-oriented adaptive singleton consistency, namely VOASC, that could be applied in general-purpose constraint solvers. It calculates the filtering efficiency of local consistency enforced by the default propagation engine and the singleton-based consistency for each variable, and then selects an appropriate consistency to propagate the decisions of the variable in subsequent searches. We performed extensive experimentation with the MiniZinc benchmark suite. VOASC demonstrates superior solving performance on both CSP and COP, compared to the two candidate local consistencies and several existing adaptive propagation methods.