So welcome to Workshop 11,

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.

[LAUGH] In the last workshop, we were talking about [INAUDIBLE] but

then we didn't wear the [INAUDIBLE] t-shirt, but today you're wearing it.

>> That's right, so we won't talk about [INAUDIBLE] at all.

>> Right, but we are in the workshop of module three now.

And we are supposed to be talking about No Zha.

That's why I'm wearing the No Zha tee shirt.

But then our workshop is not about No Zha either.

It's actually about Hou Yi.

And then we don't have a tee shirt for Hou Yi.

Well, in any case, if you still remember,

Hou Yi had to practice his Arrow-shooting, his archery skill, okay?

And that 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 is 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.

No, 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 how he has to do is to really go around the shops,

locate 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 minimize on the amount of money he will have to spend, and

then he will have to get all the arrows that he wants from the shopping list.

>> Yep.

>> Okay.

>> All right, so we actually have a model for this, right?

>> Right, let's take a look at the model.

>> Okay, so our job is not to look at the models.

So here we have for each merchant, how many we have to buy and

how many we get for free.

This is the dollar, the price of each arrow they 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 used that arrow type

A positive number is we get that arrow [INAUDIBLE] for free as part of

the merchant deal and zero means we just buy the arrow without using any deals.

>> So this how, okay,

this array of how variables essentially for each type of arrow.

How you have to decide where he's buying from.

>> Exactly. >> Which merchant?

But then there are three possiblities to get the [INAUDIBLE] from a particular

merchant.

>> Yeah. >> What are the three possibilities?

>> Sorry, he can use it,

he can buy it from the merchant as part of their buy x get y free.

Right, he could get it free from the merchant or

he can just buy it without using the deal.

>> Right, so there are two kinds of buying right, he can buy it so

that he can 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 stands for the merchant, right?

>> Yeah, the merchant, yeah, exactly.

Which merchant we're doing the deal with.

And of course the zero, he could do the deal with any merchant, right.

>> Exactly. >> Because we do it,

so we don't really care.

>> It's not associated with a particular voucher.

>> Right, exactly. >> Right, okay.

>> And so it just means,

we know the price it doesn't really matter which merchant he uses.

All right, so we have these decisions,

they're principal decisions right for each arrow, how do we bide?

All right., because we need to get them all.

How do we obtain it really, because we don't buy some of them.

>> Yeah.

>> And we're going to have this auxiliary variables here for merchants.

So which merchants are used?

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. >> Okay.

>> So it has to be more than and

what they specify in the voucher, right? >> Exactly.

If we basically look for

this merchant, do we use their deal?

Well, if we sum up the number of hours we bought at that merchant as part of

the buy with negative v.

Then that has to be greater than the number of acquired for

that merchant's deal.

Then we've used that merchant's deal, right, okay.

>> So we are using a C style kind of pseudo-boolean,

we are counting the number of trues, right?

>> Yeah, exactly.

>> Okay. >> We're counting the number of times that

this occurs.

>> Right, okay.

>> Okay, and then of course, if we don't use the deal, right?

>> Mm-hm. >> Then we have,

none of these negative v's should appear for that merchant v.

>> Mm-hm. >> because we're not using the deal.

>> Okay. >> 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 we

need to buy.

There's no point buying 12 arrows to use daily, [INAUDIBLE] needs 10.

>> So this is actually tricky here.

I don't think it's specified in the specification but you know it's 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 [INAUDIBLE] instead of buying it for the voucher, right?

>> Yeah, 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. >> Right, so

I'll always be better by just buying ten.

So it's a dormant rule if you want.

The next one is very similar in looking to the one above, which it says okay,

if you got the deal, so this deal is being used and

we can buy up to that many errors for free.

So if [INAUDIBLE], we are getting those errors for free from the merchant.

And of course, [INAUDIBLE] zero or false, then we can't get any for free.

So that constraint makes that happened.

>> Right. >> Okay, and then the last thing.

>> One more constraint.

>> It's the important one really which is whenever we

buy if whenever we get an error for free.

>> Yes. >> It can cost more

than any of the errors we bought.

>> For that particular deal.

>> For that particular deal.

>> Yeah. >> All right, so what are we doing?

We're looking through each pair of arrows.

>> Mm-hm.

>> Okay, so this how [INAUDIBLE] is less than how [INAUDIBLE].

So that means that we, so if you think about this way,

the only case we care about is we do this one [INAUDIBLE] of each other.

>> Right.

>> If the [INAUDIBLE] bought them from the same merchant.

One of them was bought and one of them was free.

>> Right. >> Okay, and

once we add, if we have that information,

and then we say that how[a1] is less than how[a2] it means that we pay for a1.

>> Mm-hm.

>> But we got a2 for free.

>> Because when we pay for a1, we have a- >> Right, you have negative v.

>> Negative v, you're right.

>> Yeah, okay.

>> Okay.

>> So if that's the case, if we pay for a1 and

