Hierarchical constraint satisfaction

Hierarchical Constrain Satisfaction (HCS) is a method of handling constraint satisfaction problems where the variables have large domains by exploiting their internal structure. In fact, for many real world problems the domain elements cluster together into sets with common properties and relations. This structure can be represented as a hierachy and is partially ordered on the subset of a relation. The expectiation is that the domains are structured so that the elements of a set frequently share consistency properties permitting them to be retained or eliminated as a unit. Thus, if some elements of a set satisfy a constraint, but not all, the subsets of the set are considered. In this way, if no elements of a set can satisfy the constraint the whole set can be discarded. Thus, structuring the domain helps in considering sets of elements all at a time and hence helps in pruning the search space more quickly.