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.