工作坊习题课12解答 (英文原声中文字幕)

Loading...

From the course by The Chinese University of Hong Kong

离散优化算法篇 Solving Algorithms for Discrete Optimization

ratings

The Chinese University of Hong Kong

离散优化算法篇 Solving Algorithms for Discrete Optimization

ratings

优化是决策的一般形式，在我们的社会中很常见。它的应用包括从求解数独谜题到婚礼上的座次安排。同样的技术可以调度航班和机组成员，协调钢铁生产，组织铁矿从矿井到港口的运输。人力资源和材料管理上好的决策可以令企业提升上百万的盈利。同样的问题很多也在我们日常生活出现，成为决定每天送货路线，决定学校时间表，传输电力到家里等种种问题的一部分。除了它们的重要性，这些问题如果用传统的本科计算机科学方法难以求解。这门课程为已经完成离散优化高阶篇的同学设计。请看这门课程的宣传视频：http://www.cpr.cuhk.edu.hk/cutv/detail/988

From the lesson

局部搜索

这个模块带你进入局部搜索的神奇领域，它可以高效地探索一些大而复杂的搜索空间。你将会学到状态，移动和邻域的概念，还有它们在受约束的搜索空间中如何被应用在基本贪心搜索和最速梯度下降搜索中。你还将学习不同的方法来逃离或者避免局部最小值，包括重启，模拟退火，禁忌表和离散拉格朗日乘数法。最后，你将会看到大邻域搜索把在邻域中找到最优相邻点看作一个离散优化问题来解决，并因此使我们探索更远和更有效地搜索。

工作坊习题课12解答 (英文原声中文字幕)30:20

Meet the Instructors

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

Welcome to Workshop 12.

This is the fourth workshop in the course on solving algorithm.

So Jimmy, where we up to?

Well, this is the last module of the course.

In this last module,

all the stories were about Wukong.

Okay. But then, actually in this workshop.

We have both Wukong and Nerja as well.

And Nerja was the main character in module number three.

Now in any case, at the end,

Wukong has finally got the te fan from the Princess Irene Fan,

and then, he was going to fan off the flames in the flaming mountain.

But unfortunately, there is a village that is nearby.

Okay. If Wukong is using the fan to fan off the flames,

some of the flames might catch on to the village,

and then jeopardize the houses in the village.

So Wukong, of course,

his was busy into fanning off the flames,

so he's asking Nerja for help.

He's asking Nerja somehow to send messages to

the villagers to warn them of this possibility.

So that people knowing that Wukong was gone,

there is such danger,

they would stand by their house,

they could defend their house when fire comes in.

So, what happened is Nerja has got M,

or he's gotten a number of magic boots.

So he could send those magic boots to the villages.

Okay. But then the village would have more than M magic boots.

So, what he's planning is to send the M boots to M houses.

Inform the villagers there,

and then, ask these people to become a messenger.

Okay. So what they have to do is once they receive a message,

they will have to run off to the other houses.

Okay. Inform the other people, and then,

they will have to run off to one house after the other, and then at the end,

within the time limit,

they have to return to their own home because

they have to stop defending their house as well.

Yeah.

Okay.

And of course, the objective is really to finish all

these within the shortest time. So that's the problem.

Okay.

So let us have a look at the starting point for this model.

So we're giving you a starting point of his model.

So this time, we are not given the model.

No.

We have to build the model as well.

We're going as to build the model as well.

As we get deeper into the course,

we want the workshops to be a bit more challenging, a bit more interesting.

Yes.

So we've given you the starting point,

and actually we've given the main idea.

Okay.

So the main idea of this is that we are adding these dummy nodes,

and extra dummy node for each of the M messages,

which basically represents them coming back to their own house.

Okay.

Okay. And so if we do that,

then we've got basically enough nodes to represent

one big tool because we sort of think of

a messenger leaves their house, comes back to their house,

but we think of it as a new copy of the node,

and then we just put the next of

that to be the next messenger's house, and then they go around,

and then the next messenger's house, and they around,

and finally, the last house points back at the first messenger.

So there'll be a big loop.

Yeah. So basically there'll be a big loop,

and that's good because that allows us to

use some global constraints which are exactly designed for that.

Okay. So, let's take a look at the data,

and the data's decision variables that we have.

Yeah. Okay. So we're obviously going to pick what are the messengers?

Which houses are going to be used to stop the message, right?

So this is why it's interesting from

a routing perspective because we don't know our starting points,

often we do, And then,

the key things of course is from each house, where do I go next?

And including these dummy houses,

like the dummy houses will be pointing,

