0:02

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.

Â 0:49

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.

Â 2:07

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.

Â 3:03

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.

Â 4:33

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.

Â 6:55

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.

Â 8:03

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.

Â 8:45

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.

Â 9:26

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.

Â 9:51

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.

Â