0:21

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.

1:30

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.

2:46

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.

3:03

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.

3:41

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.

4:37

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.

5:07

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?

5:45

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.

7:57

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.

8:26

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.

8:48

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.

9:30

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.

10:54

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.

11:59

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.

12:34

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.