at the next, the messenger's house.

What are given for each of the houses?

So the only thing we have for each house is its x and y coordinates.

Okay. Just to a location.

Yeah. Exactly.

And the time limit.

And the total time limits.

Yeah.

So that's the maximum time we can spend.

And obviously we're trying to minimize by the time everyone gets back to their own house.

I see that we also have a set of

decision variables that you have not mentioned yet as a messenger.

Oh yeah. I talked about those,

that's choosing the messengers.

Which houses are going to be the messenger.

So, where Nerja is you going to send the M boots, right?

Exactly.

Okay.

Because they're the people who are going to run out

and be messengers for the rest of the village.

Okay.

All right. So, if we think about this model,

we're going to have to keep track of a few things.

First of all, we've basically made it.

So the circuit constraint, right?

We're going to make a big,

the next is going to be one big loop.

So we've basically, set it up so we can use this global circuit constraint.

So we know that is going to happen. Yap.

We never talk about the circuit constraint in the course but then,

it's meaning is that you would take an array of variables as the argument.

Yeah.

And then you will make sure that this array of

variables it will form a loop like a circuit.

Yeah.

Right.

All right. So the circuit global constraint will do most of the workforce,

but now we have to make sure that we work out what's going on in the circuits.

So remember we had this special relationship.

So we knew that,

these dummy houses always pointed the next messenger's house.

Right.

Okay. So, we can do that.

That's fairly easy, so this is- we're going to take all of the messengers, right?

All right. And we're going to say that next,

now remember the dummy houses n plus i.

Yeah.

Right. That's i's dummy house.

So it's next will always be the next messenger.

But actually since we have to do this.

And the last one of course has to point back to the first.

So we have to break it into two.

Right.

All right. So the next of the n plus i is going to be messenger of i plus one.

Yep. Because we know that no one points at the messenger's houses

because no one- enters the messenger house they leave.

So we need that one but we also need the end case which is that,

the next of the last one m plus n is the first messenger.

All right.

All right. So we've set up that.

So now, we've got our grand tour.

All right.

So now, we have to work out how long it takes, right?

Actually that's the main problem,.

Right. Must be within the time limit.

Exactly. So we can do this first.

But let's think about the main idea, right?

Is if I look at all of the house nodes- so remember when I look at the dummy houses,

that next point that isn't really talking about moving.

That's just part of building up the circuit.

So certainly the nodes in the house,

I'm sorry i in house,

we can sort of work out the distance that the messenger has traveled to this house,

to the next of that house.

The distance we're using Manhattan distance, right?

Yeah. So is the distance to i,

All right so we're going to have to keep track of the distance to each house.

Yeah.

To each node in fact. All right.

Right.

Node.

And we know that well,

this time that is not the distance.

Let's call it time. Actually, it's a good idea.

So the time the messenger arrives at that house is this time,

the time of the previous house plus some distance.

Now let's build an array to look up that distance from i to next [i].

The tricky part is going to be doing that array

because sometimes this next will be a dummy house.

Then we don't actually know where it is.

So we're going to use all the powers of a modeling language to be able to build that up.

All right. So we're going to build this array, all right.

For each, actually we only care about houses.

So you'll notice when you look up this distance when i is a house,

from i to node.

And I'm pushing it can't have to be a variable.

Oh, something we have to solve.

Oh, so it limit.

Yeah.

All right. So let's call this distance.

Actually, well you can do it.

Maybe it's doing as if, no let's do it this way.

Let's do it as a function first.

We never talk about functions.

Did we?

No.

Okay, listen. Let's not do it as a function.

Okay.

But, in the end,

it's going to be very similar, right?

Right.

Because we're going to have to work out.

Basically, we're going to have to write a complex expression here,

which is going to give me

the distance from each house to each possible other house, all right?

So that's this function here.

Okay. So, basically, I'm going to have to work out.

So, normally, if it's two nodes,

if it's a house, I know that the normal thing is this Manhattan distance,

which is absolute value of [from]- [to],

the absolute value of-

Y [from].

Y [from] , thank you. Y [from] minus y [to] , all right?

Right.

So that would be perfect if from and to only were houses.

So from is always in house, right?

Yeah.

But to could be a node,

could include the dummy houses.

To is a node. So we're going to have to think about what to do.

So, this is the case, right.

If to is in house,

then that case, right? That's the normal case.

Otherwise, we have to think about what do we do.

And you can see that when we go to the dummy house,

the dummy house has to be the house of the messenger, right?

Right. One of the messengers.

Well, the messenger who's on this trip.

So it can't be any messenger,

it has to be the messenger of this trip.

