Enforcing local consistencies is one of the main features of constraint reasoning. Which level of local consistency should be used when searching for solutions in a constraint network is a basic question. Arc consistency and partial forms of arc consistency have been widely studied, and have been known for sometime through the forward checking or the MAC search algorithms. Until recently, stronger forms of local consistency remained limited to those that change the structure of the constraint graph, and thus, could not be used in practice, especially on large networks. This paper focuses on the local consistencies that are stronger than arc consistency, without changing the structure of the network, i.e., only removing inconsistent values from the domains. In the last five years, several such local consistencies have been proposed by us or by others. We make an overview of all of them, and highlight some relations between them. We compare them both theoretically and experimentally, considering their pruning efficiency and the time required to enforce them.

Filtering techniques are essential for efficient solution searching in a constraint network (CN). However, for a long time, it has been considered that to efficiently reduce the search space, the best choice is the limited local consistency achieved by forward checking. However, more recently, it has been shown that maintaining arc consistency (which is a more pruningful local consistency) during searching outperforms forward checking on hard and large constraint networks. In this paper, we show that maintaining a local consistency which is stronger than arc consistency during searching can be advantageous. According to a comparison of local consistencies that are more pruningful than the arc consistency which can be used on large CNs, max-restricted path consistency (Max-RPC) is one of the most promising local consistencies. We propose a new local consistency, called Max-RPCEn (Max-RPC Enhanced), that is stronger than Max-RPC and that has almost the same CPU time requirements.

Constraint satisfaction problems (CSPs) are widely used in Artificial Intelligence. The problem of the existence of a solution in a CSP being NP-complete, filtering techniques and particularly arc-consistency are essential. They remove some local inconsistencies and so make the search easier. Since many problems in AI require a dynamic environment, the model was extended to dynamic CSPs (DCSPs) and some incremental arc-consistency algorithms were proposed. However, all of them have important drawbacks. DnAC-4 has an expensive worst-case space complexity and a bad average time complexity. AC/DC has a non-optimal worst-case time complexity which prevents from taking advantage of its good space complexity. The algorithm we present in this paper has both lower space requirements and better time performances than DnAC-4 while keeping an optimal worst case time complexity.