Comparisons between primal and dual approaches have recently been extensively studied and evaluated from a theoretical standpoint based on the amount of pruning achieved by each of these when applied to non-binary constraint satisfaction problems. Enforcing arc consistency on the dual encoding has been shown to strictly dominate enforcing GAC on the primal encoding (Stergiou & Walsh 1999). More recently, extensions to dual arc consistency have extended these results to dual encodings that are based on the construction of compact constraint coverings, that retain the completeness of the encodings, while using a fraction of the space. In this paper we present a complete theoretical evaluation of these different consistency techniques and also demonstrate how arbitrarily high levels of consistency can be achieved efficiently using them.
Local consistency enforcing is at the core of CSP (Constraint Satisfaction Problem) solving. Although arc consistency is still the most widely used level of local consistency, researchers are going on investigating more powerful levels, such as path consistency, k-consistency, (i,j)-consistency. Recently, more attention has been turned to inverse local consistency levels, such as path inverse consistency, k-inverse consistency, neighborhood inverse consistency, which do not suffer from the drawbacks of the other local consistency levels (changes in the constraint definitions and in the constraint graph, prohibitive memory requirements). In this paper, we propose a generic framework for inverse local consistency, which includes most of the previously defined levels and allows a rich set of new levels to be defined. The first benefit of such a generic framework is to allow a user to define and test many different inverse local consistency levels, in accordance with the problem or even the instance he/she has to solve. The second benefit is to allow a generic algorithm to be defined. This algorithm, which is parameterized by the chosen inverse local consistency level, generalizes the AC7 algorithm used for arc consistency, and produces from any instance its locally consistent closure at the chosen level.
Specifically, we present a relationship between the looseness of the constraints, the size of the domains, and the inherent level of local consistency of a constraint network. The results we present are useful in two ways. First, a common method for finding solutions to a constraint network is to first preprocess the network by enforcing local consistency conditions, and then perform a backtracking search.
In this paper, we show that there is a close relation between consistency in a constraint network and set intersection. A proof schema is provided as a generic way to obtain consistency properties from properties on set intersection. This approach not only simplifies the understanding of and unifies many existing consistency results, but also directs the study of consistency to that of set intersection properties in many situations, as demonstrated by the results on the convexity and tightness of constraints in this paper. Specifically, we identify a new class of tree convex constraints where local consistency ensures global consistency.