0:02

[MUSIC]

Nuwa was still concerned about the stability of the sky after it was patched.

She knew that there was a giant turtle with legs strong enough to act as pillars

to support the sky.

With a magic spell, Nuwa obtained parts of the turtle's legs and

placed these at four different points on the ground.

0:34

It attempted to move away the foot placed at the northern point

to jeopardize the stability of the sky.

But it could only move this leg along certain lines, or dragon veins, and

nowhere else.

Nuwa however,

could only move the leg to points of the intersection between two dragon veins.

And along the lines of what was known as a stability diamond.

0:55

To avoid the risk that the turtle might move the foot again,

in order to destabilize the sky, Nuwa needed to remove some dragon veins.

Again, she sought help from Zhuge Liang, who summoned the Dragon of Dimensions for

assistance from the professors.

1:11

>> So the Great Turtle's Challenge to Nuwa.

Every day he's going to pick either horizontal vein,

dragon vein, or a vertical dragon vein.

And she has to place a turtle egg on the intersection of the one he picked with

one in the other direction.

1:28

But not only that, of course the North Pole is where the sky is held up and

there's a stability diamond around the North Pole.

And the turtle egg also has to be placed on the stability diamond.

So it needs to be on the intersection of horizontal and

vertical dragon vein and on the stability diamond as well.

1:55

So the sneaky Dragon Turtle of course has this problem.

He can pick a dragon vein like this one where there are no points

that are also on of vertical dragon vein, which will fit on the stability diamond.

So if we have a look at all of the intersection points of this dragon vein

2:30

So we can think about this in this way.

We've got a set of possible vertical dragon veins, lets call that D(X).

And a set of possible horizontal dragon veins, call that D(Y).

And then the stability conditions are, we need to find an X in the D(X),

so that's a vertical dragon vein,

and a Y in D(Y), that's a horizontal dragon vein,

that also satisfies this constraint, which is the stability diamond.

The absolute value of X plus the absolute value of Y is 10.

2:57

And, really, we want to find the largest possible set,

so basically whatever dragon vein the turtle chose,

there will be a place that will satisfy all these constraints.

So we're trying to find the largest subset D prime (X) of D(X) and

the largest D prime (Y) of D(Y).

Such that, for every X which is in this set

then there is a corresponding Y in the D(Y) which satisfies all the constraints.

And similarly, for every Y there is an X.

3:30

So, what we're going to do is examine each of the existing vertical dragon veins

in turn.

And then eliminate the ones that don't have a supporting horizontal dragon vein.

So if we look at this vertical dragon vein.

We can look at all of the intersection points with horizontal dragon veins, and

we see that none of them occur on the stabilty diamond.

Which means that, we can't allow the turtle to choose this vein, so

we should remove it from possibility.

Similarly we can look at this one,

we can look at each of its intersections with the horizontal dragon veins,

and again, we see that none of them appear on the stability diamond.

So we should remove it from consideration.

And we can keep going, so this one also gets removed.

This one has got a point on the stability diamond, there it is.

So we can keep that vein.

4:19

This one, again, has a stability point,

this one as well, this one as well, and this one doesn't.

Right, so we've removed all of the vertical dragon veins,

which had no horizontal support.

Now we'll need to do the same for the horizontal dragon veins, looking for

a vertical support.

So if we look at this one here, it has no intersection, as far as I can tell.

And we look at this one here So the second one down,

this of course does have an intersection with stability diamond.

4:53

We'll look at this one down here and

we'll find no intersection, so we should remove it.

We look at this one here, we will find an intersection.

This one, no intersection, no intersection and no intersection.

5:06

So after we've removed all of these dragon veins,

we can see no matter how the Great Turtle chooses a dragon vein, vertical or

horizontal,

Nuwa will always be able to find one of these green points, an intersection point

of a horizontal and a vertical dragon vein which is on the stability diamond.

So whichever vales the Great Turtle picks, Nuwa will be able to find

the other corresponding value which satisfies the constraint.

So, let's try to understand what we've been doing in terms of propagation engines.

So these vertical dragon veins are our variable X and they're basically

representing the different position values we could take for variable X.

And our horizontal dragon veins are the variable Y,

and each Y represents a position value for the variable Y.

And the stability diamond is of course this constraint,

that the absolute value of X, and the absolute value of Y is equal to 10.

6:05

And so what we've done here is we've been reasoning about this constraint,

about the absolute value of X, and absolute value of Y is equal to 10.

And we're reducing the possible values of the variables X and Y.

And you can see these domains represent the possible values of the variables.

And the propagator that we've been talking about, the propagator for

this particular constraint,

