Enhancing Neighbourhood Substitutability Thanks to Singleton Arc Consistency

In this paper, a semantic generalization of neighbourhood substitutability is presented. Instead of the syntactical concept of supports, our generalization originally exploits a new semantic measure based on single arc-consistency (SAC) checking. This generalization is then exploited in two different ways. Firstly, a new pretreatment of constraints networks is proposed. Secondly, as SAC is a basic operation in backtrack search-based algorithms like MAC, we show that our generalization can be easily applied dynamically. The experimental results of our approach show interesting improvements on some classes of CSP instances and demonstrate the feasibility of the dynamic integration of our generalized neighbourhood substitutability.