Workshop 11

Loading...

En provenance du cours de The University of Melbourne

Solving Algorithms for Discrete Optimization

2 notes

The University of Melbourne

Solving Algorithms for Discrete Optimization

2 notes

Discrete Optimization aims to make good decisions when we have many possibilities to choose from. Its applications are ubiquitous throughout our society. Its applications range from solving Sudoku puzzles to arranging seating in a wedding banquet. The same technology can schedule planes and their crews, coordinate the production of steel, and organize the transportation of iron ore from the mines to the ports. Good decisions on the use of scarce or expensive resources such as staffing and material resources also allow corporations to improve their profit by millions of dollars. Similar problems also underpin much of our daily lives and are part of determining daily delivery routes for packages, making school timetables, and delivering power to our homes. Despite their fundamental importance, these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students who have completed Advanced Modelling for Discrete Optimization. In this course, you will extend your understanding of how to solve challenging discrete optimization problems by learning more about the solving technologies that are used to solve them, and how a high-level model (written in MiniZinc) is transformed into a form that is executable by these underlying solvers. By better understanding the actual solving technology, you will both improve your modeling capabilities, and be able to choose the most appropriate solving technology to use. Watch the course promotional video here: https://www.youtube.com/watch?v=-EiRsK-Rm08

À partir de la leçon

Mixed Integer Programming

This module starts by introducing linear programming and the Simplex algorithm for solving continuous linear optimization problems, before showing how the method can be incorporated into Branch and Bound search for solving Mixed Integer Programs. Learn Gomory Cuts and the Branch and Cut method to see how they can speed up solving.

Workshop 1126:35

Rencontrer les enseignants

Prof. Jimmy Ho Man Lee
Professor
Department of Computer Science and Engineering
Prof. Peter James Stuckey
Professor
Computing and Information Systems

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),

how[a]-- okay so that is a guess.

This is still not going to work.

But basically, that check how [a,v] is greater than or equal to one,

that says that we bought this arrow from some merchant.

Alright.

Yeah. So that's the thing that's true.

Actually, that will do.

Yeah.

And then we sum over all arrows.

This is a linear sum.

And this sum is guaranteed to be,

okay, you're checking whether it's greater or equal to one.

Yeah, is it?

No.

No. I'm going to get the arrows in the right place.

Right.

If I sum that greater than or equal to one times the price.

Now, this is not linear, right?

Right.

So we need to think about this.

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

That's not true. We can just sum.

Equal that one. No.

No, no.

Yeah.

That's a relief.

Because that can only be zero or one.

Exactly. We know that the sum,

there's only one of them is true.

Okay. Are we done?

Possibly, because we are missing a bracket somewhere,

like there are too many brackets there I'm guessing.

Yeah.

Alright.

So, we can try and run it.

It doesn't look good.

No.

So, one thing we've forgotten, right?

Is we have to,

once we move to the zero-one description,

we have to make ensure that we buy each arrow once.

Okay.

There's nothing telling us that we just set all of them to zero.

Right.

So we need to say "constraint forall(a in ARROW)."

There's only one way we buy it.

So, (v in ASSIGN).

That's the sum of how [a, v].

Right. So exactly one way of buying it.

Yeah.

Right? So that's better.

Now let's see if we get an answer that looks more sensible.

Alright. So, good, 130.

It seems to be the--

The right answer.

Yeah.

If we look at it carefully, okay,

we have to think about our data.

Open the original one, shopping.

And we run with this data.

So minus three, it could be different, right?

Right.

In fact, that minus three is useless.

I'm buying a voucher but not using anything to buy it with.

But if we look at the answer we got for here, it worked out.

So there's four vouchers,

so there's nine possibilities: one,

two, three, four, that's a zero.

So we can convert this.

But I think, actually, what we find is that the solution is zero,

one, four, one, minus one.

Okay.

Which is correct. Alright.

So, if we actually have a look at the FlatZinc that we've generated.

Alright, so this is generated remember for G code.

Okay.

So there's been basically minimal translation

and we should only see int linear equalities,

int linear less than or equal to's, and no other constraints.

Alright.

Okay? Of course, if we run it for CBC, alright,

that will always be the case because that's what MiniZinc will do,

it will make sure that it only has those kind of constraints left.

Okay.

Alright? But now we could also look at that.

Okay? If we run our original shopping for CBC,

it took 746 milliseconds that time

If we look at that the new one, which we've hand modified, 84 milliseconds.

Yeah.

Alright.

And we can have a look at some bigger examples. Alright.

So there's shopping_01, so it takes a little while to compile.

See, this is a much, much tougher example.

It's not actually going to prove optimality.

But we got down to-- Stop it. No, that's right.

Okay.

So in 14 seconds, we got 715,000.

How does the original one go?

Alright. I'll give it about 14 seconds.

We've got no solution so far. Alright.

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

The MIP solver.

MIP solver to solve it, right?

Yeah.

But how about comparing your 0,1 model using

a MIP solver and then your CP model using G code?

Okay.

What would happen?

So if we run this model with Gecode,

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

Right.

So if we go back and run the CP model.

Okay.

So, oh, we're finding lots of solutions.

Okay.

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

Okay. Sure.

Yes. Nothing like watching paint dry as we wait for 14 seconds, approximately.

Okay. There's the stop. Okay. So you can see.

A button.

Oh, it's going to print out my last solution but I suspect it's not very close.

Right.

Not much better than this nine,

one, zero, five, zero, three, six.

So this is an example, actually,

where one side made a MIP model out of it.

The member of the MIP solver knows where the good solutions are.

The CP solver really doesn't know.

All it does is tries to find a solution then says,

"Oh, let's find a better one." Alright.

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'll be a lot more efficient.

It depends where the difficulty is.

Alright.

If the difficulty is in the combinatorial search,

then the CP solver are typically better.

But if the difficulty is sort of there's lots of solutions and

we're just trying to understand costs and how they interact,

then a MIP solver will be better.

Alright.

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't 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.

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.

Yup.

That was a much better idea.

Yeah.

And maybe we should grab the way we thought about this, right?

This constraint too, and think about how we could write that in

our CP model and maybe we get a better result there too.

So how do we write this?

Basically, that this is just saying we could use linear but it's really just

saying how of two equals minus v. So,

it's not the case if both of these hold, right?

So I'm thinking about running it this way.

Well, actually, one better way to write is how

[a1] is not equal to the negative of how [a2].

Yeah but that's what we did up here. Right?

Okay.

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.

So we can do the same, basically the same,

trick but how we'd express it in CP.

We'd say that, 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 of all.

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 solver are we using right now?

So we're using G code,

but let's try it on one of the smaller examples so we can-- Oh no.

I'm still running data five.

I don't want to do that. I want to run it.

Okay. That's G code on the improved model, 77 milliseconds.

Okay.

If we go back to the original,

which we're going to have to reopen,

and I run it there. 57 milliseconds.

I'm not seeing any difference there.

I didn't get an improvement. We need a slightly harder one.

Alright.

There's shopping done in,

that was two seconds and now we're getting something where we can basically compare.

It's the same.

Basically, we're not finding any difference in this case.

Alright. But it is sometimes the case that we can actually get insights.

I mean, this seems just like a better way in the CP model as well.

Yeah.

Right? So we can get insights by thinking about how we'd model for

another underlying solver and that might be helpful in improving output altogether.

Alright. That brings us to the end of this workshop.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play