The process of replacing a constraint by another which has a simpler form, but is equivalent (in some sense)

Constraint C1 implies constraint C2: C1® C2, if every solution of C1 is a solution of C2

Constraint C2 is redundant with respect to C1 if C1® C2

The elimination of redundant constraints is a form of simplification

The transformation of a constraint to an equivalent normalised form often results in simplification

It is often the case that we are interested in the possible values of only some of the variables in a constraint

A projection of a constraint C1 onto a variable set V is a constraint C2 such that

• Every solution of C1 is a solution of C2
• Every solution of C2 can be extended to a solution of C1

Applies to linear inequality constraints

• For each variable to be eliminated
• For each pair of constraints which can be written t1 £ y and y £ t2
• Add the constraint t1 £ t2
• Finally, delete all the constraints involving y

Some constraint domains do not permit simple projection (essentially, the extra variables permit constraints to be imposed that cannot be imposed without them - see the successor example in the text)

A simplifier is an algorithm which takes a constraint C1 and a set of variables V and returns a new constraint C2 which is equivalent to C1 with respect to V

A simplifier isweakly projecting if the simplication of C1 with respect to V is the smallest constraint which is equivalent to C1 with respect to V

Assume a tree constraint C is to be simplified with respect to variable set V

• First, apply the unification algorithm to C
• Whenever there is a constraint in C which does not involve variables in V, delete it
• Whenever there is a constraint in C of the form x = y, where x is in V and y is not, replace y by x throughout C

An optimisation problem (C,f) consists of a constraint problem C, together with an objective function f which gives a real value to every valuation of the variables in C

An optimal solution to an optimisation problem (C,f) is a solution of C which has a lower value under f than any other solution of C

This has been covered (briefly) by John

Rules are written

(read "if B then A" or "A if B")

B (the body) may contain any number of literals (primitive or user-defined constraints),

If B contains no literals, the rule is written

and is called a fact

A (the head) is only allowed to contain one user-defined constraint, of the form

There may be more than one rule for a given predicate p; they are normally all grouped together when a program is written.

Kirchhoff's laws give the equations

V1 = I * R1

VD = I2 * R2

V = V1 + V2

I = I2 + ID

We can write a rule which specifies that the given circuit is a voltage divider:

Suppose we have 5, 9 and 14W resistors available, and 9 or 12V cells. We can specify this by

If we want an output voltage of between 5.4 and 5.5V, with a divider current of 0.1A, we would specify this as

Overall, then, our goal is

We can rewrite the goal using the rules above; there are three possible rewrites for each of the two 'resistor' goals, and two for the 'cell' goal, giving a total of 12; of these, only one reduces to a satisfiable constraint, giving

V=9

R1=5

R2=9

Note that one of the commonest uses of divider circuits arises when the resistances R1 and R2 are combined into a variable resistor with a fixed total resistance R, and a contact sliding along the resistor dividing it into R1 and R2; this is usually drawn:

N! = 1 if N = 0

N! = N * (N - 1)! If N ³ 1

In constraint logic programming, this would come out as

Given the goal

we could rewrite by the second rule to

2=N, X = N * F, N ³ 1, fac(N - 1, F)

and again to

2=N, X = N * F, N ³ 1, N - 1 = N', F = N' * F', N' ³ 1, fac(N' - 1, F')

finally, applying the first rule gives

2=N, X = N * F, N ³ 1, N - 1 = N', F = N' * F', N' ³ 1, N' - 1 = 0, F' = 1

Simplifying with respect to X gives X = 2

Note that the first two rewritings are forced on us, because rewriting by the first rule would immediately give unsatisfiable constraints

However the last step could be replaced with a further rewriting by the second rule, and indeed this process can continue on forever (though no further satisfiable constraints will be found)

In fact, CLP systems virtually always have the strategy of preferentially rewriting by earlier rules where possible (which is why we write the recursive rule last)