So this is the point where we realize we probably need to keep track of something else.

We need to keep track of who delivers the message to each house, right?

So let's add another variable.

Who's going to deliver that message to this house?

Because without that, we won't be able to work out where we go back to. All right.

So, now we have to, let's build up that who constraint.

So we know the easy thing for the who's is we

know each messenger just visits their own house, right?

So for each i in messenger, who [messenger [i]].

Okay. Actually, we're going to keep track of the number,

which messenger visits the house, right?

So we're not saying the name of the messenger.

We're saying is it the first messenger or

the second messenger or the third messenger, okay.

So we know for the messenger houses, it's themselves.

And otherwise, we know that if we visit

a house then the same person visits the next to that house.

So who [next [i]] is equal to who [i].

And we have to be a bit careful.

This is only not true for the dummy houses but we're not doing it for the dummy houses.

So now we're keeping track of who visits each house.

Now we've got enough information to come back here and work out the distance

because we know where if we're going to a dummy house,

we know who visited it.

It's actually the person who's visiting this first house from because we're going to to.

So we just have to look at the distance from from, this is to.

Where is the house of the messenger?

Who.

So it's messenger, we have to get

the house number out of who visits from.

All right. Think about it for a while.

Okay.

So we look at who visits this node.

We're talking about moving from this node to a dummy node, right?

So we know that who visits this node is this messenger.

This is messenger number and their house number is this one and so this is the distance.

That's the x distance and then the y distance.

This is the same but

there's a bit of effort in that, right?

Right.

Okay. And that's it.

So we iterate overall from is in houses and to in nodes.

We have to convert it back to to distance, right?

But now, we have the distance so now we can use our distance here.

Okay. Is there anything else we need?

So we now have the time at each house.

Of course, we need to make sure that this in time is bigger than every time.

So constraint time of

i is less or equal to endtime.

Okay. Well, let's see if that works.

Oh, we could. If we run,

oops, we've got some typos.

File to close, break it there.

Okay. I probably left off a semicolon.

Yup, there, let's see if we can get through. All right.

Let's pick "village0".

No, we haven't put a solver item.

Okay.

We want to minimize. So, I'm trying to solve.

Minimize the entire, right?

Do we have equal strength to limit, the time limit?

So we've just used the limit we've just used in the demand.

All right. Sure.

So that's going to make sure that we've satisfied.

So off you can go. You can see it's generated some solution.

Actually, that's as good a solution,

the 16, as we found.

Okay.

All right. So the default-

The default is such a small problem, you know.

Yeah, a tiny problem still sitting there, okay?

Right.

We're 10 seconds in. In fact,

it will sit there forever.

It's never going to actually find approve

optimality because if you think about it

there's lots and lots of routes through the village.

Yeah.

All right. So we want to do better than that. All right. Well, I guess we should.

What did we learn in this course?

What did we learn in this course?

We learned that search makes a difference.

The village free, which is the smallest but we can actually prove optimality.

Right. With only two messengers.

Yeah. There's only two messengers.

There's only eight houses so it's a much smaller problem.

Should we try different search heuristics first?

Exactly. All right.

What do you think one of

the key variables that we should be trying to search on do you think?

Well, how about next?

Next seems like a pretty good one. All right.

That's a major decision like where do we go next.

So, if we just search on next,

now what kind of- so like a smallest doesn't make much sense, right?

Because it's not going to make sense, we could try,

we just "input_order" but this is

unlikely and we could just go are "indomain_random" let's say,

because we got no idea about where but I suspect we'll

find that one that will be worse than the default search, right?

I mean we finished this in 856 milliseconds and we try it without complete search.

All right. It was slightly faster.

It's slightly fast so all right.

So just telling the solver that we should search on next is better.

How about we try first_fail?

Right. That's often a good idea because it picks the ones with the least possible,

it didn't really work that well for this one out.

No.

Let's try "dom_w_degree", which is sort of the most powerful people to search for G-code.

Wow.

Even slower.

No, no, no, no. One second.

One second, 191 millisecond.

Oh, one second. I did see it.

That's okay. All right.

So, for this particular example, let's try.

That was the simplest example.

Let's try a bigger example because, of course,

so let's say after two seconds or so,

we got to level twenty-eight. All right.

Command E, command E.

Well, stuff will do.

And I'll compare that with "input_order"

and just see how well I can go after about two seconds.

Right? It looks the same.

We get to about 28. So they're finding the same solution.

It was 26 I think.

Oh, it was 26.

Oh, it was 26.

Okay. Oh, I guess you're right.

So we are seeing some benefit and you'll

