1:40

So, when we're digging tunnels, we can't dig under the huts, okay?

So the huts are actually impervious so

we can't just directly break through the bottom of the hut.

We have to dig to places which are open ground.

So the diggable spots are these ones particularly in the corridors

inside the thing, we can't dig directly to a heart.

Now, once the tunnel is built, then our soldiers are going to jump out of

the tunnel and they're going to run around and attack the bandits.

And basically, what we want to do is get all the bandits quickly.

So we want to be able to get to every hut within a distance of three.

So, that's a Manhattan distance.

The Manhattan distance counts basically the number of steps we take vertically and

horizontally.

So, here the Manhattan distance of three to here because we go one horizontal stop,

then two vertical steps.

So each of these are examples of Manhattan distance 3.

2:44

So, if we open the tunnel here then we could reach all of these positions in red

within a Manhattan distance of 3.

And basically, that's how quickly we want to be there.

So we want to make sure that we're going to cover all of the huts within

a certain Manhattan distance, all right?

So we're going to make sure that huts are covered.

So for example, if we dug a tunnel to here,

we're going to cover these four huts in the corner.

If we dug a tunnel here, we're going to cover these four, right?

With these four tunnels,

we could actually cover all of the huts at Manhattan distance 3.

Unfortunately, Liu Bei and the other heroes only have three digging teams,

so this is not going to be a solution to our problem.

Now there's a cost of digging.

So basically, since the digging starts from over here,

the cost is how far away we are from that position.

So every different slot we can dig to has a different cost.

3:39

And what we're trying to do is minimize the cost of the digging because

effectively that's going to be how much effort we have to pay for

from our diggers.

So let's look at that model.

So we have the size of the bandit's point, so

it's size times size, it's a square bandit camp.

Then the number of points that we're going to dig to is going to

be this number of points and the maximum distance that we can be, so

we can cover where we're going to escape from a tunnel.

What's the maximum distance that we're going to be able to get to

in Manhattan distance to surprise the bandits?

Okay, so for each position in this size by size bandit array, we've got a cost.

How much it costs to dig there?

And then the main decisions, of course, are for each point,

we have to decide which row does that point occur on.

And which column does that point occur on which variables from one to size.

Now, we need that all the tunnel exits are different.

So we could write that this way so basically we're taking the row

number minus 1 and multiplying by size and adding the column number.

And that will map our two decision variables into a single integer and

making sure they're all different will force that the positions that we exit

are all different.

But that's kind of difficult to understand, so can we do better?

Well, we're going to introduce a new construct from MiniZinc to help us

do that.

So the let-in construct is very powerful in fact.

So it allows us to introduce new variables and parameters "any point" in the model, so

any points inverted commas because it's not exactly true.

And we'll come back and look at some of the restrictions of any point later on.

So the format as we say, let and

then we have basically a declaration of the variable.

We could have an expression which we equate it to,

we're going to have to do that for parameters.

And we've got a list of all these normal variable definitions in MiniZinc.

And then we're going to finish that off with a close brace and in.

And then, we have the expression for

which these local variables are going to be available.

So the parameters, if we introduce a parameter in this we must have a defining

expression because otherwise there's no way to get that parameter value to that

parameter variable.

And basically, we've gotta remember that anything we define in

this let expression is only going to be visible in this expression here,

the one after the in, and not for the remainder of the model.

So let's see how to use let.

So here, we're going to build an explicit array for

each of the points of this particular integer, right?

Which is going to vary from one to psi squared which is the points.

So it's exactly the same expression we did before.

So we take the row number minus 1 times the size plus the column number.

So we're going to build up this array and

then we can just say, alldifferent of this set of values.

Okay, this makes the definition easier to understand,

because we're basically explicitly showing you what's going on.

It's not going to create actually anything different really,

in the underlying solver.

We're just going to make our model easier to understand, and easier to modify.

7:33

Now, we need to make sure that all the building are covered.

So here's an example of where we can use a predicate, and

we're using some local variables to define that predicate.

So, do we cover a building on the position x, y?

This is what this predicate is meant to ensure.

So if we do cover a building on x, y,

there must be a point within a Manhattan distance of mDist from that building.

So we're introducing a local variable, i,

which is going to guess basically which exit point we're using.

And then we're going to calculate the distance from x, y to this exit point.

So the distance from x, y is just the position x minus the row of i,

the absolute value,.

Plus the absolute value of the y-th coordinate,

the column coordinate for the position we're looking at covering,

minus the column where we find the particular point we've picked.

So we're going to calculate that distance and then, say,

well that distance must be less than the maximum distance that we're

allowed in that model, in our example, which is 3.

So this is a predicate, which is going to test where this position x, y is covered.

And notice we're doing something quite clever here.

We're actually allowing it to pick which point is covering it.

So basically,

there's a pseudo decision here about which point is going to cover it.

Now, how do we apply the constraint?

So let's build basically the even numbers, right,

the huts occur on the even numbers, which is from i is 1 to size div 2 i times 2.

Let's build that array and then we'll say, forall i, j in huts.

So basically, picking all row columns in these even numbers,

we're going to check that it's covered.

All right, so we can see that by building this cover constraint,

we've made it clear what we're trying to do.

