In the last lecture we tried to solve the shift patrol problem. And we built a model, and it did actually work but it took a long long time. Didn't seem that hard a problem, and it took a long time to solve. So what went wrong? Let's look at our model. So, the shift requirement constraints said that they had to be o soldiers on the night shift and that was the top level constraints here and between l and u soldiers on each evening shift. And we can see there were two constraints there basically saying they had to be grand equal to l on each evening shift and less than equal to u on each evening shift. And we can see that there is an expression here that evaluates the number of soldiers on each evening shift that we're building twice. And that's a Common Subexpression. Now every time we have a common subexpression in our model, then we have to be careful because if that subexpression goes to the solver and we end up building it twice then the solver had two different representations of the same thing. And that can duplicate the amount of work it does. Now menu will try to notice common subexpressions and eliminate them for you but if you can avoid doing them yourself, then that'll always be better. So intermediate variables gives us the ability to introduce a new variable into our problem just to store some comments of expression. So they're not really new decisions but they're just storing some expression that we're going to use multiple times In our model. So, here we're introducing an intermediate expression onEve, we're just going to count the number of soldiers that are on the evening roster for each day. And so, we can just calculate that by summing up the number of soldiers on each evening roster, and with that array, now we can build our constraints on everyday. The number or soldiers on eve is greater than equal to L and less than equal to u. Just like we did before but here, we've certainly only got one expression, counting the number of times a soldier, how many soldiers are on each evening, roster. So we can do it this way by building this expression here and then evaluating what that expression is and then having a constraint making sure they're between L and U. We could do it more simply by just saying when we build this expression onEve, we know that each of these variables has to between L and u. So that's going to force those constraints that each evening roster has between L and u, soldier on it. And then we can evaluate the onEve to count up the number of soldiers on the evening roster. Now we should also look throughout our model a bit further and find out that there is another place where we counted the number of soldiers on the evening roster because remember what we we're trying to maximize is the number of soldiers on the evening roster. So that's another use of this common subExpression which we can also replace with our new common subExpression named variable so we can get rid of that as well. So if we look through our entire model, we've got our data declarations at the top. Here's the decisions, our roster. Then there's constraints about the number of night shifts you can take in a row not being able to take a night shift directly after an evening shift. And then our constraints for hidden individual rosters where we're counting that the number of people on night shifts each day is O. Here's the constraints that we just defined, about making sure that the number of people on evening shift is correct, and our objective function, which is just summing up the number of people on the evening shift. Much more concise. And the new version of our model now solves in 4.5 seconds, much less than it was before, the ten minutes. So, obviously, we've found a common subexpression, removed that, and that's made the model much more effective for the solver. So what we're talking about here in the rostering problem, shift patrol problem is a partitioning problem. What we're trying to do is partition our soldiers into three different classes. They're either on night shift or evening shift or no shift at all. And we're interested in the size of those partitions. So we want to make sure that every night shift has O soldiers on it and every evening shift has between L and U soldiers on it. And there are special constraints for this kind of partitioning. And what we're going to introduce here is the global cardinality constraint. So the global cardinality constraint is going to count the number of values in X that fall in different partitions. So the size of these two arguments, v and c are the same. And what it does is constrain that the number of values that x take the value vi, is counted by the value ci. So it collects the counts, and bounds the number of counts by the number of occurrences of vi. So that might sound little complicated. Let's look at an example. So if you look at global cardinality here this is that the number of ones that occur in the array x should be 2, and the number of 2s that occur in the array x should be 1. So this is telling you the values that we're counting, and this is telling you the counts of the values. So for this example, this is the correct answer. There are two 1s and one 2 in the answer. And this is an incorrect answer because there's only one 1 where we needed two 1s. And notice we're not counting the 3s and the 4s. We're not interested in counting those because they don't occur in these values of interest part. So, that's a global_cardinality constraint, another substructure of interest. And we can use that to replace all of this information about the rosters by just one single constraint. So, if we take all of our information about rosters, we can replace it with just one single constraint by saying this. Well, we're going to count the number of nights. Number of soldiers on night shift on evening shift on every day and it should be o for night shift and on evening shift it should be the number people on evening shift for that day. So notice what we're doing here is we're actually using this to actually do our counting to set the value of this variable, this is our evening shift variable. Which is going to take values between L and u. So, rather than, before, we actually had an expression to count on eve, we're using global_cardinality to evaluate this expression for us. And then we're using the bounds, here, and the definition of that variable to enforce the constraint that we wanted. Then there are variance of global cardinality, because sometimes we want to do different things. So sometimes we don't want to ignore the other values. We want to count every possible value. So global cardinality closed says that we're going to count the values in x and the different values v. And their counts have to be equal to c. But there can't be any other values in this x which aren't counted by V. So in our example back a few slides here where we have a value 3 which wasn't counted, this would no longer be allowed. So every value that occurs in the X array, has to occur in the V array. So, that's global_cardinality clause, that's a notion of clause, we can have values that aren't counted, and we can have a simpler values of global_cardinality, the global_cardinality_low_up, which just has lower and upper bounds on the count. So, we're not, here we're actually giving you the exact count, how many values in x took the value v for each particular value. Here we're just going to put lower and upper bounds on the count. So, we're going to count the number of A's in the X array which take the particular value of V. And we're going to say it's between some lower bound and upper bound and we could use that instead and this obviously a version which combines those two. Where we just had the lower and upper and we have the closed condition as well so that no other value occurs. So the different variations of the Global Cardinality Constraint which we can use depending on the exact constraint that we need for our model. So if we go back to our full model again the decisions. Here's our constraints about an individual roster. And now we can basically do with one global_cardinality constraint, we can define the number of night shifts and the evening shifts, and in fact also evaluate the number of soldiers here on evening shift which we can then use In our objective function. Now, this version because we've put all of that constraints together in one global cardinality constraint our solver is going to be more effective and it can solve it faster. And in subsequent courses in this specialization, we’ll explain how modeling can affect solving efficiency. So in summary, there are many discrete optimization problems which end up deciding a function from a domain to a co-domain. And you can see this as partitioning a domain into sets labeled by codomain. And this partition view is useful when we reason about these sets F(c). This is the pseudo-inverse of f. And when we have this partition view. We can think about cardinality constraints, and that cardinality constraints, where we're saying, how many of these elements of the domain fall into these sets labeled by things by the codomain? Absolutely captured by this global_cardinality family of global constraints. So, the global_cardinality family captures this common combinatorial substructure of partitioning with cardinality constraints on the partitions. And we've also seen a very important thing in modeling is, whenever we build common subexpressions, if we can detect them. Name them and I only build them once, then we're likely to have much more effective models. And we've introduced logical connectives, which are going to be very powerful for us to build much more complicated models than we've seen before.