absolute value of X plus the absolute value of Y equals 10,

is representing the constraints.

The propagator's the algorithm that we did to get rid of

values which were no longer possible, given the current domain.

6:39

So that's the core of a propagation engine.

We're going to record for every variable, its domain.

So its a set of possible values,

and we're going to use this D(X) notation and usually D(X) is finite.

We're doing discreet optimization, mainly we're talking about finite problems, but

it could be very large.

So all 32-bit integers, there's a large number of those.

It could even be all 64-bit floating point numbers between 0 and 1,

there's still a large number of those.

7:14

So essentially, the variable X represents a choice, right?

Which of these possible values are we going to take?

And the domain of X represents the possible choices for X,

snd as we go through, that domain will change,

it will be reduced, we'll get less and less possible choices.

And we may get down to the point where X has no choices left,

and that's what we call a false domain.

And that means that this domain, there is no solution,

because if there's no value for X, there's no value for the whole problem,

because if we can't get one variable of value,

I can't give a solution to the whole problem.

7:46

So the other thing we need to know about is valuation.

So valuations is a mapping from variables to values.

So X is mapped to 3 and Y is mapped to 4.

And so of course our solutions are going to be of this kind of find.

And we're going to use this notation so we say theta of X is 3.

So theta is this valuation here.

So it maps variables to values.

So theta of X gives you 3, and theta of Y gives me 4.

And the variables in theta, so

the variables are actually given a value of X and Y.

And we'll also say that a valuation theta is in the domain if

this theta of X is in D(X) for each of the variables in vars(theta).

So here we have two variables X.

So 3 has to be in the domain of X.

And 4 has to be in the domain of Y, in which case theta would be in D.

8:42

And there's another technical thing we might use here as a valuation domain.

So we can think about a valuation as a domain itself, so

a valuation domain just maps X to the single set of single possible values,

which is theta of X, right?

So, there's a particular kind of domain just is equal to a valuation.

So you can see D(X) equals 3 and

D(Y) equals 4 would be the valuation domain for this valuation.

Alright, so what are constraints?

So technically, a constraint is really just a set of valuations,

which are solutions, over the set of variables which make it up.

So you can think about X not equal to Y, if we have the domains of X and

Y that we'll ever talk about are 1, 2, and 3.

And we get this set of six possible solutions, six valuations.

And similarly, if the domains of X and Y are colours, and

we're going to get another set of valuations over these colours.

And if we think about the constraint X equals Y plus 1,

then a couple of example valuations, which satisfy this constraint,

are these X is 2 and Y is 1, or X is 3 and Y is 2.

In general, you can see that these constraint represented as a set of

valuations and solutions could be very, very large.

So typically, we won't think about constraints in that way,

because this is what they are formally speaking -

they're just a set of solutions.

10:02

So, how we are going to deal with constraints is via propagators.

So a propagator f for some constraint c is a function from domains to domain.

So it takes an incoming domain, so that's a set of possible values for

its variables, and gives you a new domain,

which is hopefully a reduced set of possible values for its variables.

So it's meant to be monotonically decreasing.

That is, when I apply this propagator to a domain,

I always get back a domain which is less than or equal to what I started off with.

So basically, variable values can only disappear, they can't be added.

That would be a rather strange thing in this case, where we're trying to

reason about values that are impossible then just values should disappear.

10:44

Now we need this propagator to be correct for this constraint,

and hat that means is that it never removes the value which occurs in the solution

of c given the current domain.

So we can think of that technically as we take any valuation which is in the current

domain and which is also a solution of c,

then that valuation should still be in the result of

the domain after I apply that propagator f.

So that's the first thing that we need about a propagator,

it never removes the correct solution, that would be just wrong,

and if we do that we'll get the wrong behaviour.

We're going to ask for one more thing from our propagators and

that is that they're checking.

This means that if all the variables in c are fixed,

that is they have a domain which is a size of exactly 1,

then it returns a false domain unless this is a solution.

So basically if we get back to everything is fixed,

then we've got a valuation domain,

and we should basically get the same domain back if we apply f,

so nothing should change, if an only if theta is a solution of c.

If we have a valuation domain D theta which is not a solution of c,

we should get back a false domain saying there is no solution,

otherwise we get back the original domain.

And that means we know that once we fixed all the variables

each of these propagators will basically check if it's true or false

and will certainly answer the question.

12:03

So, let's look at an example propagator for X equals Y plus 1.

So, we can represent this, like this way.

So we can say, well, we're going to change the domain of X like this,

we're just going to intersect the domain of X with this range, right?

The minimum value which occurs in the domain of Y, with 1 added to it,

and the maximum value, which occurs in the range of Y with 1 added to it.

