Hou Yi wanted to shorten the time needed for an army to enter a village through its front gate, as attacks from the monsters could be sudden. Within an army there were four units of different widths, each requiring different amounts of time to pass through the gate. Also, each unit itself had to pass through the gate continuously to maintain the formation. More than one unit could go through the gate simultaneously, but the limited gate width had to be considered. Moreover, the hunters had to enter the village before the cards, and the whole army had to pass through the gate within half an hour. Hou Yi wanted to estimate when its units should be ready to pass through and asked Zhuge Liang for help. Zhuge Liang summoned the dragon of dimensions for assistance from the professors. So Hou Yi has to send armies to enter these towns to protect them, and unfortunately if he just sends them higgledy-piggledy then there's big kerfuffle in front of the gate, the narrow gate to entering the town. 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. Alright, so drawing the parallel, what we have here is each of these units is a task that we’re going to schedule. 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. So this is exactly the cumulative constraint. 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. 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. 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. 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. And you can think of it like a packing problem. Really we have these resources of meters of gate, and we have 30 minutes of time, and basically we want to pack these boxes, which represent the duration and the number of meters of the gate width that we need into this box. 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. 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. 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. So then, let's think about where the troopers can go. 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. 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. 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. 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. 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. 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. We could add that into our timetable. 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. 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. And then we can impose this constraint that at every time, if we take the tasks which are running and multiply them by the amount of resources they need, it has to be greater or less than this global limit. 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.
