0:00

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 Wu kong.

Okay. But then, actually in this workshop.

We have both Wu kong and Ne Zha as well.

And Ne Zha was the main character in module number three.

Now in any case, at the end,

Wu kong has finally got the the 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 Wu kong is using the fan to fan off the flames,

some of the flames might catch on to the village,

and then jeopardise the houses in the village.

So Wu kong, of course,

his was busy into fanning off the flames,

so he's asking Ne Zha for help.

He's asking Ne Zha somehow to send messages to

the villagers to warn them of this possibility.

So that people knowing that Wu kong 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 NeZha 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 Ne Zha 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 work for us,

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.

5:25

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.

14:37

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 built in 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, stop 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, Jimmy.

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 "dom_w_degree", 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. forall(i in 1..n 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.

26:42

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.