And then we're using this cover constraint on each of the hut positions,

improving readability and modularity.

Now finally, the objective we're trying to minimize the total cost of building, so

that's basically looking up the row and column.

Looking at the cost value for digging to that point and minimizing the total cost.

And if we can run their model, we'll find that we can actually cover the bandits

with only three points, if we pick these three points, and our cost is 18.

So, just to show you another use of let-in,

if we go back to the patrol problem we saw a number of lectures ago.

Then we needed that in every day,

the number of soldiers on evening shift was greater than equal some lower bound.

And every day the number of soldiers on the evening shift was less than equals to

some upper bound.

Well, another way we could do this rather than introducing direct common

subexpression based for this, we could just do it the same by using a local

variable to build up that expression that we're going to use twice.

So here, for each day, we're going to build a new local variable,

which is how many are on evening shift which is just this value, right?

The sum of the soldiers are on evening shift on that particular day.

And then we're going to add these constraints

that l is less or equal to u and on is less or equal to u.

Which is going to enforce these two constraints, so we're building a common

sub-expression but we're just using a local variable to do that.

It's often easier than building an array of intermediates,

which is what we did last time.

We were basically adding some global decisions into our model and

then use them in multiple places.

If we're only going to use them in one local place, we just add a local name for

this particular common subexpression and then reuse that local name.

So, let's look at another use of let-in.

Suppose our solver does not support division,

then we can actually define division using multiplication.

because really from a relation perspective,

they're really the same thing, like plus and minus are really the same relation.

11:31

I only do it for non-negative numbers because it makes it simpler.

But if that's the case, then if I were to write that x div y = z,

it's really the same as saying this.

That there is a number, if I multiply z times y and

add in some extra remainder, then I would get x.

And I need that this remainder is between 0 and

less than y, so these are two equivalent statements.

We can define division in terms of multiplication by these constraints.

But we need a new variable for this remainder and so

this is a perfect example of where to use a let to introduce that new variable, so

here's a predicate defining division.

So here's the actual arguments we're interested in, x and y and z, and

we're going to introduce this local variable r,

which is going to take a value from 0 to the upper bound of (y)- 1.

So we can't use y here, because y is not a decision, so far.

We have to give it a fixed range, so

we're taking the largest possible value that y could take, -1.

And then, we just write down our constraints, so x = z * y + r,

and r is less than y.

Okay, of course the actual value of y will constrain r as well.

But any time we introduce a local variable,

we should try to introduce very tight bounds on its possible values.

That's going to make our model much more efficient.

So what happens, we should think how does this work with division by 0.

Well, if y is set to 0, then this constraint will fail, right?

Because r has to be 0 or bigger, so this will have no solution and

that's what we want.

Remember the relational semantics says, if we divide by 0,

the constraint should be false and so this division constraint will return false.

What happens with division by negative where you can see that if we

add in a negative number then this will also fail?

And so, it's not really correct because there are,

you can do division with negatives, this version of the predicate is only

meant to work when we're doing non-negative numbers.

13:37

So, if we ever make an assumption in our model,

we should really check it using assert.

So we can do that by using a new form of an assertion that is specifically

useful because of things like predicates.

So our division predicate was only really meant to work if the lower bound of y was

greater than or equal to 0.

That is that y was definitely not going to be a negative number.

And so, this is our version of assert which says,

okay, if this test holds then we just give you the regular definition.

Otherwise, we're going to print out an error message and abort, right?

So this is good, it documents the assumption we made about this predicate.

It's only meant to work when y takes a positive value and

it prevents the misuse of this predicate.

15:02

Now we gotta be careful because these bounds are not

guaranteed to be the declared bounds.

They're guaranteed to be correct bounds on the variable we were talking about.

So for example with this little snippet of code here, if we ask for

the lower bound of x, then MiniZinc could return 0.

Because well, x is the result of an absolute value call, so

it's definitely going to be a positive value.

It could return -4, that was the declared lower bound of x, so

that definitely is a lower bound to any possible value that x could take.

Or it could return 2,

because if we propagate this constraint just looking at the possible values

of y between -4 and -2, it means in fact that x has to take values between 2 and 4.

So all of these are correct lower bounds on x.

And you can't rely

on which one of these you get when you're using the lower bound code.

You can probably rely on the fact that we'll always get no worse than

the declared lower bound, if there is one, because it'll be impossible for

MiniZinc to lose that information.

And we'll see that this assertion that we've used here,

this new form of the assertion takes three arguments.

The previous version only took the first two arguments.

16:45

So in summary, let-in expressions are actually a very powerful way of

introducing parameters and variables for use locally.

So we introduce a parameter basically if we want to build

some complicated expression and use it in multiple places.

That's very handy.

Similarly we use variables if we want to build some local decision or

common subexpression, we can use it locally or

we want to make a new local guess, basically a local decision.

As we saw in the covered constraint where we added a point variable which was going

to basically check which point it was covered the hut we were interested in.

Whenever we define local parameters, they must be defined by this expression,

because that's the only way they're going to get a fixed value.

But local decisions don't have to be covered.

And what let-in does is help us modulize expressions and improve the readability of

our model, and basically remove common subexpressions in another way.