After several victories, Liu Bei wanted to arrange a patrol team to work in shifts and watch out for potential assaults. Three soldiers were needed for the night shift. No soldiers were needed for the day shift. And ideally, two soldiers were needed for the evening shift. Although one soldier was acceptable. To save the soldier's energy, no soldiers could patrol for more than two night shifts in a row, or patrol on an evening shift immediately followed by night shift. Liu Bei wanted to put together a patrol shift roster that satisfied all of these requirements, and that would ensure as many soldiers work evening shifts as possible. He picked up his magical tablet to ask for help. So Liu Bei is worried about a possibly impending attack by Dong Jur and so, he needs to patrol. So this leads us to the shift patrolling problem. So, he wants exactly three soldiers on each night shift. So there are the most numbers soldiers out there to make sure there’s no possible night attack. There’s no need for patrolling in the day time in the sense there’s a lot of soldiers around and any movement by Dong Jur's troops will be easily spotted. During the evening, there can be two soldiers on the shift or one, both are possible, there’s less danger. Now, this gives him the shift patrolling problem. How on Earth can he organize his soldiers in order that their shifts are maintained. Because it's not that he can arbitrarily put any number of soldiers on any set of shifts. So a single soldier can't have more than two consecutive night shifts in a row. So if we have three night shifts in a row like this. Then the soldier basically will loose so much sleep that they'll be ineffective, and on the third night shift, they'll basically be non-functioning, and this will not be an effective patrol. So that's just not going to work. And they can't have a night shift after an evening shift. So basically, if they spent all this time in the evening shift and have been go directly to a night shift, they just not going to be effective on that night shift. And so, that would be an ineffective approach. So that's not going to be allowed either. And so of course, to be most safe, we want to maximize the number of soldiers on the evening shift. So we'd rather have many more soldiers on the evening shift. That's going to be much safer than just having a few soldiers on the evening shift, so that's going to be our objective. And so, our shift patrolling problem is basically to make sure that for each individual soldier, they get a roster which is correct, like this one here, which doesn't break any of the rules. Doesn't have three consecutive night shifts and it doesn't have a night shift directly after an evening shift, like this one here. And it's still manages to make sure that we have three soldiers on night shift every night, and one or two soldiers on evening shift everyday. And this is going to turn out to be a kind of partitioning problem. What we're going to do is find a function from a domain to a codomain. And just like we have been for the rest of this section, it's a partitioning problem. So this will give us additional insight, rather then think about it as building a function, we think about partitioning out domain into sets labeled by the codomain. And if you think about this is building a kind of pseudo-inverse function, right? Which maps from the codomain to the subsets of the domain, which are all distinct. So this is another way about thinking about building functions, by building this pseudo-inverse version of the function. So let's think about building our shift patrolling problem, which is an example of a rostering problem, just like many modern day rostering problems. So, we've got two enumerative types, the set of soldiers that we're going to roster and the set of shifts. And we have a number of days that we need to build the roster over. We also have the number of required soldiers for a night shift and a lower and upper bound on the number of soldiers for an evening shift. So, what are the decisions that we need to make? Well, the objects of the domain are for each soldier and for each day. So that's our domain. And the objects of the codomain are the shifts. So for each soldier and for each day, we have to choose a shift. So there are our decisions. An array for each soldier and for each day, which shift does it take? And that's our roster. So there's another view of this, taking our pseudo-inverse view as a partitioning problem. And we can think about this by partitioning the soldiers by shift type. So for each day, we can think about the soldiers, they can have a night shift, an evening shift, or no shift at all. Basically, we can be partition in our soldiers into three sets. So we can reason about these sets of soldiers that are on a shift, a night shift, an evening shift, or no shift at all on that particular day. So, now we have to think about how we roster our pattern constraints. How we express them, so we can express no two night shifts in a row. Well, in order to do that, we're going to have to, one way to do it is we can look at every three days in a row. So that's what we're doing here. We start from case one K1 to the last everyday with the last two days. And then we sum over those three days from K to K+2. And we count up the number of night shifts that this soldier, S has in that time, and it has to be less than or equal to two. So that's going to make sure that soldier S does not have these three night shifts in a row. It's not very clear, it's quite subtle, and it's quite difficult to generalize this to more difficult patterns. So a better way of doing this is to use logical connectives. So, instead, let's look at this expression of the problem. So, this says, okay, if soldier S on day D has a night shift, and if soldier S on day D+1 has a night shift. So he just had two night shifts in a row, then on day D+2, they can't have a night shift. So that's more or less explicitly saying, if you have two night shift's in a row, you can't have a night shift in the next thing. First, and basically an explicit rule preventing three night shifts in a row. And we can do a similar thing for the evening shift followed by a night shift. So, if on day D, soldier S has an evening shift, then on day D+1, they can't have a night shift. So, you can see that using this logical connectives, we can very straightforwardly express this complicated pattern constraints. So, logical connectives is an important part of modeling in MiniZinc, and we're going to use this extensively in lots of models, later on. So, true and false, obvious Boolean expressions, would just mean true and false. Conjunction means, is and. We write it this way in MiniZinc. Disjunction is, or. Implication, we've seen they're used, and by implication or equality between two Booleans. So these are the usual Boolean operators, negation as well, although negation is very hard to use effectively in modeling without getting into all kinds of trouble, and we'll look into that later on. So these Boolean connectives are going to allow us to build very complicated and powerful constraints. But beware if we start combining logical operators and global constraints, we're going to get into some difficulties, and we'll talk about that more later in the course. So, we have some other constraints, which is the shift requirement constraints. Remember, we require that there are exactly O soldiers on night shift every day. So that's fairly straightforward. We just have to look at everyday. We sum up across the soldiers. The number of those that have a night shift has to be equal to O. And then we have to do the same thing for evening shifts. So we know that for every day, the number of soldiers that have an evening shift have to be greater than or equal to L. And the number of soldiers that have an evening shifts have to be less or equal to U. So you can add those two constraints and we've enforced that our shift requirement constraints are met. And of course, our objective is that there should be as many soldiers on patrol in the evening as possible. And all we need to do there is count how many soldiers are on an evening shift. So basically, summing out for each day and for each soldier the number of soldiers on evening shift and maximize that number. So we can put that all together in one big model, right? There's our data, declarations, and decisions. Here's our constraints about the individual soldiers rosters being correct, no three night shifts in a row, no evening shifts followed by a night shift. Here's our constraints on the roster itself, having enough people on night shift and enough people on evening shift, or not too many people on evening shift. And finally, our objective. And there's our entire model. So now it's time to solve the model. So we asked it to run. It's solving, solving, solving. Nothing, after five minutes. Doesn't seem that complicated. Finally, a solution after 10.5 minutes. So what's going on? If we reduce the number of days to six, in fact, the more we can find an optimal solution after only seven seconds. It seems that this problem doesn't look that hard, so why is it taking so long to solve? This is a problem you'll find very commonly when we're solving discreet optimization problems. But very small problems can take a long time to solve. There is a problem with the problem itself or is it a problem with the model? So, we're going to find out what went wrong in the next lecture.