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

Constraint hierarchies were introduced for describing over-constrained systems of constraints by specifying constraints with hierarchical strengths or preferences. It allows one to specify declaratively not only the constraints that are required to hold, but also weaker, so called soft constraints at an arbitrary but finite number of strengths. Weakening the strength of constraints helps to find a solution of previously over-constrained system of constraints. Intuitively, the hierarchy does not permit to the weakest constraints to influence the result. Moreover, constraint hierarchies allow "relaxing" of constraints with the same strength by applying, e.g., weighted-sum, least-squares or similar comparators.

Example in Constraint Hierarchies

Consider the problem of choosing matching clothes from the introductory section to over-constrained problems. Now, we can specify labeled constraints which express our preferences about matching clothes.S::{r,w}, F::{c,s}, T::{b,d,g}required C_{ST}::{(r,g),(w,b),(w,d)} strong C_{FT}::{(s,d),(c,g)} weak C_{SF}::{(w,c)}.Using any comparator (see thereinafter) will give two solutions:

(S,F,T)=(r,c,g)and(S,F,T)=(w,s,d), that satisfy the required and strong constraints but violates the weak constraint. Note, that there is no valuation satisfying all the constraints and that the above two valuations satisfy the priority constraints and, thus, they comprise the solution.

Formal definitions

In constraint hierarchies, one useslabeled constraintswhich are constraints labeled with a strength or preference. Then, aconstraint hierarchyis a (finite) multiset of labeled constraints. Given a constraint hierarchy H, let H_{0}denote the required constraints in H, with their labels removed. In the same way, we define the sets H_{1}, H_{2}, ... for levels 1, 2, ...A solution to a constraint hierarchy H will consist of valuations for variables in H, that satisfy best constraints in H respecting the hierarchy. Formally (U, V are valuations):

S_{H,0}= {U | for each c in H_{0}, c is satisfied by U}

S_{H}= {U | U is from S_{H,0}& for each V in S_{H,0}V is not better than U respecting H}.The set S

_{H,0}contains valuations satisfying required constraints in H and S_{H}, called asolution setfor H, is a subset of S_{H,0}containing all valuations which are not worse than other valuations in S_{H,0}.

There is a number of reasonable candidates for the predicate better, in the above definition of solution set, that is called a comparator. Acomparatoris anirreflexiveandtransitiverelation over valuations of variables thatrespects the hierarchy, i.e., if there is some valuation in S_{0}that completely satisfies all the constraints through level k, then all valuations in S must satisfy all the constraints through level k. Note that the comparator defines partial order over valuations.Currently, there are three widely used groups of comparators (respective valuations are denoted by greek symbols in formal definitions):

locally-better comparatorsconsider each constraint individually, i.e., a valuation U islocally-betterthan another valuation V if, for each of the constraints through some level k-1, the errors are equal for respective valuations, and at level k the error is strictly less for at least one constraint and less than or equal for all the rest

regionally-better comparatorsextend locally-better comparators to enable comparison of valuations which are incomparable by locally-better comparators, i.e., a valuation U isregionally-betterthan another valuation V if, for each level till k-1, the levels are incomparable by locally-better comparator, and at level k the error is strictly less for at least one constraint and less than or equal for all the rest.

globally-better comparatorsconsider combined errors of individual constraints at each level, i.e., a valuation U isglobally-betterthan another valuation V if, the combined errors are equal till some level k-1 for both valuations, and at level k the combined error is strictly less for the valuation U.There is a number of reasonable candidates for the

combining functionthat combines error of individual constraints at each level, namely weighted-sum, worst-case or least-squares methods.The above defined comparators need an

error functione(c,V) that returns a nonnegative real number indicating how nearly the constraint c is satisfied for a valuation V. The trivial error function returns 0 if the constraint is satisfied and 1 otherwise. Comparators based on this error function are calledpredicate-comparators. If some metric is used as the error function that the respective comparator is calledmetric-comparator.

In the above section we give a formal definition of the solution of the hierarchy. Now, the question is:"If the set of solutions S_{H,0}for the required constraints is non-empty, is the set S_{H}of solutions for the hierarchy non-empty as well?"Intuitively one might expect the answer yes, but there are some pathological hierarchies for which this is not the case. The following example presents such hierarchy.

: Consider the hierarchy {required X>0, prefer X=0} for the domain of the real numbers, using a metric comparator. Then SExample_{H,0}consist of all valuations mapping X to a positive number. Let X=d be such valuation. Then, we can find another valuation, for example X=d/2, that better satisfies the soft constraint X=0. Therefore, the set S_{H}of solutions for the hierarchy is empty because for every valuation in S_{H,0}it is possible to find a better valuation in S_{H,0}.By analyzing the above example it is possible to identify three sources of this pathological behaviour and to formulate the following propositions that guarantee the existence of the solution under some conditions.

: If the set SProposition 1_{H,0}is non-empty and finite then the set S_{H}is non-empty.

