2-C3OP: An Improved Version of 2-Consistency

Nowadays, many real problems can be modeled as constraint satisfaction problems. Arc consistency algorithms are widely used to prune the search space of constraint satisfaction. In this paper we present a new algorithm, called 2-C3OP, that achieves 2-consistency in binary and non-normalized CSPs. This algorithm is a reformulation of 2-C3 algorithm and it performs the constraint checks bidirectionally using inference. The evaluation section shows that 2-C3OP achieve 2-consistency like 2-C3 and it is 40% faster. Furthermore, 2-C3OP performs less number of constraint checks than both AC3 and 2-C3.