definitely see that kind of behavior here that will just stop after a while.

Right. Okay.

All right. So that's a reasonable search strategy.

Okay. But we know we've got some tricks on our sleeve.

Yes.

What can we do to improve?

We can do restart.

We can do restart so let's go in and add some restart.

And because we are lazy, we're just luby.

Because it's fairly robust, it's hard to beat.

Yeah.

You can play around with other things and actually there is

a case often in these kind of routing problems,

we don't use luby restarts.

We'd use a constant restart factor actually.

Oh, okay.

Then you have to tune in to get to the size of the problem.

The good thing about luby is it doesn't matter.

So let's see if we can do better.

Okay, so we can immediately do better.

Wow.

Right? We're up to 22 almost immediately.

And then nowhere, no way further.

Right.

Okay, for that particular problem by adding restarts.

All right.

Can we do better yet?

We have some other tricks up our sleeve, Jim.

Right. From this model here, right?

Exactly.

The large neighborhood search.

All right. So let's add a large neighborhood search as well.

Yes.

And it's "relax_and_reconstruct".

You are demonstrating to students that, you know,

we are able to combine search annotations.

Yes. Almost anywhere I'm using which you can put annotations,

you can actually put two or more annotations, right?

So it's basically just can add on to each other.

So, basically, it the next vairiable that seemed to be the most important.

Let's keep 80 percent of them, right?

So, basically, if you think about this problem,

we're trying to find routes,

which are short, right?

So then we go from one house to another, which is close by.

And actually it doesn't really matter if the whole route changes.

That's still likely to be useful information,

all right, for change where if I go into that route.

Still if I got routes where I'm moving the houses which are close by,

I'm still likely to get a good solution.

Okay.

So sort of keeping the next information is

likely valuable even if we sort of change the whole set of messages, right?

Right.

We still want these routes,

which move around houses which are close to each other.

All right so let's see if we can improve.

Oh, okay. I need to define science.

Right.

Just "relax_and_reconstruct" so I can just steal from here I think. All right.

So, hopefully, by the time you're running this,

that will be in the standard library and you don't have this problem.

All right. So you can see now,

we got stuck before 22.

Now, we've managed to get down to 16.

So this large neighborhood search,

which is concentrating around solutions which were good

is enabling us to get a little bit further and actually that might be the operable solution.

Exactly.

We will never know really.

Exactly. Anyway, this cannot prove optimality.

No, exactly. Once we go to LNS,

we're not going to prove optimality but then,

for these problems, even though they're small,

it's quite tricky to prove optimality.

You can, for some of the small ones if you use a learning solver like chuffed but then,

you're then limited otherwise and so you don't have that built-in LNS.

All right. Okay. But we could try other LNSs, right?

So another possibility so there's another set of variables,

which are interesting, right, which are the messengers.

All right.

Yeah. Can we improve by keeping

track of some of the messages that I have misspelled the messenger?

All right.

And so you can see really, now okay.

It's improving.

It's got the 18 but didn't get down to 16.

But, previously, it got down to 16 very quickly.

Exactly.

Yeah. So it turns out that keeping

the messenger actually doesn't really help for this problem. It seems.

Yeah.

It's got to 16 eventually, right?

It is the overhead.

Yeah, it entered overhead and it really didn't help us.

So keeping some messages and saying, "Oh,

those are important," didn't seem to help so yeah,

we could try smaller device, right?

We can relax and reconstruct on a smaller set.

And just sort of seeing it's not so good, right?

It's probably, it get stuck here.

We used to get down to 16 for this particular example.

Of course, we're generalizing one example,

which is a very dangerous thing to do but we didn't have time.

How about?

Okay. The other way, we got 70 percent, make a bigger domain.

A larger neighborhood.

And so about four seconds, it doesn't seem to be that good.

It seems like that 80 was pretty good guess.

Yes.

Maybe because I've played around with this a bit.

But just some tuning that we have to do.

Exactly.

Yeah.

Yes. So, can we do better?

All right.

Can we do a better search where you can think?

So here we are only talking about the next, right?

Right.

We could try also because the messages are the other part of the problem.

Right.

All right. So we could try also think about searching rather than default search.

But searching on the messengers as well.

It seems interesting that we're doing input order.

We're doing input order, man.

Yeah.

I don't have any, wasn't doing it.

Well, we know this combined with restart.

So input order, you see we're definitely got rid of some of

the weakness of input order by using restart because,

of course the search changes the ones which are fixed.

They just get fixed,

it jump to the other ones and then doing them in order didn't seem to matter.

So, is there anything we can do about messengers?

