*Guide to Constraint Programming*
*© Roman Barták,
1998*
**Up**

Constraint Hierarchies sounds to be the most popular approach for describing and solving over-constrained problems. Nevetheless, there exists other alternative approaches too. Also, some frameworks that cover today's approaches have been proposed as a generalization of solvers for over-constrained problems.

Alternative Approaches

In addition to Extended CSPs, there also exist other alternative approaches that express similar ideas as PCSP or constraint hierarchies.

Higher-order constraints are another approach to solve over-constrained problems. Traditionally, a constraint system or store is assumed to be the conjunction of primitive constraints, i.e., the solver tries to satisfy all the constraints. Why not to allow a disjunction of constraints in place of the primitive constraint? If one needs to express that a constraintcis not required to be satisfied than it is possible to substitute the constraintcby the disjunction(c or true). Now, if the system is not able to satisfy the constraintc, it selects the alternative constraint, that is allways true. It is possible to generalize this view and allow arbitrary disjunction of constraints as a primitive constraint.Notice that the above described disjunctive constraints change the declarative character of the constraint store because the disjunction is not perceived declaratively and the order of constraints in the disjunction is important for the constraint solver. On the other hand, it could be easier to incorporate disjunctive constraints into languages like Prolog as the process of satisfying disjunctive constraint is similar to solving a goal in Prolog (alternative rules to reduce the goal are also selected in a given order in Prolog).

Higher order constraints are used in some constraint languages like CHAL (extended version of CAL) and it can also substite inter-hierarchy comparison, e.g., in IHCS. Note, that disjunctive constraints are closer to Partial CSP than to constraint hierarchies.

There exists alternative definition of constraint hierarchies by Maher and Stuckey. This approach is based on the following notions:

pre-solutionthat corresponds to the set S_{H,0}in traditional constraint hierarchies, andpre-measurethat maps pre-solutions and sets of constraints to some scale S.Pre-solutions mapped to the scale S can then be compared via a lexicographic ordering in a following way:

alfa is better than beta iff

(g1(alfa,H1),...,gn(alfa,Hn)) >= (g1(beta,H1),...,gn(beta,Hn)),where g1,..., gn are pre-measures, alfa, beta are pre-solutions, i.e., valuations satisfying all required constraints, and H1,..., Hn are respective levels of the hierarchy H.

Various comparators can then be realized by the use of different scales and pre-measures. For example, if the scales are the set of all sets of constraints ordered by inclusion and the pre-measure is the set of constraints at a given level satisfied by a valuation, then we obtain the locally-predicate-better comparator.

Generalized Approaches

To model features of various CSP systems, the general frameworks have been proposed. Among them the compositional theory for reasoning about over-constrained systems and the semiring-based constrained satisfaction are the most popular.

Michael Jampel's Compositional Theory is a variant or extension to constraint hierarchies. It is based on idea of distributing the hierarchical solver into two parts:

compositional schemewhich can compose together solutions to individual hierarchies, andnon-compositional schemewhich removes precisely those solutions of the compositional scheme which are unacceptable to traditional constraint hierarchies.## Bags for Composition of Hierarchies (BCH)

Compositional part of the theory is called BCH (Bags for Composition of Hierarchies) because it exploits the bag data structure to represent a solution of the hierarchy.

Bags, sometimes called multisets, are like sets except that duplicate elements are allowed. Each bag can be described by membership function #, such that, e#B denotes the number of occurences of the element e in the bag B. It is possible to define operations like union, additive union and intersection for bags in an obvious way. We also need an alternative to bag intersection that is called aguard, denoted[]and defined by the following way:e#(A []B) = e#A, if e#B>0 = 0, if e#B=0Then, the

BCH solutionof the hierarchy H is defined as a tuple of bags representing solutions of individual levels guarded by the solution of the required level, i.e.,[S, where_{0}(H),S_{1}(H),...,S_{n}(H)]

S_{0}(H) = a bag of solutions of the constraints in the required level, and

