Alternative and Generalized Approaches

[higher-order] [pre-solutions] [compositional theory] [semiring-based CSP]

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

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 constraint c is not required to be satisfied than it is possible to substitute the constraint c by the disjunction (c or true). Now, if the system is not able to satisfy the constraint c, 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.

Pre-solutions and Pre-measure

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

pre-solution that corresponds to the set S_H,0 in traditional constraint hierarchies, and

pre-measure that 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.

Compositional Theory

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 scheme which can compose together solutions to individual hierarchies, and

non-compositional scheme which 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 a guard, denoted [] and defined by the following way:
e#(A [] B) = e#A, if e#B>0
           = 0,   if e#B=0
Then, the BCH solution of 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₀(H),S₁(H),...,S_n(H)], where
S₀(H) = a bag of solutions of the constraints in the required level, and
S_i(H) = S(H_i) [] S₀(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 commutative composition operator o that is defined in a following way:
S₀(o CH_j) = intersection of S₀(CH_j)                
S_i(o CH_j) = (additive union of S_i(CH_j)) [] S₀(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 filter that is a function from bags to bags. Filter f is applied to the BCH solution and a new solution is constructed, i.e.,

[FS₀(H),FS₁(H),...,FS_n(H)], where
FS₀(H) = S₀(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,   otherwise                 
After applying the filter to the BCH solution, we get exactly the same solution as in traditional constraint hierarchies.

Semiring-based Constraint Satisfaction (SCSP)

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-semiring is 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 constraint specifies 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>.

[higher-order] [pre-solutions] [compositional theory] [semiring-based CSP]

Contents

Prev
Up
Next

Designed and maintained by Roman Barták

Guide to Constraint Programming	© Roman Barták, 1998
Contents	Prev	Up	Next