So, welcome to Workshop 11,
and the third workshop in the course on Solving Algorithms.
So, what is happening, Jimmy?
Well, before we do that, let's talk about our t-shirts.
Well, in the last workshop,
we were talking about Shennong,
but then we didn't wear the Shennong t-shirt.
But today, you're wearing it.
That's right. So, we won't talk about Shendong at all.
Right. But we are in the workshop of module three now.
And we are supposed to be talking about Nerja,
that's why I'm wearing the Ne Zha t-shirt.
But then, our workshop is not about Ne Zha either,
it's actually about Hao Yi.
And then we don't have a t-shirt for Hao Yi.
Well, in any case, if you still remember,
Hao Yi had to practice his arrow shooting, his archery skill.
And then he needs to have a large number of arrows for him to practice
on so that he could break the big rock that's blocking water going into the village.
So, he has to go to the market to shop for arrows.
Now, this particular market they have has
very strict rules about the pricing of the arrows.
Essentially, all the shops,
they have to sell the same arrows at exactly the same price, no bargaining allowed.
Okay.
So actually, the merchants are not happy because there's no competition in the market.
Of course, shoppers are not happy either because shoppers always like to bargain.
In any case, somehow,
the merchants, they finally came up with a trick.
So, instead of having different prices for the arrows,
they would offer deals to the shoppers,
they offer vouchers to the shoppers.
The vouchers, they're always in the form buy x get y free.
So, if you buy x arrows of a certain type from that shop,
you would be able to get y of these arrows for free.
Not the same kind of arrows,
but the arrows that you're getting for free
must be cheaper than the arrows that you're buying.
So, that's the deal here.
So, what Hao Yi has to do is to really go around the shops,
look at all kinds of offers they are making,
and then he has to decide from which shop he's buying a particular type of arrows.
And of course, he would like to minimise on the amount of money he will
have to spend and then he will have to
get all the arrows that he want from his shopping list.
Yes.
Okay. Alright.
So, we actually have a model for this, alright.
Right. Let's take a look at the model.
Okay, so our job is not to look at the model.
So here, we have, for each merchant,
how many we have to buy and how many we get for free.
This is the data, the price of each arrow that he has to buy.
And the way the model works is,
it's going to work out, for each arrow type, what do we do with it?
So, a negative number is used to say that we use
that arrow type to buy part of a merchant's deal.
A positive number is we get that arrow type for free as part of the merchant deal,
and zero means we just buy the arrow without using any deals.
So, this is array of how variables,
essentially, for each type of arrow,
Hao Yi will have to decide where he's buying it from, right?
Exactly.
Which merchant.
Yes.
But then, there are three possibilities to,
as you say, get the arrows from a particular merchant.
Yes.
What are the three possibilities?
So, he can buy it from the merchant as part of the buy x get y free,
he could get it free from the merchant,
or he can just buy it without using the deal.
So, there are two kinds of buying, right?
Yeah.
I mean, he can buy it so that he could make use of a voucher, or he could just buy it.
And then, the how variable would get different values, right?
What kind of values do we have?
So, we have these negative values if he bought it to use the deal,
and positive values if he gets it free.
And 'i' stand for the merchant, right?
Yeah, the merchant, Yeah, exactly.
Which merchant we're doing the deal with.
Okay.
And of course, the zero,
he could do the deal with any merchant.
If he doesn't do it. So, we don't really care.
It's not associated with a particular voucher?
Right. And so, it just means
we know the price and it doesn't really matter which merchant he uses.
Alright. So we have these decisions, they're principal decisions.
For each arrow, how do we buy it?
Because we need to get them all.
How do we obtain it, really?
Because we don't buy some of them.
And we're going to have this auxiliary variables here from merchants,
so which merchants did we use their deal?
Okay.
Okay. So now, let's write down the constraints for this thing.
So, first thing is,
you can't use the deal unless you buy enough arrows.
Right.
So, it has to be more than what is specified in the voucher, right?
Exactly, so if we basically look for this merchant,
do we use their deal?
Well, if we sum up the number of arrows we bought at that merchant, as part of the buy,
with negative v, then that has to be
greater than the number required for that merchant's deal,
then we've used that merchant's deal.
So we are using a C-style pseudo-boolean.
We are counting the number of trues, right?
Yeah, exactly. We're counting the number of times that this occurs.
Right, okay.
Okay, and then of course,
if we don't use the deal,
then we have none of these negative v should
appear for that merchant v, because we're not using the deal.
So, if we're not using the deal, that should be zero.
If we use the deal, of course,
the most we should have is actually the number that we need to buy.
There's no point buying 12 arrows to use a deal which only needs 10 to start off.
So, this is actually tricky here.
I don't think you specify in the specification,
but you're basically saying that if we have to buy
more arrows from that particular merchant,
but then the deal does not require us to buy that many arrows,
then we might as well just buy it using zero,
instead of buying it for the voucher, right?
Yes. So the dominance rule says,
if I need to buy 10 arrows to use the deal,
there's no point in buying 12 because it's just more expensive.
Okay.
So, always be better by just buying 10.
So, that's the dominance rule, if you want.
Alright, the next one is very similar in looking to the one above,
which just says, okay, if we've got the deal,
so this merchant's deal is being used,
then we can buy-- we can get that up to that many arrows for free.
So, if how of a equals v means we're getting those arrows for free from that merchant.
And of course, if used to v is zero or false,
then we can't get any for free.
So that constraint makes that happen.
Right.
Okay, and then the last thing.
Yeah, one more constraint.
It's the important one, really,
which is that whenever we get an arrow for free,
it can't cost more than any of the arrows we bought.
For that particular deal?
For that particular deal,
alright? So, what are we doing?
We're looking through each pair of arrows.
Okay, so this how of a1 is less than how of a2.
So, if you think about it this way,
the only case we care about is really this one,
the negatives of each other.
If they're the negative of each other,
then we bought them from the same merchant.
One of them was bought and one of them was free.
And if we have that information,
and then we say that how of a1 is less than how of a2,
it means that we pay for a1,
but we got a2 for free.
Because when we pay for a1, we have a
value of negative v.
Negative v. You're right. Okay.
Okay. And so, if that's the case,
if we pay for a1,
and we got a2 free,
it better be that the price of a2 is less than or equal to the price of a1.
That makes sense.
Okay. And then of course,
the objective is just the total price that we pay, which is,
I sum up for all the arrows,
and if this how of a is less than or equal to zero,
then I pay for it either as part of a deal or just bought it normally,
and the other ones I get for free.
Right.
Okay. So there's our model there,
and we can run it on some small data.
Yeah.
We should get something like that, right?
Okay.
That was the example,
the test example that's in the handout.
Alright.
Alright. But our role today is to say,
how do we map this? If we don't--
We can run this actually using MIP solver.
So, let's use the CORN-OR CBC solver.
And that will run as well.
You see it takes a little bit longer.
Alright.
One second versus 61 milliseconds.
Right.
If we didn't have all of Minizinc's interface
to convert this into
linear constraints because that's all that's going to MIP solver,
how should we write this model?
Okay. Now, the task is not to rely on the Minizinc translation.
Exactly.
And we would like to come up with a MIP model directly, right?
Exactly.
Right.
The rules of the game are,
If we looked at.
Don't do that.
Yeah, don't do that. That's the name.
Let's call it slightly different so that we can have a new copy.
Alright.
Alright. So we're going to start off with the same model.
But now we have to make it into a version,
that if I did a compilation.
Let's see.
If I compile it,
then I should only see,
you can see that everything's been converted because we can combined it to bq.
Right.
Right?
You see that many new variables are introduced.
Exactly. So what we want,
we know that that's what compilation to COIN-OR will be,
but what if we are compiling it to G code, right?
The rules of the game are,
that if we compile it to G code,
well, I've to compile it again.
Then the result, should have only linear equations in it,
and 0,1 variables. You can see, it's not.
It's got linear re-ifs all kinds of other constraints in it. Alright.
So that's the game, the name of the game we're trying to do,
which is basically to build a direct MIP model for this problem.
Alright. Let's get rid of those.
Okay.
Okay. So, the first thing we need to do is,
decide how we're going to represent the decisions.
Right. But, if we look at the original model, it's almost linear.
Yes, it's not too far.
We are not too far, right?
I mean except that, as I was saying,
we are making use of C style pseudo Boolean to count something.
Yeah.
One possibility is to really turn that into 0,1 variables.
Exactly.
And then, of course, our last constraint is not really linear by itself.
We might have to do something to translate that.
We're going to have to go through and linearise everything.
Right.
Okay. So, the very first thing is how do we make these decisions.
So, if you think about this, right?
We've got this integer variables here.
Now, we could leave them as integers except that we
keep on doing this kind of check, right?
how [a] = -v or how [a] = v. So,
we are really treating these Booleans are the important thing,
zero-one decisions about where this arrow's gone.
The obvious way to map these decisions.
I think you should be MERCHANT.
You're right, it should be MERCHANT.
No, it's ASSIGN, not MERCHANT.
Right? It's how I use the ARROW. Good point.
Okay. Right.
Because I want for each arrow,
for each assignment, how is it done?
So, I'll just change that into zero.
Okay.
But the bools here, obviously,
since I don't have any Booleans,
I've just changed zero, one that's easy.
Yeah.
Now, we sort of need to look at each of these constraints and think
about how we can write them directly.
The first thing we can say is,
well, obviously, this thing here,
how [a] = v,
just exactly becomes this.
And now, this is not quite linear, right?
This is linear, but then we got this used [v] here.
Right? But actually, if we look at the next example,
we can see this also becomes how [a, -v].
This one is linear.
Right? We're summing up a whole lot of zero-one variables,
and this is a linear thing because buy of v is known, so used[v] is a variable.
This is a linear constraint.
We need to get this thing here.
And this thing is actually it's easy, right?
We can use similar trick as the second constraint, right?
Yes. Exactly. And actually,
even simpler because, really remember,
if we're going to use this voucher,
we have to buy basically exactly the right number.
All we need to really do is change that to equals.
Okay.
Now, if we think about the two cases.
If we use the voucher then,
the sum of the arrows we buy from that merchant has to
be exactly buy v. If we don't use a voucher,
sum of the arrows we buy from that merchant using no vouchers has to be exactly zero.
And that's a linear equation.
So, that's not too bad. Okay?
And that is according to the early discussion we had, right?
I mean, we really have to buy more than what the voucher requires,
that should overflow to using zero to buy the arrows.
Yes. Exactly.
Is that right?
Okay. Alright.
So, from next constraint again,
this is easy enough, right?
We just make that how [a, v] because that's exactly what that describes,
I mean, it's already linear.
Yeah. Read them.
Okay. The tricky one is here.
Well, this is it. What do we do here?
So really, for two arrows,
if we buy them from the same merchant,
we get one for free, and buy one from the same MERCHANT.
We have to know that their price has a certain relationship.
We can look at all possible pairs of arrows?
Yes, so we definitely want look at all possible pairs of arrows.
I think the best way to think about this is we're
going to add a whole lot of little constraints,
which remove the possibility of doing something wrong.
Right? So, if we just,
and since these have, we know the prices of these arrows, where to pick an arrow.
This can go wrong if the price of a2 is greater than the price of a1, right?
Where we got a1, we bought a1 and we go a2 for free.
In that case, we cannot use a2 as a gift.
We can't get a2 as a gift.
Now, we have to think about again.
Basically, this is the truth for any merchant.
For any merchant, we
can't buy a1 and get a2 for free.
Okay? It's not the case that we bought a1 from this MERCHANT,
and we got the other one for free.
We got the other one for free,
was with that we [a2, v] if they can't be true at the same time,
that basically means. Right?
Less than or equal to one.
Exactly. Yeah. We can have them both true.
If they're both true, this would add up to two.
Right.
We can't allow that, but we can have any one of them true.
Yeah. Or Both of them false.
Or both of them false is fine, yeah.
There's a way of linearising our relationship on the arrows.
But that's kind of tricky.
It is a bit tricky.
And actually, it's also about thinking
about this thing we're often better off building conjunction, right?
A small conjunction of lots of little things is better
than one big thing, which is disjunctive.
Here this is completely conjunctive.
The other one was a bit more complicated, right?
Okay.
We haven't finished yet here no.
And in fact, one of the real challenges comes in here.
How[a] less than or equal to zero?
We can work that out by just summing up some variables.
If we just sum(v in -m..0),