we got a2 free, [INAUDIBLE] the price of a2 is less than or equal the price of a1.

>> That make sesne.

>> Okay, and

then of course the objective is just The total price that we pay, right?

Which is if I sum up for all the arrows, and if this how[a] is less or equal to 0,

than I pay for it, right, either as part of a deal or just order it normally.

And the other ones, I bet I get for free.

>> Right.

>> Okay, so there's our model there.

We can run it on some small data.

>> We should get something like that, right?

>> Okay. >> Okay,

so that was the test example that's in the handout.

>> All right. >> All right, but our role today is to

say, okay, how do we map this if we don't, so

we can run this actually using MIP solver.

So let's use the coin OR CBC solver, and that will run as well.

You can see it takes a little bit longer, 1 second versus 61 milliseconds.

>> Right.

All right, let's get rid of those.

Okay, so the first thing we need to do is decide

how are we going to represent the decisions?

>> All right, but if we look the original model, it's almost linear.

>> Yes, it's not too far.

We're not going to make you work too hard.

>> Right, except that, as I was saying, we are making use of C style, so

the Boolean to count something.

>> Yeah. >> So

one possibility is to really turn that into serial one variables.

>> Exactly, so- >> And then, of course,

our last constraint is not really linear by itself.

We might have to do something to translate that by ourselves.

>> We're going to have to go through and linearize everything that’s there.

>> Right, okay.

>> Okay, so the very first thing is how do we make these decisions?

So if you think about this, right?

>> And now, this is not quite linear, right?

So this is linear, but then we've got this used(v) here, right?

But actually, if we look at the next example,

we can see this also becomes how(a)- v.

So this one is linear, right?

So we're summing up a whole lot of 0 1 variables, and

this is a linear thing because buy v is none, so use to v is a variable.

So this is a linear constraint, so we need to get this thing here, okay?

And in this sense actually it's easy, right?

>> We can use a 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, right?

So all we need to really do is change that to equals.

>> Okay.

>> So now if we think about the two cases.

If we use the voucher,

then some of the arrows we buy from that merchant has to be exactly buy v.

If we don't use a voucher, the sum of the arrows we buy from that merchant using for

vouchers has to be exactly 0, and that's a linear equation.

So that's not too bad, okay?

>> And that is according to the earlier discussion we had, right?

I mean, if we really have to buy more than what the voucher requires,

that should overflow to using 0 to buy the arrows.

>> Yes, exactly. >> Instead, right?

>> Okay. >> All right, so

for the next constraint, again, this is easy enough, right?

We just make that how[a,v], because that's exactly what that describes.

And then, it's already linear.

>> Yeah. >> Yeah, we're done.

Okay, the tricky one is here.

[LAUGH] >> Right.

>> Okay, so, wow, this is it.

What do we do here?

So really, all right, 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, yeah?

>> We could look at all possible pairs of arrows.

>> Yes, so we definitely want to 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 we know the prices of these arrows once we pick an arrow.

So this can go wrong if the price of a2 is greater than the price of a1.

Where we bought a1 and we got a2 for free.

In that case, we cannot use a2 as a gift, I mean, something-

>> Yeah, we can't get a2 as a gift.

So now we have to think about, okay, so

basically this is true for any merchant, right?

>> Right.

>> For any merchant, We can't,

So there is a way of linearizing our relationship on the arrows.

>> But that's kind of tricky.

>> It is a bit tricky and actually it's It's also about thinking about this thing,

where you're often better off building conjunction, right?

A small conjunction of lots of little things is better than one big thing,

which is disjunctive.

So here, this is completely conjunctive.

The other one was a bit more complicated, right?

>> Okay. >> Okay, we haven't finished yet though,

and in fact, one of the real challenges comes in here, right?

So okay, how of a is equal to 0?

>> Mm-hm.

>> So we can work that out by just summing up, right?

>> Right.

>> Some variables.

So if we just sum over v in,

well, -m to 0.

>> Mm-hm.

>> All right, and then we sum over all arrows.

Yep, so this is a linear sum.

>> Okay, you are checking whether it's greater than or equal to 1.

>> Yeah.

>> Is it?

>> So- >> No.

Okay, no.

>> Yeah, okay, we've gotta get the arrows in the right place.

>> Right. >> Okay, if I sum-

>> Sum.

>> That greater than or equal to 1 times the price.

Now, this is not linear, right?

>> Right.

>> Yep, so we need to think about this.

Well, actually, we know only one of them will be true.

>> Yeah.

>> So that's not true.

So we can just sum them up.

>> Equal to one?

No, okay.

>> No, no.

>> Yeah.

>> Yeah. >> That's-

>> That's a relief.

>> [LAUGH] Because it can only be 0 or 1,

the sums, right? >> Exactly, I mean, we know that the sum,

there's only one of them that's true. Okay, are we done?

And we run with this data.

So -3, it could be different, right?

>> Right.

