this could optimization local search, 
part two. 
more concept and the main concept today 
is going to be the concept of swaps. 
But there will be another set of really 
interesting concepts on the way you'll 
see that. 
So let me start again with the car 
sequencing example. 
You'll remember these beautiful cars, 
right? 
So basically what we have is an assembly 
line we have to produce these cars from 
this assembly line but these cars are 
requiring different types of options 
right so leather seats, moon roofs all 
these kind of things. 
So when you produce this car as we saw 
previously you have to basically sequence 
them on the assemnly line in such a way 
that the production unit Have the time to 
put the options on the cars. 
Okay? 
So how, how do you do that is really the 
question here. 
Okay, that's what we have to solve. 
We have to sequence these cars such that 
production unit will have the time to put 
the options on the car. 
Okay? 
So this is a configuration. 
This is a solution acitvity that we saw 
before. 
You know every one of the roads you see 
over here okay so that's the capacity 
constraints. 
That about the eruption lets say 
[UNKNOWN] and the capacity of that one is 
one out of two which basically means if 
you take two successive slots you can at 
most one one cause requiring 
interruptions otherwise the production 
won't have the time to actually put the 
options on the table on the On the, on 
the car. 
So so when we look at this thing from a, 
from a local search standpoint, what are 
we looking at? 
While we, what we'll do is we start with 
a sequence, right? 
We always seq start with, with 
configurations and that configuration may 
be completely violating these capacity 
constraints, okay? 
That's the way local search works. 
And what we're going to do here is, we're 
going to look at that configuration and 
we're going to look at 2, 2, 2 parts of 
the assembly line and we're going to swap 
them, okay so that's the basic idea here. 
Okay? 
So we're going to take two 
configurations, you know 2 types of 
[UNKNOWN] and we are going to swap that. 
Swap that. 
Okay? 
So, the first strategy therefore, is 
going to find a car configuration. 
Okay? 
Which appear in some violations, that 
means that some of the capacity 
constraints or maybe several will be, 
will be violated and what we will do is 
to swap that particular type of car with 
another car in the assembly line. 
Okay? 
And the goal of course, is going to be 
trying to minimize the violation. 
Okay? 
So, every one of these moves. 
Its goal will be mining, minimizing the 
overall violation of the capacity 
constraints. 
Okay? 
So let me illustrate that on an example, 
okay. 
So what you see here are all the, all of 
the assembly line that, the exact way we 
saw it for constraint programming. 
The, the diagram on the bottom, there, is 
essentially looking at all the options, 
and that's How we will be able to look at 
the violations. 
Now, the table that you see here, okay, 
is basically the various configurations 
that we have produced. 
I won't talk about it very much, because 
you'll see everything here. 
Here. 
So the beauty of local search is that at 
every point you see the everything 
because you've assigned you know 
essentially all the, all the, all the 
decision variables. 
Okay so what you see here is that we 
produce the various types of car you 
know, we had a demand for 1 for this one, 
1 for that one, 2 for the you know to 
that 3rd type of car and so on. 
And so essentially what you see there is 
basically a completely arbitrary 
configurations at the beginning, Okay? 
Now we look at the options of that car 
and that's the kind of options that they 
require, okay? 
So you see for instance that here, you 
know, we have three cars requirirng 
option one, okay and we know that the 
capavity is one out of two so they will 
be violations there. 
Okay, and you see all the other options 
being required by the various types of 
cards. 
Okay so now we have to find we have to 
understand the concept of iteration 
right. 
So these capacity constraints are huge 
stuff right so they look at the entire 
line. 
But there is a very, very nice way of 
actually capturing the violation. 
What you do, is that we know the capacity 
of this guy is one out of two. 
So what we are going to do what you see 
there, right. 
We are going to take this window, this 
sliding window of two slot of a time, 
okay. 
And then we are going to look if inside 
that window, there is a violation or not, 
okay. 
So in this part of the case, we see a 
nice, you know. 
Two slot window. 
Only one carries, requiring the option so 
we're know that we are fine. 
Okay? 
So for the next for the next option, just 
a little bit complicated. 
Here my hand is probably not big enough 
but we have a window of three slots. 
And we are looking if there are more than 
two cars actually requesting that option, 
OK? 
So we can do that for essentially all the 
various options there, really big at the 
end because they're windows of size five. 
So in a sense, what we can do is we can 
take these windows and move them along 
the slot, the assembly line essentially 
And so you see this nice you know, window 
which is moving and at every step, okay, 
what we are doing there is looking how 
many cars are requesting that option in 
that particular window, and if there are 
more than one is this particular case we 
will have a violation. 
So essentially the violations are 
going to come when you are in a 
particular window okay? 
We are, the window is in a particular 
part of the assembly line such that the 
capacity of the production unit is 
violated, okay? 
So in this particular case what you see 
here is that it's violated so we know 
that we have one violation. 
We move it a little bit. 
to the right and we see another violation 
and then the last slot of the, the last 
two slot of the assembly lines have also 
two cars there requesting that option so 
we know that we have another violation. 
So, in this particular case, we know that 
the first, the capacity constraints of 
the the first option is violated three 
times, okay? 
Now, we can do that in a very similar 
fashion for the second option, okay? 
So also, you know, show which cars are 
here. 
Which, which options are basically 
violating the capacity constraints. 
We could do it for the next one, and we 
see that in this particular case we have 
two, we left two violations. 
Okay? 
And that's what you see there. 
And we also see which essentially slots 
are violating that particular 
constraints. 
Okay? 
And we can do that for every one of the 
lines. 
And you see. 
You know in this particular example, how 
many of the, the, the capacity 
constraints and, and how much the 
capacity constraints are violated. 
Okay. 
So the, the, look and such, no It's 
basically going to take configurations 
here, okay, types of cars, which are 
appearing in some violation, and then 
swap them together. 
Okay, so we take one, we take another one 
we swap them together we observe the two 
costs and obviously we have to [UNKNOWN] 
all of the violation and which of the 
slots inside the assembly lines Are 
basically in valuations. 
Okay, so we did, we did one move. 
This is another move. 
We take the, we take care two and car 10 
and sub them together. 
And we reduce the valuations again, so 
there is at least at this point, there is 
only one tiny violation. 
And we could continue doing things like 
this, and in this particular case we keep 
one violation and we can continue. 
These are the various local moves that 
you can do, okay? 
So, the key point here, is that compared 
to the queens example, what we are really 
doing Is swapping cars. 
We are not assigning a value to a 
particular to a particular to a 
particular to a partiuclar slot. 
So why do we do that? 
Think about it. 
Why are we essentiallyy considering 
swaps, and not assignments of values to 
the decision variables? 
Okay can you think about it? 
So the reason we are doing that is that 
we are automatically by doing that 
maintaining the satisfaction of one type 
of constraints, the demand constraints. 
So we are making sure that at any point 
the demand constraints is always 
satisfied. 
We always produce The right amount of cap 
So that constraint, we can just forget 
about it. 
Okay? 
So because we at all the first, the 
first, you know the first configurations 
that we had at all the cars that we 
needed to produce, once we swap, we keep 
exactly the same number of constraints, 
and the demand constraints is going to be 
satisfied forever. 
Right? 
So this is the key aspect here. 
So, in a sense, you know if you tried to 
abstract this a little bit, what we have 
is two types of constraints. 
There are the hard constraints, they're 
the constraints that you want [INAUDIBLE] 
of search procedure to satisfy all the 
time, and then you have the soft 
constraints, which are very nice because 
you can violate them and try to violate 
them less and less. 
Okay? 
So the key idea here is that in many of 
these complex problems, what you do is 
you separate the two constraints into the 
hard constraints and the soft 
constraints. 
You maintain the hard constraints. 
They are always satisfied by the local 
search and then the soft constraints can 
be violated and used trying to decrease 
the number of violations of these soft 
constraints. 
That's the basic power line here, when 
you try to solve satisfaction problems, 
okay? 
So let me move to another problem that we 
saw. 
And discuss how we can actually solve it 
wit local search again. 
This is a magic square where we trying to 
have this a square and trying to pit all 
different numbers into the various square 
such that the sum of the diagonals, the 
sum of the horizontal line, the rows and 
the and the columns. 
Were equal to the same number. 
So this other constraint that you saw 
okay, and essentially they constrainting 
that all the, the rows and the column, 
have to sum to t, and then you have the 
sum of diagonals, and once again you have 
to sum to t, and then you have the all 
different constraints, which is basically 
specifying that every one of the squares 
in the big square have to have received a 
different number. 
Okay? 
So, once again, we're going to do exactly 
the same thing. 
We're going to split these constraints 
into two sects. 
A hard constraint and then a bunch of 
soft constraints. 
So, the hard constraints here is going to 
be the all different constraints. 
Now, I'm going to make sure that we only 
assign different numbers to every one of 
the squares. 
Okay, the slot in the squares, in the 
square. 
And the other constraints, essentially 
here the inequalities, the equalities for 
the rows, the column, and the diagonals, 
are going to be soft constraints. 
We can violate them, and we'll move 
towards decreasing these violations. 
Okay. 
So, you know this is a particular 
configuration that we have. 
Look all the numbers here are different. 
Okay? 
And what we are trying to do is making 
sure that the you know, the rows, the 
rows, the columns and the diagonals sum 
to the same value. 
Okay? 
Now, the real magic number that we want 
to find here is 15. 
Okay? 
But we see that this particular column 
here sums to 17. 
[SOUND] You know, violation. 
Okay, that constraint is violating. 
This one is summing to 14, it's also 
violating, we have another violation. 
This constraint is also violating. 
I mean the whole thing here is violating. 
We are in a completely you know terrible 
state so we are not satisfying any of 
these constraints. 
OK? 
So, since we have these hard constraints, 
you know which is keeping all of these 
numbers different. 
OK? 
What we're going to do is, basically, 
look at, again, at the swapped neighbor 
root. 
We're going to take 2 positions in the 
square and going to swap the values. 
And we're going to look at the effect on 
the violation. 
So, now if we swap 8 and 3, what's going 
to happen? 
Is that, you know, the sum of the rows 
and the columns and so on? 
And the diagonals are going to change? 
But in this particular case all the 
constraints are violated again, okay. 
Now, when you look at this you say, this 
is a nice neighborhood, this is a nice 
way of modelling the problem. 
But every time I swap, you know, most of 
these constraints are going to still be 
violated. 
And therefore I get essentially no 
information, right. 
So in a sense I have nothing, nothing at 
all to drive my search, OK? 
So that's where essentially you can think 
of another way of representing violation. 
Instead of you know having this kind of 
mannequin approach, its I have violated 
or not. 
OK? 
So what you can do is to look at how much 
These constrains are violating. 
Is, is this constraint violating a lot, 
or not? 
Am I getting closer to the right value, 
or not? 
Okay, so that's what we're going to do. 
Because if we only look at the zero and 
one values, essentially We don't have 
enough information to actually drive this 
search, okay? 
So what is, what is, what is, you know 
what is the amout of violations of an 
equality? 
Well, if you look at the value of the 
left hand side, you look at the value of 
the right hand side, you take the 
difference between them and the absolute 
value, okay? 
So once you do that, you get a sense of 
how much that constraints it's violating. 
An therefore, you know, when you make a 
local move you can see that the 
violations of these constraints are 
actually decreasing. 
Instead of saying yes or no, you have 
something that tells you, yeah, yeah, 
yeah, yeah, yeah, you are making 
progress. 
An that's what we are going to use, okay. 
So once again, you know, the magic number 
that we want to get is 15. 
You see all the numbers here, you know 
for all the variations. 
But now the goal is not to find out you 
know, is this [UNKNOWN] satisfy enough. 
Is the, the basic idea is that can I get 
closer to 15 for everyone one of these 
rules verbally? 
Okay, so you see that here, you know, for 
that particular value, 17, the distance 
with respect to 15 is 2, so I have, you 
know, the degree of violation here is 2. 
Okay, so you look at the next one, 14, 
the distance to 15 is 1, so you have one 
violation. 
So when you look at everything here, you 
know, you see, essentially, the various 
violations. 
Of the various constraints. 
And you have a much finer measure on the 
hole close this configuration is a part 
of a feasible solution, OK? 
So the number of violations here while 
they're not to the degree, the order of 
the degree of violation is 21, when you 
swap these two guys know what happens, 
OK? 
So you can see that You have decreased 
the overall number of violations. 
It's 14 at this point. 
Okay? 
So in a sense, and this constraint is 
satisfied, okay, so there is zero degree 
of violation. 
But, overall you can see also that the 
various degree of violation of all the 
constraints. 
You know you see how these degrees are 
basically evolving. 
And so your goal now is to not minimize 
the number of violations but minimize. 
The overall degree of violation of the 
entire system. 
So different, but giving you more 
information. 
Okay. 
So we keep swapping, we swap 7 and 4 
here, and we decrease the total number, 
the total degree of violation to 5, so we 
get closer, closer. 
Okay, so we keep, you know, solving 8 and 
7, and then magically, okay, wow, that's 
a good name for this problem, right, 
magically, we solve the magic square 
problem. 
Okay, no violation anywhere. 
And we have a solutions. 
Okay, so the two key ideas that you see 
here is, once again, okay, so we look at 
this problem and we identify some hard 
constraints and some soft constraints. 
Okay, the hard constraints here is that 
all the digits Have to be different, and 
we maintain that. 
By swapping them, we don't change the 
number of digits or the nature of these 
digits, okay. 
So that's how we do a swap neighborhood. 
We maintain automatically one of the 
constraints, it's always going to be 
feasable. 
And then a second idea here, which was 
improtant, is that we sometimes don't 
want just to resolve about whether a 
constraint is violated or not. 
We want to find out how much is violated, 
and that's what we use for actually 
solving this problem. 
Okay? 
So, we'll see you next time. 
And talking about optimization. 
Look and search for pure optimization 
products. 
Thank you.