Liu Bei recommended the strategy obtained from the tablet to the leader, Yuan Shao. But Cao Cao warned that there are only three elite groups within the army to attack the walls. And so a new strategy of attacking three walls was needed. Once again, Liu Bei turned to the magical tablet to find a suitable strategy. [SOUND] >> So the problem with the last model for attacking the bi-wall was was Liu Bei didn't have enough soldiers. So we've got to revise the question we're actually going to answer. So we've got a set of spots, and h is associated with the set of symbols. And we have to select a set of spots of a given size, so now we have three squads to attack. And we want to maximize the damage points we can do for this chosen set of a particular size. So now we're adding something to our data file. We're adding the size of the set that we want to choose. So we could easily add just one extra thing to our model to do this, right? All we have to do is say, well, we have this attack set that we're choosing, we're just going to force the cardinality of this set is equal to size. And then that's going to force what we choose exactly three attack positions, and we execute our model, we're going to get a new solution. The damage is less than before, but that's okay, we've solved the problem. But once we've got this new constraint, the size of the set we're choosing is known, we can actually model the set differently. And let's think about why we might want to do that, so rather than having a variable set of spots attack with this cardinality saying, the cardinality equals size, we can instead model it this way. We're going to have an array of one to size elements of var SPOT. We are going to say that the attacks are just the elements that occur in this array. So why should we do this? Well, imagine that the number of spots is 1,000, and we need to pick 4. So in the first representation, we've basically got a set variable with 1,000 possibilities in it, which in many solvers, will map down to 1,000 Boolean variables. So we basically have to make 1,000 true, false decisions. Is this value, this spot in or not, 1,000 choices have to be made. In the second representation, in this array representation, we have four integer variables, which are the four spots that we're actually going to take. But there will be some issues that come with that. So let's think about a smaller example. So here we have an array from 1 to 3 of variables from 1 to 10 that we want to represent. For example, the choice of a subset of the values 1 to 10 of size 3. Well, how many values are there of this array? Well, there's 1,000 possible values of that array. But here we have the actual thing that we're trying to do, which is we're trying to pick a subset of the value of the numbers 1 to 10, which is of cardinality 3. And if we think about how many possible values there on that, well, there's, in fact, 120 possible values. There are 120 different subsets of the numbers 1 to 10 of size 3. So obviously, there are lots more arrays than there are subsets of size 3. So the problem is that some of these array solutions don't represent subsets of cardinality 3. So if you think about if we chose that the values of the variables in the x array were 1,1,1, it wouldn't represent a set of cardinality 3. It would represent the set 1, which is not a set of cardinality 3. If we chose the values 1,2,1 in our array, it would represent the set 1,2, which would not be a set of cardinality 3. So that's one of the reasons that there are thousands more values here in the array than there are in the sets. So the first thing we need to do is ensure that all the values in this array are different, otherwise it won't represent a set of cardinality 3. So we can add some constraints on our array saying that all the values in the array elements are different, okay? So that we can do that straightforwardly, and that will get rid of that. So if we now think about our array with these extra constraints that all the values are different, we see how many possible values are. Well, there's 10 x 9 x 8 = 720. We still have more values left over with the array than there are sets of cardinality 3. So what's going on? Well, there's still some multiple representations of the same set. We think about the set {1,6,10} then there, all these array values correspond to the same set {1,6,10} obviously in the same order but also {10,1,6}, {10,6,1}, {1,10,6}, {6,10,1}, and {6,1,10}. Every order of the values in the array ends up representing the same set. And so what we have to do to get rid of this is make sure that we only allow one of these orders to appear in the array values to make sure there's only exactly one representation of the set. And the way to do this is to ensure that the values in the array are ordered. So here we can just make sure that the values in the array are increasing, in which case, there'll be exactly one way to write down this set. In this case, {1,6,10} will be the only way left over. And if we do that, we can see that this constraints here forcing them to be ordered will in fact, also force that they're not equal, and so we can get rid of these constraints here. They won't be needed anymore once we force them to be ordered, that would certainly be not equal. So once we do that, we'll have got down to exactly the same number of possibilities. So this brings up a critical issue in modeling decisions. So when we're modeling decisions in our problem, they are not necessarily the decisions we have to make in our model. Because decisions we make in a model have to be representable in the modeling language that we're using. So if it's possible, we make them identical. But sometimes we're making decisions in our problem which are complicated like a path in a graph or a tree structure, things that just can't be expressed directly in the modeling language we're using. So a critical modeling issue is making decisions in our model, which satisfy constraints and ensuring that they are valid decisions in the problem. So we add constraints to our model to make sure that the only answers that come out of the model are valid decisions to the problem. So we add these constraints in, just have we seen here, if we add constraints, forcing our array once we're not equal. To make sure that the array decisions in our model end up being valid decisions for our problem. And another issue that comes up is that multiple decisions in the model can reflect the same decision in the problem. So an example here is where we had x could be [1,2,7] or [7,2,1], they both represented the set x [1,2,7]. So another critical issue from modeling is to try to have only one set of decisions in the model corresponding to each solution in the problem. So reflecting the valid decisions in the problem having only one possible way of having that set of decisions in the model. And we add constraints to remove all but one set. So adding constraints in this case to force the array elements to be in order did this. So this in general is a notion of symmetry, and we'll come back and talk about that in much more detail. So these are two critical modeling issues we're seeing here for the first time, but we'll come back to them many times throughout this course. So let's come back to our problem, we have our problem of solving the bi-wall with a fixed cardinality set. Now let's use our new alternate way of building the model. So our decisions now is an array from 1 to size of var SPOT. So here is an array representation of the set of spots that we're going to attack. And we're going to force it is a valid representation by forcing that these attack positions increase in order so that we know that we exactly get one copy of each spot. We don't have duplicates, and they're in order, so there's only one representation of every possible set. And then we have to write our constraints using this new representation. For these particular constraints, it's straightforward, we're going to sum up. We have to make sure the cardinality constraint holds, that we only attack every symbol at most once. So this is easy enough. We sum up for all the attacks in the array, the intersection with the group, and that has to be less than or equal to 1 for each symbol s, so that's straightforward. And in fact, the total damage is even easier, basically because we can just add up the damage for these spot attacks of i for each of the i in 1 to size in the array, and that gives us the total damage. So that gives us our fixed cardinality version of the model. And we execute the model, and we've got our solution, just as we did with the other simplified version, where we just added a cardinality constraint. But for different kinds of datasets, with large sets of spots, we would expect that this cardinality model could be much, much more efficient. So in summary, we've got multiple ways of representing these fixed cardinality sets, so we can have our var set of OBJ with the cardinality constraints. And this is going to be good if the solver natively supports sets and when this object set is not too big, or we have arrays from 1 to u of var OBJ, which is very good when u is small. If we're picking a very small set of objects out of a large set, then this is typically going to be much more effective. And we brought up two critical issues in modeling decision, and that is we need to ensure that each solution to the model is a solution of the problem. So we make sure that we don't leave other solutions possible in the model, which don't refer to anything in the problem. And we try to ensure that each solution of the problem, only has one solution in the model and not many, many. Sometimes we won't be able to manage this, but if we can, it's a good thing to add constraints to our model to try to ensure that we do this.