>> In fact, that -3 is useless on buying a batch, but

I'm not using anything to buy it with.

>> Mm-hm.

>> And if we look at the answer we got for here, and sort of work out.

So there's four vouchers, so there's nine possibility, one, two, three, four.

That's a 0.

>> Mm-hm. >> [LAUGH] So we can convert this.

But I think, actually, what we find is that the solution is 0, 1, 4, 1, -1.

>> Okay. >> Which is correct.

All right, so if we actually have a look at the flat sink that we've generated.

Right, so this is generator remember, for G code.

>> Okay. >> So there's been basically minimal

translation and we should only see int linear qualities int linear less than or

equal tos, no other constraints.

>> All right. >> Okay?

If we run it for CBC, all right?

But that'll always be the case because that's what, I mean, this equal will do,

it'll make sure that it only has those kinds of constraints left.

>> Okay. >> Right?

But now, I could also look at that, okay?

If we run our original shopping for CVC, okay, it took 746 milliseconds that time.

Look at that new one, which we've hand-modified, 84 milliseconds, right?

>> Yeah. >> Right?

And we didn't have a look at some bigger examples.

All right, so there's shopping01, so it takes a little while to compile.

Let's see.

This is a much, much tougher example.

It's not actually going to but we go down to stop it.

No, that's right. >> Okay.

>> So in 14 seconds we got to 715,000, how does the original one go?

We've got no solutions so far.

[LAUGH] Right?

We're going to actually hit 14 seconds with no solutions, whatsoever.

>> Right.

>> Okay? So you can see that we've certainly

improved our model, right?

So knowing which solver you're writing a model for

can make a substantial difference.

Now, ideally, we don't want to take that into account.

>> So you were using the CP model but then asking-

>> The MIPso, right.

>> The MIPso to solve it, right?

>> Yeah. >> But

how about comparing your serial model using a MIP solver and

then your CP model using G code?

>> Okay. >> What would happen?

>> So if we run this model with a G code, remember,

I took I think 14 seconds we got to this 715,000.

>> Right. >> So we go back and run the CP model.

>> Yeah.

Okay. >> Okay,

so, we're finding lot's of solutions.

[LAUGH] >> Okay.

>> We'll just give it about 14 seconds and then stop it and see how it goes.

>> Okay, sure.

>> Yes, nothing like watching paint dry, as you wait 14 seconds, approximately.

Okay, there's a stop.

Okay, so you can see, it's printed out my last resolution, but

I suspect it's not very close.

>> Right. >> Not much better than this 9105036.

>> Mm-hm.

>> So this is an example actually where, once I've met a MIP out of it,

the member of the MIPso knows what the good solutions are.

The CPs over really doesn't know or does this.

He tries to find solution, and says, let's find a better one.

All right, so you can see- >> So

you're basically saying that if a problem is inherently linear then we might

as well try to come up with a good linear model, and then submit it to a MIP solver?

>> Yes. >> It will be a lot more efficient.

>> Well, it depends what the difficulty is.

>> Right. >> If the difficulty is in combinatorial

search then the CP serve typically better, but if the the difficulty is sort of,

there's lots of solutions and we're just trying to understand costs and

how they interact, than a MIP solver will be better.

>> All right.

>> So the last thing we want to do is actually think about what we did here,

right, with this 01 model which only generated linear constraints and

see if we can improve our CP model.

>> Right.

>> So if we go back to the original CP model and let's copy it again.

And let's call it shopping_improved.

>> Mm-hm.

>> And we should think.

I mean, actually this MIP model was fantastic, right?

>> Right.

>> We can do the same trick here, right, without changing anything else.

>> Yeah.

>> That was a much better idea.

>> Yeah.

>> And may be we should grab the way we thought about this, right?

>> Mm-hm.

>> This constraint two and think about how we can write that in our CP model.

So I'm thinking about running this.

>> Well, actually, one better way to write is

how[a1] is not equal to the -(how[a2]).

>> Yeah, but that's what we did up here, right?

And I think it turns out that it's better off basically because actually what's

going to happen inside the CP model, because we keep up here, right?

We basically built boolean variables implicitly for

each of these values which value it takes.

So we can reuse them down here.

>> Mm-hm. >> So

we can do basically the same trick, but how we'd express it in CP.

We'd say that, right, it's not the case that we bought a1 and

we got a2 for free from the same merchant, right?

So it's just a different way of writing the same constraint but

more in the MIP style.

I don't think there's anything we need to do here.

This is actually quite effective from a CP perspective, right?

>> Sure. >> Simple.

And so we can just try that.

So let's see.

>> What software are we using right now?

>> Yeah, so we're using G code, but let's try it on one of the smaller examples so

we can, I don't know, I'm still running data five.

I don't want to do that. >> Mm-hm.

>> I want to run it.

Okay, that's G code on the improved model, 77 milliseconds, you get there.

>> Okay. >> If we go back to the original,

which I'm going to have to reopen.