S_{i}(H) = S(H_{i})[]S_{0}(H), i>0 and S(H_{i}) is a bag of solutions of the level H_{i}.Note, that the BCH solution respects the required constraints but does not respect the hierarchy because S

_{k+j}(H) can contain solutions that are not present in S_{k}(H). In general BCH solution is a superset of the traditional constraint hierarchy solution set.Now, it is possible to compose BCH solutions of individual hierarchies CH

_{j}using associative and commutativecomposition operator othat is defined in a following way:S _{0}(o CH_{j}) = intersection of S_{0}(CH_{j}) S_{i}(o CH_{j}) = (additive union of S_{i}(CH_{j}))[]S_{0}(o CH_{j})## Filters, Guards and Hierarchies (FGH)

The second part of the compositional theory is a non-compositional part called FGH (Filters, Guards and Hierarchies). FGH is responsible for removing such valuations from the BCH solution which are unacceptable to traditional constraint hierarchies. For this purpose FGH uses an extra mathematical construct

filterthat is a function from bags to bags. Filter f is applied to the BCH solution and a new solution is constructed, i.e.,[FS, where_{0}(H),FS_{1}(H),...,FS_{n}(H)]

FS_{0}(H) = S_{0}(H), and

FS_{n}(H) = f(S_{i}(H)[]FS_{i-1}(H)).Filters correspond to the comparators in traditional constraint hierarchies. For example, locally-predicate-better comparator corresponds to the filter f

_{max}that selects only those elements which have maximal number of occurences in the bag, i.e.,e#f _{max}(A) = e#A, if e#A=max{e'#A | e' in A} = 0, otherwiseAfter applying the filter to the BCH solution, we get exactly the same solution as in traditional constraint hierarchies.

Semiring-based Constraint Satisfaction (SCSP) is a general framework for constraint satisfaction and optimization where classical CSPs, FCSPs, WCSP, PCSPs, and others (over finite domains) can be easily cast. The framework is based on a semiring structure, where the domain of semiring specifies the values to be associated with each tuple of values of the constraint domain, and the two semiring operations (+ and *) model constraint projection and combination respectively.A

c-semiringis a tuple <A,+,*,0,1> such that

- A is a set and 0,1 are elements in A;
- +, called the additive operation, is a closed (a+b in A), commutative (a+b=b+a), associative (a+(b+c)=(a+b)+c) and idempotent operation (a+a=a) operation such that 0 is its unit element (a+0=a=0+a) and 1 is its absorbing element (a+1=1=1+a);
- *, called the multiplicative operation, is a closed and associative operation such that 1 is its unit element and 0 is its absorbing element;
- * distributes over + (a*(b+c)=(a*b)+(a*c)).
As + is an idempotent operation, it is possible to define a

partial order<= over the semiring domain A in a following way: a<=b iff a+b=b. Note, that 0 is the minimum element of the ordering and 1 is the maximum element of the ordering.A

constraintspecifies the involved variables and the "allowed" values for them. More precisely, for each tuple of values for the involved variables, a corresponding element of the semiring domain A is given. This element can be intrepreted as the tuple's weight, or cost, or level of confindence, or else.Now, the multiplicative operation is used to combine the values of the tuples of each constraint to get the value of a tuple for all the variables, and the additive operation is used to obtain the value of the tuples of the variables in the type of problem. That is, for each valuation of the variables a combined value in A is computed by multiplying tuple's weights of individual constraints, and such valuations that have maximum combined weight are selected to the solution.

SCSP can be used to model various CSP frameworks by choosing appropriate c-semiring structure as the following examples shows:

- Classical CSP correponds to the c-semiring <{false,true},and,or,false,true>;
- Fuzzy CSP coresponds to the semiring <[0,..,1],max,min,0,1>;
- Probabilistic CSP corresponds to the semiring <[0,..,1],max,*,0,1>;
- Weighted CSP corresponds to the semiring <R
^{+},min,+,+inf,0>.

**Up**
*Designed and maintained by **Roman
Barták*