So why do we use LNS? Because two reasons.

First, CP is really good for finding feasible

solution and for optimizing very small combinatorial space.

Okay?

So in a sense, you exploited two strengths of CP for finding a high quality solution

and you expl-, you exploit large, you know,

you exploit, you know local search for scalability.

Okay?

So in a sense, you exploited two facets

of these two techniques and put them together.

Of course, you can generalize that to MIP.

Okay? You can find

a feasible solution using MIP and you can exploit the neighborhood using MIP.

That works as well.

Okay?

Essentially any kind of method you can actually plug in instead of CP or

instead of MIP inside, inside of a

large neighborhood search is basically technology independent.

It's the basic idea of finding a feasible solution, defining the

neighborhood, finding a good neighbor in

that neighborhood, and repeating the process.

Okay?

So let me illustrate that with a very interesting example.

Okay? So this is from industrial engineering.

It's a problem with a robot.

Okay?

So a robot has to visit a set of

locations and do work at every one of these locations.

Okay?

It has a service time that it has to spend at every location.

That's the time that it takes to actually perform the task at that location.

It also has a time window for when

it can apply this service at that particular location.

And what we want to do is

also, there is also distance between the various locations.

So, time window, service time, distance on how you can travel between the

locations, and that distance is actually

asymmetric, which has complicated the problem tremendously.

And so what you want to do is find a path for

the robot to visit all the locations, that's called a Hamiltonian path.

Okay?

And we have to make sure that we

satisfy all the time window constraints, when we can

actually do the service at a various location.

And we also minimize the total travel distance.

These two constraints are actually have a lot of tension between them.

And that's what made the problem very difficult.

So this how you can moderate

using a, the scheduling, the girlfriend-based scheduling.

So I don't expect you to understand all the details

but let me just give you a high level overview here.

You model every activity that the robot

has to perform as an activity.

And it is about your service time, which is the duration that it takes.

We model the robot itself as a utility resource.

It's a vehicle here, okay?

And we have a transition time made for us here which basically tells

us how much time it takes to move from one location to another one.

And so the optimization is really minimizing the sum of the transition

times for all the location, subject to the time window constraints and

the fact that the robot can only be at one particular place in time, okay?

So the key aspect that I want to show you here

is that this is a very, very simple models, model okay?

So it doesn't require a lot of sophistication.

It's a very natural modeling of the problem.

Now, how do we apply large neighborhood search on this?

Well let's look at what the schedule look like.

So this is, is every one of these lines here, I know is basically the time window

of a particular a particular location that a task that we have to achieve and

the blue stuff is essentially when the robot

is there performing the particular, the particular service.

So.

This is one particular solution the only thing that you

don't see here is spacial the, the, the spacial information.

And so what I'm going to show you

is basically how large neighborhood search can works.

So look at this, what we going to do is to say, wow, I'm going to fix everything

outside this box.

So this part of the schedule and that part the schedule.

Assume that this is essentially the path of the robot.

And what I will do is basically say,

Ooh, I want to reoptimize that subsequence, find

the best subsequence, you know, from this particular

task to that particular task and reoptimize that.

Okay?

Then I get a better solution.

And then I move that window and do that

at another part of the schedule and keep repeating that.

That's what large neighborhood search is about.

Take a sub part of the problem and

reoptimize that, keep the rest completely fixed.

Okay?

So this is very structure based.

You are basically looking at which tasks are consecutive inside a schedule.

You can do something completely random.

Pick a random set of tasks and fix the rest

and reoptimize the, the task that you have reoptimized randomly.

That's also large neighborhood search.

Okay?

So you can imagine a variety of neighborhoods and you

can reoptimize every one and you can alternate between them.

That's what large neighborhood search is about.

Okay.

So, so let me give you the sense of

how beneficial this can be for for some particular problem.

So, so as I told you this is a,

a industrial engineering problem, a real problem with variables.

Now it was solved initially with a branch-and-cut algorithm, very

sophisticated algorithm by the Seuss team in, in Berlin, that's

one of the top group in mixed integer programming, and

the wrote 50 pages of algorithm and theorems and prove all

kinds of polyhedral case for solving this, and this is the best solution they found.

And for instance, you know, 48 there is not an optimal solution.

They can't prove optimality.

This problems are so hard that they couldn't prove optimality at that time.

Okay?

So what we did was applying the very simple model that

we have seen, and putting large neighborhood search on top it.

And we were looking at how good, you know, how

quickly we could find solutions that were beating these numbers.

And essentially

in five minutes of CPU time and this is like a decade ago right?

So we could essentially improve almost all the problems in five minutes and

find better, better solution using the

very simple, modern, and large neighborhood search.

And to actually improve the larger instances

we needed about you know ten minutes.

Okay?

And so this is the kind of value of

large neighborhood search, it's a technique that is extremely good.

For finding high quality solution

quickly and this is evidence of that, a simple case study of that, okay?

So, use it.

It's really nice for a lot of problems if you want

to scale, if you want to find high quality solution quickly, okay?

So, use it as I said.

This is a very interesting technique and you know, I'll see you next time.

Thank you very much.