A FILTERING TECHNIQUE TO ACHIEVE 2-CONSISTENCY IN CONSTRAINT SATISFACTION PROBLEMS

Abstract

[EN] Arc-Consistency algorithms are the most commonly used ltering techniques to prune the search space in Constraint Satisfaction Problems (CSPs). 2-consistency is a similar technique that guarantees that any instantiation of a value to a variable can be consistently extended to any second variable. Thus, 2-consistency can be stronger than arc-consistency in binary CSPs. In this work we present a new algorithm to achieve 2- consistency called 2-C4. This algorithm is a reformulation of AC4 algorithm that is able to reduce unnecessary checking and prune more search space than AC4. The experimental results show that 2-C4 was able to prune more search space than arc-consistency algo- rithms in non-normalized instances. Furthermore, 2-C4 was more efficient than other 2-consistency algorithms presented in the literature.