A new strategy for attacking three wolves was discovered and suggested by Liu Bei. But Cao Cao worked out an even better strategy for attacking only two wolves. Liu Bei was confused. He discussed this further with Guan Yu and Jung Fei. They all failed to understand why the tablet didn't provide them with the best strategy. Lui Bei took out the magical tablet to figure out what was wrong. [SOUND] >> So Lui Bei has three squads to attack the army but that doesn't mean that he has to attack in three different positions. It means that he can attack at most three different positions. And if we think back to the greedy solution which attacked two different positions for damage 20. That's actually a better solution than we saw in the last lecture where we attacked three positions for a value of 19. So the real question that we need to answer is how do we select a set of at most size 3 that will do the maximum damage. So let's look at that question. So it's easy if we've got the variable set version of this problem to change a model to do a bounded cardinality version of the model. So all we needed to do is change this constraint here which used to say. The card and area of attacks equals the size to the covenant is listening for the size. That's the only change we need to make. And we're fine, we execute the model and we get, in fact, exactly the same solution as the greeting model that we should attack positions 1 and 10 for damage of 20. But, what about an integer model? We saw in the last lecture that If you had fixed cardinality set, then there was a different way of representing it, which could be advantageous if we are picking a very small set from a very large set of possibilities. Can we do the same if we're picking a bounded cardinality set? So not a fixed cardinality set. But where we have a bound on the number of possible values. Well we can, but we're going to have to do some more work to make this work correctly. So again, we have an array from one to size of decisions. But they're not just spots we're going to pick. We have to be able to pick from an extended set of spots. So not just the spots, but an extra value we're going to add, into our decisions here of where to attack. And these extra values basically only represent no element. So sometimes we're going to not attack a spot and that's going to allow us to get a set of smaller cardinality than size. So some of the things in this array represent no attack whatsoever. And that's going to allow us to have a cardinality less than size in our total representation. So for an example, now spots are represented from 1 to n spots, and we're going to use extended spots from 0 to n spots, so the value 0 to represent this extra null element. So of course there is two critical issues that we talked about that we have to worry about when we are building up the representation of decisions in our problem in terms of how we model it in a model. So every solution in the model has to represent a solution in the problem. So we want to avoid things like this [3,0,3]. Has repeated values in it. So that has to be avoided because we're going to have two 3s, that would not be a set. But we have this extra value. So [0,2,0] does makes sense because those extra values just represent, we didn't attack anywhere in those two positions. And so that would be okay. So there's some difference with this special extra value 0. We also have that we want just one solution representative of the model. So each of these [0,2,0], [0,0,2] and [2,0,0] represent this set 2. We don't want to allow that. And similarly each of these six different arrays represent the set 1 and 2. We don't want to represent that. So we're going to add constraints to fix those issues. So here's our array representation [1..size] of var SPOTx: of attacks;. So how can we add some constraints to make sure that we only get exactly one representation of these subsets of size of spots?. So we could just order the values. We're going to order them decreasing order to put our null elements at the end of the array. So that basically most of our processing will be at the start of the array. So if we're trying to do this, we just said that the attacks values are decreasing in order. There's a problem. Because there's no representative left for the set 2. Because the representative we'd want would be two zero zero. Right, so the problem with this is these null values. We do want to have duplicates of these null values. So we do have to have two of these null in a row, and so we can't do that if we have strictly decreasing values. So what if we had non strict ordering, so we just said that the attacks of i is greater than or equal to the attacks of i+1. Well the problem with that is it would leave solutions with repeats so we could have [3,2,2]. That would be allowed under that constraint and that of course has two copies of the position 2, attacking spot 2 and wouldn't be a set. So we don't allow that. So how can we overcome this? We're going to do that by basically combining those two constraints together. So here we can see that this constraint actually combines the strict and the non-strict ordering for the two different cases we want to consider. So if attacks of i is not null, then this expression here will be true and then the the implicit which is here added by MiniZinc. We'll convert this to 1. So this constraint will read of attacks[i] is going to equal to 1 + attacks[1+1]. So if the attacks[i] is not the null element then this will be a strict decreasing order. So that'll force that there can be no repeats of any non null element. But if it's a null element, then this will evaluate to false and this will just say attacks[i] is going to make the attacks[i+1], and which means that for null elements, there will just be non-strict ordering and I can have any number of repeats. So this constraint by itself will do both of those things at once. It will force no repeats of real elements but allow me to repeat the null element. So with the constraints in place, you can see that I'll have this exactly where I want that every of the variable sets of 1, 2, 3 has exactly one representation in this array from 1 to 3 of the vars which range over 0 to 3 right, with the 0 representing this extra null element. So obviously the set 1,2,3 is represented by exactly 3,2,1. Each of these is decreasing. And similarly the set {1,2} is represented only by the array [2,1,0]. Each of those are strictly decreasing. And similarly [3,2,0] and [3,1,0]. More interestingly is for the singleton sets, so this is only represented by [1,0,0]. The first one is strictly decreasing but this one, because this element is null, is only non-strictly decreasing which allows the third element to also be null. And similarly for the last elements here, and finally the last, the empty set is represented by [0,0,0] of all null elements. So you can see that we've built array representation which allow us to represent all of the Bounded Cardinality sets. So now we can build our model using this bounded cardinality approach. So here our decisions, so we have an extended spot which is adding 0 into the spot set of representations. And we have our constraint forcing where this is a valid representation. So this is the clever constraint that forces the strictly decreasing for non-null elements and decreasing for null elements. Then at most one intersection constraint is just as it was before, just forcing that every symbol is only dissected once with any of the attacks. And now objective, just as it was before, summing up for all the attacks that damage. And we can run that model and we find that the attacks 9, 7, 5 and damage 19. Hang on, shouldn't we have got the attacks [10, 1, 0] with a damage of 20? That's why we did this, that we knew that the Cardinality 3 solution, wasn't actually the best and we wanted Bounded Cardinality so we could find the Cardinality 2 solution. What went wrong? Well let's look carefully at what was going on in this calculation of damage. So, we are summing up for all of the phase in this attack array the damage[p]. So, let's think about what happens when we have a null element in the attacks array. So, we look up the damage[0], so p is 0. And let's try to look up array of p of 0 in the damage array. There is no damage of 0. So that means basically, if I try to look up damage of 0, it won't be allowed. So this will, in fact, constrain that there cannot be a 0 in the attacks array. So basically, this definition of the total damage will force that there is no zeroes, no null elements in the attacks array. And so in fact, it's going to force that the cardinality of the set we choose is size. So one thing we have to be careful with is when we build this representation of bounded cardinality sets using these arrays. We have to be careful that we look at how the intersection, how the interaction of this null element is with the constraints that we use. So we should also go back, and look at how it interacts with the constraint that defines the intersection. Now if attacks[i) is 0 and we look at it doesn't appear in any of these groups of s well it won't because these are only sets of spot. And that's fine because we're trying to determine if these cardinalities of intersections is less than or equal to 1. So it will be no problem in the constraint here. But how do we fix the objective? Well, we really don't want to sum up all the damages of the attacks. We only want to sum up the ones which are not the null element. So we can do that by adding this condition. So where the p is greater than 0. So where it's not a null attack. Not this dummy attack, we add up its damage. If we do that, then we're going to get the correct answer. So, in summary there are multiple ways to represent sets. You can have a var set of objects. This is very good if the solver natively support set and it's good when object is not too big. The array object of var bool 0 1. This is good when object is not too big. And indeed, most var set of objects if you declare them in a model and send it to a server which doesn't have native support for sets. Well, we convert it into this in any case. If you're doing a fixed cardinality set using this array 1 to U of our OBJ can be very effective. Particularly, if this fixed cardinality is small compared to the size of the set OBJ that you're picking from. And you can use this array [1..u] of var of extended object. Again when the cardinal of u is small but it's compared to the size of the objects you're picking from. But you need to represent the null object, and as we've seen, you have to be very careful about how that null object interacts with the definitions of the constraints and the objective which you're talking about for this search. You have to be careful that that null object Is taken to account in your representation of the set and doesn't break what you're doing in the constraints and the objective. So the SetSelect problem that we've looked at is actually known as the weighted set packing problem. It's one of the most well studied problems in combinatorics and it's a jewel of set covering another well studied combinatorics problem. So in this set of lectures we've seen a lot about set representation and choosing a set and many combinatorics problems fall into that category.