: Suppose to the contrary that SProof_{H}is empty. Pick any valuation V_{1}from S_{H,0}(S_{H,0}is non-empty). According to the assumption that S_{H}is empty, V_{1}does not belong to S_{H}. and therefore there is an V_{2}in S_{H,0}such that V_{2}is better than V_{1}respecting H. Similarly , since V_{2}does not belong to S_{H}, there is an V_{3}in S_{H,0}such that V_{3}is better than V_{2}, and so forth for an infinite chain V_{4}, V_{5}, ... Since the comparator better is irreflexive and transitive, it follows that all the V_{i}are distinct, and so there are an infinite number of them. But, by hypothesis S_{H,0}is finite, a contradiction.

: If the set SProposition 2_{H,0}is non-empty and if a predicate comparator is used, then the set S_{H}is non-empty.

: Suppose to the contrary that SProof_{H}is empty. Using the same argument as before, we show that there must be an infinite number of distinct valuations V_{i}in S_{H,0}. However, if the comparator is predicate, one valuation cannot be better than another valuation if both valuations satisfy exactly the same subset of constraints in H. Therefore each of the V_{i}must satisfy a different subset of the constraints in H. However, this is a contradiction, since H is finite.

: If the set SProposition 3_{H,0}is non-empty and D is a finite domain then the set S_{H}is non-empty.

: Because the hierarchy is a finite set, it contains only a finite number of variables. The domain D of variables is also finite and, therefore, there exists only finite number of valuations. Consequently, the set SProof_{H,0}is finite. Now, both conditions of Proposition 1 are satisfied and therefore we can derive that the set S_{H}is non-empty.

In the original definition of constraint hierarchies, only alternate solutions to one constraint hierarchy are compared. The later extension also supports comparison of solutions to more constraint hierarchies, so calledinter-hierarchy comparison(opposite to traditional intra-hierarchy comparison described above).Inter-hierarchy comparison uses globally-better comparators to compare valuations arising from more hierarchies (neither locally-better nor regionally better comparators can do it). Formally (X is a set of constraint hierarchies):

S_{X,0}= {U_{H}| H is in X & for each c in H_{0}, c is satisfied by U_{H}}

S_{X}= {U_{H}| U_{H}is from S_{X,0}& for each V_{J}in S_{X,0}, V_{J}is not better than U_{H}respecting X}.Note that each valuation is labeled by it's respective hierarchy now.

Inter-hierarchy comparison is useful especially in

Hierarchical Constraint Logic Programming(HCLP), where it can rule out some unintuitive solutions. HCLP is an extension of CLP (Constraint Logic Programming) that uses constraint hierarchies instead of flat constraints.

Classical logic is monotonic in the sense that adding new axioms to a theory can only enlarge the set of statements that can be inferred. It is never necessary to retract conclusions as new knowledge is gained. If the inference system is monotony then it is possible to infer new solution after adding new axioms directly from the original solution. Unfortunately such monotony feature is not present in constraint hierarchies and, thus, the constraint hierarchy solvers must (in general) solve the new hierarchy after adding new constraints from scratch.We say that the comparator is

orderly, if the solution set does not enlarge after adding new constraints, i.e., S_{H union J}is subset of S_{H}, where H and J are constraint hierarchies. A comparator that is not orderly isdisorderly.Unfortunately, any comparator that respects the hierarchy is disorderly. In general, this feature prevents construction of incremental constraint hierarchy solvers.

: Let D be a nontrivial domain (i.e., a domain with more than one element). Then any comparator that respects the hierarchy is disorderly.Proposition

: Let H={weak X=a} and let J={strong X=b}, where a and b are two distinct elements in D. Then the solution of the hierarchy H is X=a using arbitrary comparator C that respects the hierarchy, while the solution of the hierarchy (H union J) is X=b that is not a subset of the former solution. Therefore the comparator C is not orderly.ProofIt is also possible to define similar feature of inter-hierarchy comparison.

We say that the comparator is

monotonicif the solution set of the set of hierarchies does not reduce after adding new constraint hierarchies to this set, i.e., S_{X}is subset of S_{X union Y}, where X and Y are sets of constraint hierarchies. A comparator that is not monotonic isnonmonotonic.Again, any comparator respecting the set of hierarchies is nonmonotonic.

: Let D be a nontrivial domain. Then any comparator that respects the set of hierarchies is nonmonotonic.Proposition

: Let X={{required A=a, weak A=b}} and Y={{required A=b}}, where a and b are two distinct elements in D. Then the solution of the set of hierarchies X (in fact, X contains exactly one hierarchy) is A=a using arbitrary comparator C that respects the set of hierarchies, while the solution of the set of hierarchies (X union Y) (this set contains two hierarchies) is A=b because this solution satisfies all constraints of the respective hierarchy {required A=b}. This is not a superset of the former solution and therefore the comparator C is not monotonic.Proof

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