But we can ensure that our goal G is efficiently implemented

We can use the tricks we have already discussed to make G more efficient in the required mode

But what is the required mode?

Adding the redundant constraint D>=0 will stop search once the minimum depth already discovered has been passed:

There are sometimes situations where there is potential backtracking in a constraint, where we as the model builders are sure that the backtracking will not be productive (note that if we are wrong, the model may well produce incorrect answers)

The first case is closely analogous to a construct which occurs almost everywhere in traditional programming languages:

If G_test succeeds, then G_then is evaluated; backtracking may occur in G_then

If G_test fails then G_else is evaluated; backtracking may occur in G_else

But in neither case is there any backtracking in G_test; if backtracking reaches G_test, it fails

gives no backtracking in modes where X is fixed, compared with

which may give rise to backtracking

But note that the first form may not give correct answers in other modes; for example, the query

will incorrectly return the answer 'no', whereas

will return the answer X = -2

again

succeeds, and

fails, but

also fails

The other main restriction constraint specifies that only one solution to the goal is of interest

It is usually used where (the model designer believes that) any one solution is equivalent to any other

Again, if this is wrong, or if the goal is called in unexpected modes, the model may give incorrect answers

Given the goal

The predicate will return a first success answer having used X = b

If some later part of the program fails and causes backtracking, the goal will re-evaluate, and after some searching, produce two further success answers using X = e and X = g

Since X is not available outside intersect, it follows that the rest of the program will behave exactly the same, and simply cause two further failures

This can be avoided by

But note that the behaviour of this new version may be incorrect if L1 and L2 are not full instantiated

will fail because the first solution has X1 = a

Omitted

Omitted

Colour a map of Australia using only the colours red, yellow, blue given the constraint that no two adjacent states have the same colour

Place N queens on an N*N chessboard in such a way that no queen is attacking another

As discussed in the graph theory part of the course

Essentially the solver we have discussed in chapters 5 & 7

A primitive constraint c is node consistent with domain D if either it has more than one variable, or if every element of D is a solution of c (and a general constraint is node consistent if all its primitive constraints are)

For each single-variable primitive constraint p in turn

restrict the values in the current domain to those which provide solutions to p

consider the constraint

and domain {1,2,3}

This is not node-consistent, since Z = 3 is inconsistent with the third primitive constraint

Applying the algorithm we get

D(X) = {1,2,3}, D(Y) = {1,2,3}, D(Z) = {1,2}

A primitive constraint c is arc consistent with domain D unless it has exactly two variables X and Y, and for some value of X in D, there is no value of Y in D which satisfies the constraint (and a general constraint is arc consistent if all its primitive constraints are)

For each two-variable primitive constraint p in turn

restrict the values in the current domain to those which provide solutions to p

consider the constraint

and domain {1,2,3}

This is not arc-consistent, since X = 3 is inconsistent with the first primitive constraint

Applying the algorithm we get

D(X) = {1, 2}, D(Y) = {1,2,3}, D(Z)={1,2,3}

Applying it to variable Y, we get

D(X) = {1, 2}, D(Y) = {2}, D(Z)={1,2,3}

Finally, applying it to variable Z, we get

D(X) = {1, 2}, D(Y) = {2}, D(Z)={3}

Applying the node and arc consistency algorithms together allows us to solve problems which cannot be solved by either separately

Apply the node and arc consistency algorithms indeterminately until the constraints are both node and arc consistent

consider the constraint

and domain {1,2,3}

Applying arc consistency as before, we get

D(X) = {1, 2}, D(Y) = {2}, D(Z)={3}

Applying node consistency, we get

D(X) = {1, 2}, D(Y) = {2}, D(Z)=f

A further application of arc consistency (checking X before Y) gives

D(X) = {1}, D(Y) = f , D(Z)=f

Applying node consistency again gives no further simplification, but a further application of arc consistency gives

D(X) = f , D(Y) = f , D(Z)=f

One obvious extension of arc consistency (hpyer-arc consistency) is to extend it to primitive constraints with more than two variables

For example, consider the constraint

with D(X) = {2,3,4,5,6,7}, D(Y) = {0,1,2}, D(Z) = {-1,0,1,2}

The first check we would perform would substitute 2 for X and test for solutions (in the domain) for

In general, this problem (diophantine equations) is too expensive to be built into a constraint solver

A better approach takes into account the fact that the domains of X, Y and Z are in fact continuous domains of integers

An arithmetic primitive constraint c is bounds consistent with integer domain D unless there is a variable x in c for which either c(x® min_D(x)) or c(x® max_D(x)) is unsatisfiable for real values

(note that checking for real values is much simpler than for integer values, but if there are no real values, then there are no integer values as a consequence)

Depending on the form of the constraints, we may be able to devise propagation rules, which given a current set of ranges for the variables, generate a new set of ranges which are bounds consistent

(eg for linear inequalities)

Until constraint c is bounds consistent with domain D

Choose a variable x in a primitive constraint c' of

c giving rise to a bounds inconsistency

If there is no real value min_D(x) < x < max_D(x)

for which c' can be satisfied

return "unsatisfiable"

else

If x is minimum bound inconsistent

increase min_D(x) until bounds

consistency is restored

else

decrease max_D(x) until bounds

consistency is restored

Smuggler's knapsack has a capacity of 9 units

Size and profit of smuggle-able items are:

The minimum profit (ie risk premium) for a trip is 30; what are acceptable cargoes?

Capacity: 4W + 3P + 2C <= 9

Profit: 15W + 10P + 7C >= 30

Domain is initially [0..¥ ] for each variable

Applying bounds consistency for capacity to W, P and C in turn gives

D(W) = [0..2], D(P) = [0..3], D(C)=[0..4]

The profit constraint is bounds-consistent with this domain

Propagation rules for particular classes of constraint can be quite difficult to find; most solvers have built-in linear inequalities and a limited range of other classes

The applicability of a particular propagation rule will depend directly on the particular primitive form the solver rewrites the initial constraint to

Thus it can be hard to predict which bounds reductions will be achieved by the solver

If you have looked at the eclipse libraries, you may have wondered why each library has so many special predicates

It relates to the point above, namely that each particular primitive constraint may have specific bounds consistency propagation rules

In many cases, complex constraints may have stronger propagation rules than the rules which could have been derived from more primitive constraints in terms of which they could have been defined

asserts that the elements of the list are all distinct

It could be modeled by a conjunction of pairwise inequalities

Apart from the efficiency issue that n² inequalities are required, there is also a constraint propagation issue

On the other hand, if the problem is specified in terms of pairwise inequalities, there is no equivalent constraint which can be specified in terms of any particular primitive constraint

specifies that there are m tasks

The ith task starts at time Si, and requires Ri resources for duration Di; at any instant, only L resources are available

Cumulative could be defined more simply as a set of multiplicative equalities and inequalities, but propagation rules for cumulative could not be derived from those for the primitive constraints

specifies that X is the ith element of [V1,...,Vm] (it may also be required that the Vi are ordered)

The obvious propagation rules then permit the domains for i and for X to be closely linked, in ways which would not be possible if the constraint were re-rewritten in terms of primitive constraints

Omitted