1:05

So the town gate has limited width, it's only four meters wide, and the units of

the army that have to be sent are the hunters, the cooks, very important,

the carts, and the soldiers themselves, and each of those has a width of their

formation and the amount of time it takes to move them through the gate, and

what Hou Yi would like is the whole thing is over and done within 30 minutes.

He needs to get the army out quickly in order to defend.

So the constraints we have to worry about is respecting the gate width.

So we can take the hunters and the cooks, and enter them at the same time,

because they fit across this gate width of four meters.

There's an additional constraint that the hunters have to enter before the carts,

otherwise the horses see the feed in front of them and go crazy, and

what Hou Yi wants to know is when his soldiers should stand by.

So they can be free and relaxed if they're not about to enter, but

if they could be asked to enter the town in the schedule,

then they have to be available, and for this he asks Zhuge Liang for his help.

So he's our gate crossing problem.

We've got N units, each with a a width and a duration to cross the gate, so here is

a four different types of units, and the duration they take to cross the gate, and

the width, and we have some constraints.

So there's time limit of 30 minutes to get everyone in.

There's the gate width limitation, that we can only have four meters of width

entering at any one time, and we’re want the hunters before the carts, and the idea is

to give a better estimate to each of the units at when it has to stand by.

So when it could be possibly asked to go into town, and if it can’t be

possible to be asked and the soldiers can rest outside of that time.

2:59

There's a resource requirement, which is the width, so when they’re traveling

through the gate, they’re going to be taking up a certain amount of width,

that’s the resource requirement and the course is a duration of each of the tasks,

which is how long they take to get through the gate.

So here's our total resource, we have four meters of resource available at all times.

That's a cumulative resource.

3:24

So what we're going to do is in fact propagate the cumulative constraint,

because these people can be free if they're not going to be

in any possible schedule be able to move, so that's exactly what we want to do.

We want to find the tightest bounds for these tasks of when they can possibly

be able to move and so the soldiers have the freest time,

the most amount of free time to relax before they have to actually move.

3:50

So the cumulative constraint, remember takes these arguments,

it has a set of start times, a set of durations, and

a set of resource usages, and then your total resource limit,

and we're saying we got to schedule these N tasks with the start time and durations.

Each of them needing these set of resource units, and

we can only use at most L units available at any particular moment.

4:12

So the cumulative constraint is actually a very complex propagator in general,

and there are many,

many different implementations of the cumulative constraint, and in fact none

of them implement the strongest bound or the strongest domain propagation.

Alright, so they just implement something, which is strong and

fast, but not necessarily the strongest possible,

because it turns out it's not just worth it.

4:35

So how do we model this kind of a problem?

So here's a MiniZinc model.

Here's the variables for start times of each of the tasks.

Of course we have that the hunters have to enter before the carts, and

we have to finish before the end of the whole 30 minute period, and then

really most of the work is this cumulative constraint, just making sure that at any

time we aren't sending more than four meters worth of width through the gate.

So very simple to model with a cumulative constraint,

because basically all of the hard work is done by the cumulative constraint.

5:25

So available resources.

It's not exactly a packing problem,

because we don't actually have to keep the same meters in use.

All right, so let's do some initial propagation.

If we think about the hunters, in order to finish before the carts,

basically they're going to have to start at most at time five,

otherwise there won't be a space here to fit the carts in.

So basically, we have to bring back their bound to here otherwise there's

no way that the carts can be going after the hunters.

5:56

Alright, now let's look at the cumulative propagator.

We're going to use the timetable propagator.

So this is the simplest, basically, propagator that's around for cumulative,

but actually it's one of the most used.

It's actually very, very efficient to implement, and

can propagate quite a lot, enough as it turns out,

that in most problems this is exactly the propagator we want to use.

So it works on this idea of a resource profile.

It keeps track of the times when a task must be running

to make sure that the resources are used up at that time, and

if that tells us that there's not enough resources to put another task in,

we can move that other task to somewhere else.

6:35

Alright so from our initial propagation we have our hunters are fitting here,

our carts are in this range here.

We could fix them, chose to put the hunters here and the carts here,

and then you can see it where, if we're doing that,

then our resource profiles looks like this.

We're using the time that the carts are running, there's only two meters left.

The time that the hunters are going in there's only one meter left.

We're using up that resource during that time.

7:03

So if we shift the hunters back here, if we shift the hunters all the way forward

to there, then no matter what, in all of these schedules,

there's no way the troopers could start earlier than here.

Basically the anyway we can,

the earliest we can start the troopers is we put the hunters as far back as we can,

and then we can start them straight after the hunters are finished.

But there's no way they can fit in the red region,

no matter which way we move the hunters and the carts.

So, that's a kind of reasoning we want to be able to do.

7:33

So, we should be able to immediately say, well, the earliest time the troopers can

start is at time 15, because there's no way we could start them any earlier,

