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.

Â