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.