given where the hunters could go, any possible place, the hunters could go, and

the way we're going to reason about this is called compulsory parts.

So we're going to talk about a task, then we have this sort of features of the task.

We have the earliest start time, of course,

that's just the minimum domain value, and we have the latest start time, so

that's the earliest and latest times in could start.

Here, we could start here, or we could start as lately as there, and

then we have this corresponding earliest completion time.

So if we start at the earliest possible then its earliest completion time would

just be adding the duration.

It would get us to that time there, and the latest completion time,

which will be here, that's if we start as late as possible,

then we'll have a latest completion time, and a task has a compulsory part,

which goes from this latest start time to the earliest completion time.

So, if we look at this task, then if we schedule it,

wherever we schedule it, we will be using this amount of resources during this time.

So it has a compulsory part if this is actually an area.

It could be that the latest start time is after the earliest completion time, and

then there is no compulsory part for this task, and

we're going to build up a profile, or what's called a timetable,

as basically the sum of the compulsory parts of all of the tasks.

So basically, we know that this task will be using these resources that it needs

during that time, because for sure, whenever it's running, it'll be

running during that period, and timetable propagation is exactly about this.

So we sum up the compulsory parts, and if that violates the resource bound,

then we know that there's no possible solution,

because we know they'll be some time when we're using too much resource.

We can also do propagation.

So if we look at this current set of compulsory parts,

now if we look at this task here, if we added it here, it would go over the bound.

So there's no way we can put it here.

9:36

So we actually have to move its latest completion time back to there, and

that's going to change the time that it can start.

So that'll be the latest time it can start.

It will be here, and that will in fact give it a new compulsory part,

where it didn't have one before, it will now actually have a compulsory part.

So this is propagation of compulsory parts forcing tasks to move and

then generating new compulsory parts so we can do some more propagation.

10:06

Alright, so

let's have a look at an example using our cumulative timetable propagator.

We look at the hunters here, that's the earliest start time and

earliest completion time, then the latest start time and latest completion time, and

clearly, that's a compulsory part.

So we can just add that into our timetable or resources.

So the hunters are definitely using up the resources in this point.

10:30

Similarly, we'll look at the cooks.

There's their earliest times.

There's their latest times.

No compulsory part, right?

We can see that the earliest completion time is before the latest start time.

There's no compulsary part.

If we look at the carts, we have this earliest times, these latest times, and

obviously that's a compulsary part, so we can add that into our resource.

10:51

Now let's look at the troopers.

So obviously there's no compulsary part in the initial domain.

You can clearly go anywhere, but the troopers can't start before then.

So in the timetable propagation we'll see,

look, there's no way I can fit the troopers before starting for that point.

So first of all we should just move up their earliest start time to be that, and

now, if we look at the earliest start time and the earliest completion time, and

we will find a compulsory part, just in the middle.

11:23

Now let's relook at the cooks.

So now we can see that the cooks could not run at the point here.

They have to end before then.

So we can bring back the latest start time to be there, and now if we looked at

them before, they had no compulsory part, but now they do have a compulsory part.

We can add them in there, and you can see that

we've dropped the domains of two of our variables quite considerably.

11:51

Now, cumulative you can also do via decomposition.

So almost all of our global constraints can be implemented by decompositions as

well, and typically there are disadvantages.

So basically we can do the same thing by keeping track of, for

each time t, what tasks are running.

So this is what this B_it says, it means that if task i is active at time t,

and this just means that the start time is greater or equal to t, and the end time,

which is the start time plus the duration, is less than t.

12:32

And in fact the decomposition of cumulative propagates exactly

the same as the timetable propagator, so often when we build a propagator,

we try to get stronger propagation than we get out of a decomposition.

Here the decomposition will propagate exactly the same

as the timetable propagator.

So, that's interesting so that the decomposition could be that strong.

The problem with the decomposition is the size.

So it basically is this size n, the number of tasks,

times the maximum number of time possibilities in the horizon, and so

that's a very large thing when the time maximum is very big.

So that the decomposition, the complexity of the globe propagators

is only n squared, and in fact we can reduce that by using clearer techniques.

So the problem with the decomposition here is not that it's weak in terms of

propagation with respect to the timetable version of the propagator, it's that it

is just gets too big for problems that we are interested in solving.

There's just too many variables involved, and that's going to slow down the solver.

So in summary, we've looked at global propagation algorithms.

We've looked at two examples of them, and

we've got to remember they're basically the reason for CP's success.

They allow very complex algorithms for combinatorial substructures to work

together, and real-world problems are not pure,

and that's one of the reasons that this global propagation works.

So, often we're combining multiple well-studied problems together, and global

propagators allow us to add a global propagator for this well-studied problem,

a global propagator for that well-studied problem, and let them interface and

talk to each other, because they can communicate through the domains of

the variables that they share, and that allows us to use a strong inference for

each of the subproblems separately, and they work together.