Well, we can, how do we pick which messenger?

So, actually, you almost have no constraints on the messenger, right?

Actually, it's interesting, we probably should add some constraints on

the messages because we want them to be different.

Right? So you know that in any optimal solution,

they will be different because there's no advantage to

having the same message doing twice.

Right.

We can-

So this is the redundant constraint that you're-

It's redundant because this circuit will actually force it anyway.

Right.

But just making it clear up front probably help us.

Yeah.

The other thing we could do is say,

"Well, we can order the messages in order."

So you can see that they're just coming 5,14,1

when we could have had it instead of 1,14, and 5, right?

Yeah, sure.

So we could do that, in fact which will make the all different unnecessary.

So there's a symmetry breaking.

Yes exactly. For i in 1 dot dot minus 1.

We could force the messages to be in order less than, different anyway.

And once we do that redundantly,

we need that all different and that's include an input.

All right. No, I still somehow finish the search here.

So now, with the messengers in order,

then it sort of make sense that we go in domain min.

Right.

Because we're trying to hit that order. We go through.

So we're going to try and agree make our search to agree with the- Let's see how we go.

No, except that I put input domain instead of input order.

All right.

So that seemed pretty quick to get to 16.

So a bit of symmetry breaking was helping.

Okay. So there's another thing we can do in symmetry breaking if you think about

this is if we have a circuit, which goes from here to here.

Then if I had a different messenger on the same circuit,

it'd take exactly the same time, right?

So there's a symmetry break there which says that,

"I might as well pick the least numbered house in the circuit to be the messenger."

Right? Because that's another symmetry.

So in order to do that,

I just have to say, "Well,

whoever visits this house,

right, whoever visits this house has to be less than equal to this house."

Okay. So you see why because let's I had a 2 with like 5 and 2 and 7 and 9,

then I could have picked 2 as the messenger.

And then if you think 2 always less then to the who.

So this is not i,

it's the messenger [i].

All right, remember the i,

who [i] just records which messenger is in the first, the second, or third.

So we want that who [i] is and we want messenger of who [i].

That's what I want.

Yeah, I was seeing some type mismatch over there.

Yeah, exactly. Yes, wrong types.

So if we're using enumerated types here, would fix this,

we don't have any names for anonymous enumerated types would have discovered that for us.

But basically, we want to say that,

"Okay, the messenger who visits this house has to be less than the house number.".

Right.

Because if we had this circuit,

we could always pick the smallest ones.

I can see that after one minute it's two second 16,

so 16 is hard to improve.

Let's see if that helps us.

It seems to be slower.

Right. And this is a thing you're got to be working,

you got to be careful about with

a large neighborhood search or any kind of search like this.

When we add these constraints which reduced the symmetries, right?

We think, "Well, that's going to help us because

it's going to make the search smaller." Right?

Oh!

But remember, in large neighborhood search,

we're not going to visit the whole search, right?

And what these do is actually they remove solutions.

And the limits, the exploration of the search.

Yes. So they basically,

I might be very close to a solution with this redundant constraint removed.

And now, I've put that solution very,

very far away from where I am now.

Right.

So actually it's one of the tricky things when you're modeling for

large neighborhood search that adding redundant constraints maybe not beneficial.

Right.

Eventually, we got to the 16 but you could see it took us a lot longer.

No, I think you want to say adding symmetry,

breaking constrained might not help.

Yes.

The redundant constraint wouldn't matter.

No, no, no. Okay. You're right.

Right, yeah.

This is right. This is a symmetry breaking constraint.

It actually removes solutions but leaves symmetric ones back.

Right, okay.

It's not a purely redundant constraint. That's right.

But also, the same can, well not.

Anything that removes this notion of

redundant constraint shouldn't change the set of solutions.

Exactly.

But symmetry breaking or dominance breaking constraints actually removes.

Limit the exploration.

Exactly. And so that may be disadvantageous and reducing large neighborhood search.

So there's a few examples about how to play with these kind of things.

I invite you to explore a bit more what's

possible in this workshop and to get the best possible solution.

Right. I mean I suppose if learners wouldn't want to use large neighborhood search,

they could actually try to design

a local search algorithm to solve this problem specifically.

Yes, they could.

Right.

And in fact, I mean, this is the kind of problem which is often solved by

this vehicle routing problems are often solved by

us by bespoke large neighborhood search methods.

Yeah. So it's a challenge to see whether they could design

the algorithm that can beat LNS.

Oh you should, but the problem is simple.

You should be able to beat a high-level model.

Right, okay.

All right. That brings the end of the workshop.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play