A Greedy Approach to Establish Singleton Arc Consistency

Abstract

In this paper, we propose a new approach to establish Singleton Arc Consistency (SAC) on constraint networks. While the principle of existing SAC algorithms involves performing a breadth-first search up to a depth equal to 1, the principle of the two algorithms introduced in this paper involves performing several runs of a greedy search (where at each step, arc consistency is maintained). It is then an original illustration of applying inference (i.e. establishing singleton arc consistency) by search. Using a greedy search allows benefiting from the incrementality of arc consistency, learning relevant information from conflicts and, potentially finding solution(s) during the inference process. Furthermore, both space and time complexities are quite competitive. 1