And you can see how this expression here relate to this X equals Y plus 1 up here.

And we're going to do nothing for Y, we're just going to leave it as it is.

So notice that this is correct, even though it never modifies domain Y.

In fact, an identity propagator, which never removes anything,

is clearly correct, alright?

So I ask you the question, is this checking?

Will this give you the right answer if I give it evaluation domain?

The answer is yes, actually.

13:01

and the best one, the strongest propagator we can build for a constraint,

is one that removes all the values that don't take part in any solution of c

which is also in the domain D

and we call this the domain propagator for c.

There is no better form of propagation on this in terms of the strength of its

inference, right?

So we can always define this basically theoretically speaking we take

the current domain of a variable X,

we look at all the solutions and all the values that X gets and

all those solutions of c, which are also in the current domain,

and we just intersect it with that.

And that will for

sure get rid of every value of X which doesn't occur in any solution because

that's basically the definition of what we've written down there.

13:51

So we have another concept,

so if we look at all the variables in c one at a time, and

we look at all the values left in their domain,

14:00

and for each of those, we can find a value for each of the other

variables in their current domain, which is a solution, right?

Then we're saying these vi's are called the supports of these vi primes,

of the supports of vi, right?

For our variable here, vj is a support of vi.

14:22

So, if this is the case, then our domain propagator can do nothing,

so it basically means that every value for

every variable has a support in other values for other variables in terms of a solution.

And that's what we call a demain consistent domain.

So this domain D which satisfies this condition for

some constraint c is domain consistent with respect to c.

Which means that no propagator could infer anything more if we're in this domain.

14:53

So example domain propagators,

so we've implemented domain propagator for

our stable pillar problem using a simple double for-loop so,

and of course, that's just the constraint.

The absolute value of X plus the absolute value of Y equals 10.

And we basically, implement it by brute force.

We went through every possible value of X, checked every possible way of Y.

And removed the ones which didn't satisfy this stability condition.

15:27

So here is how we do it,

it's very simple actually because there's very little inference we can do with this

constraint.

So here's half of it.

How do we change the domain of X for this constraint?

Well if the domain of Y is a single value D,

then we know that X can't be that value so

we just subtract D from the current domain,

15:47

and otherwise we do nothing.

So that's how we change X, and of course since this is a symmetric constraint,

we change Y symmetrically.

And in fact, this propagator is a domain propagator,

it does everything you can possibly do.

And, you can think about it this way, if X and Y

both have two values left, then there's a solution for either of those two values.

16:10

So linear constraints are actually the most common constraint that we use in modeling

so this is the sum of ai xi equals b or we can have a linear inequality,

the sum of ai xi less or equal to b.

So these are very, very important constraints, you will have seen them throughout your modelling experience.

So we're going to think about the result of domain propagation

of these kind of things.

So let's look at X equals 3Y plus 5Z,

where we have these current domains of X, Y, and Z.

16:39

So domain propagation, remember, only keeps the values that occur in a solution.

So if we think about this constraint and these domains,

there are actually only three solutions possible, alright,

these ones, (3,1,0), (5,0,1) and (6,2,0) for the values X, Y, Z in order.

16:56

Which means a domain propagator should give me back these domains, right?

(3, 5, 6) so 3, 5 and 6, the values that X took.

(0,1,2), so we've got 1,0, and we got 2 for Y, and for

Z we only got 0s and 1s, right?

So that is what a domain propagator should do.

17:16

So the question is, how hard is this to solve, right,

if we wanted to do domain propagation on an arbitrary linear equation, well,

is it linear, do we just basically have to scan through once?

Or is it some kind of sorting complexity where I have to do some kind of sorting of

the domains and then get the result?

Or is it quadratic, perhaps, because I have to look at every pair of variables?

Or is it actually NP-hard?

17:41

So it's actually NP hard, which is surprising right?

Why is a constraint so basic, and so,

at least simple to solve independently, hard to do domain propagation?

17:54

So we can ask the same question for the linear inequality.

Alright, so now I've just changed it so

it's an inequality so how does does this change it?

Does it make it easier, is it linear, is it sorting, is it quadratic, or

is it NP-hard?

Well it turns out that this becomes linear.

18:14

So we've seen a propagation algorithm in

action, where we've actually removed values from the domains of X and

Y in order to satisfy this stability diamond constraint.

But of course for Nuwa this was problematic,

because if you looked at what happened, lots and lots of, she had to remove lots

and lots of dragon veins to stop the Great Turtle from causing problems

and dragon veins are precious.

So in the next lecture we'll look at how to do a different thing and

keep hold of more of these dragon veins.