In this paper, we introduce for the qualitative constraint networks (QCNs) a new consistency: the partial weak composition consistency. The partial weak composition consistency, similarly to the partial path-consistency, considers triangles of a graph and corresponds to the weak composition consistency restricted to these triangles. We show that for the pre-convex QCNs of the Interval Algebra (IA), the partial weak composition consistency with respect to a triangulation of the graph of constraints is sufficient to decide the consistency problem. From this result, we propose an algorithm allowing to solve QCNs of IA. The experiments that we have conducted show the interest of this algorithm to solve the consistency problem of the QCNs of IA.

In this paper, we propose a new technique to compute irredundant sub-sets of constraint networks. Since, checking redundancy is Co-NP Complete problem, we use different polynomial local consistency entailments for reducing the computational complexity. The obtained constraint network is irredundant modulo a given local consistency. Redundant constraints are eliminated from the original instance producing an equivalent one with respect to satisfiability. Eliminating redundancy might help the CSP solver to direct the search to the most constrained (irredundant) part of the network.

Many local consistency properties have been exploited in solving constraint satisfaction problems. The objective is to reduce the search space and consequently improve search methods. It has been shown that maintaining arc- consistency during search is very useful in solving CSPs. The use of stronger local consistency forms (like path consistency) is still limited since they need complicated data structures to be managed and the constraint graph may be modified. In this paper, we propose a possible way to get benefits from using, in a preprocessing step, a partial form of path consistency and arc consistency based on support intervals notion.

Many backtrack search algorithms has been designed over the last years to solve constraint satisfaction problems. Among them, Forward Checking (FC) and Maintaining Arc Consistency (MAC) algorithms are the most popular and studied algorithms. In This work, such algorithms are revisited and extensively compared giving rise to interesting characterization of their efficiency with respect to random instances. More precisely, we provide experimental evidence that FC outperforms MAC on hard CSPs with high graph density and low constraint tightness whereas MAC is better on hard CSPs with low density and high constraints tightness. This results show that on some CSPs maintaining full arc consistency during search might be time consuming. Then, we propose a new generic approach that maintain partial and parameterizable form of local consistency.

Local consistency is often a suitable paradigm for solving constraint satisfaction problems. We show how search algorithms could be improved, thanks to a smart use of two filtering techniques (path consistency and singleton arc consistency). We propose a possible way to get benefits from using a partial form of path consistency (PC) during the search. We show how local treatment based on singleton arc consistency (SAC) can be used to achieve more powerful pruning.

Recently, efficient algorithms have been proposed to achieve arc- and path-consistency in constraint networks. The best path-consistency algorithm proposed is PE-{5|6} which is a natural generalization of AC-6 to path-consistency independently proposed by M. Singh (1995) for PC-5 and A. Chmeiss and P. Jegou (1995) for PC-6. Unfortunately, we have remarked that PC-{5|6}, though it is widely better than PC-4 (Chmeiss and P. Jegou, 1996) was not very efficient in practice, especially for those classes of problems that require an important space to be run. So, we propose a new path-consistency algorithm called PC-8, the space complexity of which is O(n/sup 2/d) but its time complexity is O(n/sup 3/d/sup 4/), i.e. worse than that of PC-{5|6}. However, the simplicity of PC-8 as well as the data structures used for its implementation offer a higher performance than PC-{5|6}. The principle of PC-8 is also used to propose a new algorithm to achieve arc-consistency called AC-8.