0:00

Welcome back. This is discrete optimization, again and

Â we are moving to the second computational part for optimization which is called

Â local search. This is the outline for today.

Â We're going to start with basic interaction to our local search, and then

Â we'll cover very simple local search, which is called max/min conflict.

Â To introduce most of the concepts that we will be dealing with in the next couple

Â of lectures. So, a couple of years ago when my son

Â was, you know, very young, so I gave him the eight queens problem to solve, okay?

Â So I wanted to see how he would just approach it.

Â And so this is what he did, he took all these queens, okay, that I gave him, and

Â he put them on the chess board. Okay?

Â And then what he did was started moving these queens.

Â Okay? Trying to find a configuration where none

Â of the queens were attacking each other. Okay?

Â So, he didn't try to prove the search space, or try to extend you know, a

Â partial solution. He just moved the queens around.

Â And this is exactly what local search is about.

Â So, what you're going to do is you're going to move from configuration to

Â configuration, by doing local moves. So, moving the configuration from it's

Â current state to a state which is very close to it, but you know, but changing

Â it a little bit. In the hope of getting closer to a

Â particular solution. Okay?

Â So local search, okay, is basically working on complete assignments of values

Â to the decision variables and then essentially is modifying those, those,

Â those assignments. Okay?

Â So is there a different from constraint programming?

Â Well, essentially, what we were doing, we're working with partial assignments,

Â and trying to see if we could extend them.

Â And, to make sure that we could extend them, we were trying to prune the search

Â base as much as possible so that we would not try to extend them with a value

Â which, which was not feasible. Local search is way more brutal, okay?

Â So we accept that we're going to violate some of these constraints.

Â And then we just try to eliminate those, those, those, those violations as we

Â proceed, okay? So, how to drive a local search, okay,

Â there will be different things that we can do, okay?

Â And it depends essentially on the nature of the problem.

Â If you have a satisfaction problem, what you will do is you will always start with

Â an invisible configuration. Otherwise you would have already a

Â solution and therefore there would be no problem to solve.

Â And then what we are going to do is start, you know, move from this

Â infeasible, you know, configuration toward, you know, feasibility.

Â And trying to essentially make this configuration more and more, less and

Â less infeasible in a sense. in pure optimization problems the only

Â thing that you have is an objective function, you have no constraints.

Â Okay, and what you are trying to do is essentially go to the optimal solution,

Â so you start with a sub-optimal solution. A local search is going to try to move

Â progressively towards optimality. And then, you have constrained

Â optimization problems which are the most complicated, of course, you have both

Â constraints and optimization. And I will review some of the options

Â later on, once we have seen above satisfaction and optimization problems.

Â Because there are many ways to actually try to address those problems in low

Â consumption. Okay?

Â Now lets look at satisfaction problems first and how to drive the search towards

Â feasibility. And the key idea here is essentially we

Â have this, you know feasible, well this satisfaction problem and we will

Â transform it into a sequence of optimization, into an optimization

Â problem. Okay?

Â So we use the concept of violation. Essentially, at any point, we have that

Â configuration. Okay, basically this assignments of

Â values to the decision variables. And we know that their are a bunch of

Â constraints that are not, that are violated, okay?

Â We can count them, for instance. And then what we can try to, and this is

Â only one of the ways to do it, but we can try to minimize the number of violations

Â to these constraints. So we want to move from a configuration

Â to another configuration where there are fewer violations.

Â Okay? Now how do we do that?

Â Well we have to decide what is a local move.

Â And once again, and we'll see that in the next couple of lectures, there are many

Â ways you can move from one configuration to the next.

Â The simple things is just to select a decision variable and change its value.

Â Okay? So very simple move.

Â Okay? Now once you have defined all moves that

Â you can take, you have to design the one that you're really going to select and

Â execute. Okay?

Â And once again there are many choices, and we'll see many different strategies

Â over the next couple of lectures. But the thing that we are going to do,

Â the, the approach we are going to pursue today is simply a maximum conflict.

Â approach which is essentially a slight generalization of the main conflict

Â heuristic , which has been very successful in a variety of problems,

Â okay? So what is the max/min conflict heuristic

Â doing? Essentially what we do, is choose a

Â variable that appear in the large numbers of violations.

Â So, we look at the variable which, which is really violating a lot.

Â All those variables really violating a lot of constraints.

Â And then what we try to do is to change the value of that constraint so that you

Â decrease the number of violations the most.

Â Okay? So, let me just trade that.

Â Okay, so this is remember this is the constraint programming model for the, the

Â queens problem. And what is interesting to see on that

Â particular model are all the constraints that you see over there, right.

Â So, some of these constraints, once you assign some value to the variables, are

Â going to be violated, are the ones are going to be satisfied, okay.

Â Now visually, this is what this looks like, right, so when you look at the

Â part, so you see. You see here, you know there will be a

Â constraint which is violated. This is another constraint which is

Â violated, okay? So now when we look at the max/min

Â [UNKNOWN], what we want to do first is to compute, you know, the various

Â violations, the constraint violations in which are the particular variables

Â appear, okay? So we look at this particular queen here

Â and now we look at the constraints that they are violating and, of course, what

Â we have to do is to look at, you know, the vertical, the diagonals and the

Â horizontal lines, okay? So in this particular case, we see that

Â this particular variable appear in exactly one conflict, right?

Â This queen is attacking that one. Okay?

Â So we move to the second one, okay, second queen.

Â Okay, and what we see there is that this queen attacks that queen, and it attacks

Â this one, and so this particular queen appears in two violations.

Â Okay? And we can do that for all the Queens.

Â So this is another queen which is basically having two violation.

Â The next one is very aggressive has three violation, and so on and so forth.

Â And so essentially what you see here are all the vi, the violations that these

Â variables, appear ins, ins, into, and what the number that you see over here

Â essentially is the total number of constraints that are violated, okay?

Â Now, the first thing that a maximum conflict heuristic will do is take a

Â queen which appear in the largest number of violation.

Â Okay? So you have a queen here which is very

Â aggressive and appearing at three violations.

Â That's the queen that you're going to select.

Â Okay? So that's the first step.

Â Now we have the queen that we really want to move because this queen is very

Â aggressive. Okay?

Â So what do we do? So now we have to choose the value that

Â we going to to assign to that particular queen.

Â And what we can do is decide, okay so what happens if I move this queen to that

Â particular position, okay how does that change the constraint violation?

Â And what you can see in this particular case is that instead of having three

Â violations, we would have only two, so we are attacking these two queens.

Â And then you can do the same thing for the next queen.

Â Here in this particular case the queen is still very aggressive and has still three

Â viola, three violations, okay? And then we continue doing this

Â essentially for everyone of the possible position for that part of the queens.

Â Okay, and what we see at that point is that, you know, if you want to reduce the

Â violation the most we have to choose one of these values and we can randomly

Â choose, let's say the first one here. Okay, and at that point what we do is we

Â place the queens at that particular position, so that's the local move.

Â We chose the queens. We chose a new position for the queens

Â and we you know, we performed the move. Okay?

Â So at that point we have a new configuration and we can redo all the

Â computations that we have done. We can find that there are five

Â violations overall. We can find the number of violations in

Â which all the queens are participating to.

Â And then we can decide, you know, we can select the queen.

Â One of the queens participating in the most violation and start deciding where

Â to move it. In this particular case only one of the,

Â of the move is going to decrease the number of violation, so that is where we

Â move the queens. We have a new configuration, so what do

Â we do? Exactly the same thing.

Â Now we have four violation. We reduce the number of violation by one.

Â We recompute the violation so the variables, you know, we select the one

Â which appears in the most violation, and we start moving it again at a position

Â that will decrease the number of violations.

Â And we keep doing this, now we have, we move another queen.

Â And we can, we have three violations now. We continue moving this queen again, we

Â have another queen which has two violations.

Â We move, we decrease the violation by one.

Â We keep doing this, another queen which is violated by one, we decrease the

Â violation to one, and then finally we will be able to reduce the violation to

Â zero, and we have a feasible solution. OK?

Â So what is important to see here is that essentially we start from an infeasible

Â configuration which has a number of constraint violations.

Â And we try to move to, you know, configuration which have fewer and fewer

Â violations. And at every step, we try to do that by

Â selecting a queens, in this particular case, which, which is, you know,

Â appearing in the largest number of violation, and moving it to a place which

Â decrease the violation the most. This is just one of the possible

Â strategies. We'll see many strategies in the next

Â couple of lecture but this is essentially illustrating the concept behind local

Â search. Okay?

Â So so in a sense the way to think about local search is that you have an

Â optimization function. Okay?

Â That the, an objective function that you are trying to optimize.

Â And then what the local moves are doing is defining a neighborhood.

Â That's essentially the configurations that are close to the configuration that

Â we are considering right now, okay? So, in the sense that the neighborhood

Â is, from a particular configuration, it's going to give you a set of

Â configurations. And that's the places where we can move.

Â Okay? So, in the particular example of the

Â queens problems, the neighboring configurations were simply the ones that

Â you can reach by selecting the, one of the queens which is most violated, and

Â moving it to a position which decreased the violation the most.

Â Okay? So, in a sense you can think of local

Â search as a graph exploration. You start, you know, from a particular

Â point, and then you start moving to configuration, to another configuration,

Â and so on. And you try to go to configuration which

Â are, you know, more and more feasible in a sense.

Â Okay? So that's what we do.

Â Okay? So the concept, the key, the key concept

Â in local search is the concept of local minima.

Â Okay? That's what a local search does.

Â It gets you a local minima. And what is the local minima?

Â It's a state. Inside the configuration space where,

Â wherever you move, wherever you're neighbors are, okay, they are going to be

Â worse off than where you are. So it's a position where when you look at

Â every neighbor N okay, to the configuration C that you are conf, that

Â you are considering right now, the value of that objective functions of that

Â neighbor is going to be greater than the current value of the objective function.

Â Okay? So essentially.

Â You know, you are at that point, wherever you move, you are going to get worse, or

Â at best, you know, as, as good as you are right now.

Â Okay? So in a sense, the local search that you

Â know, the, the basic kernel of a local search, is going to select a

Â configuration seed, initially, using some method.

Â Then compute the neighborhood, okay. So that's a set of the configurations.

Â Well if you've got a computer set I of all the neighbors that you can, that you

Â can reach, and which are better than the configurations that you are in right now.

Â So we look at essentially all the neighbors which are basically decreasing

Â the value of the objective function, okay?

Â If that set is not empty you select one of these configurations, apply it, and

Â then you recompute the set of configuration in which you can move to.

Â Okay? So basically, you know, local search is

Â this kind of iteration where you move from one position to a better position,

Â and you keep doing that until you reach a local minima.

Â Okay? So local search, you know, gives you no

Â guarantees. Okay, so the only thing that it's

Â going to give you is a local minima, that local minima can be arbitrarily bad, or

Â arbitrarily good. Okay, so one of the things that we'll see

Â in a lot of the lectures later on is how to escape this local minima, or to try to

Â find local minima that are of high quality.

Â Not getting stuck into a poor quality optima and there are many, many ways to

Â do this, and but we'll talk about this later on once we have seen many of the

Â concept behind local search in itself. So for the moment we'll do this greedy

Â local such algorithm, which always trying to improve and gets stuck at some point

Â in a local minima. Afterwards, we'll see how to escape.

Â Okay? Now in satisfactions in satisfaction

Â problems what we saw is that the function F is actually minimizing the number of

Â constraint violations. Okay?

Â And usually when this function reaches zero, we know that we have a feasible

Â solution. If we get stuck in a local minima, which

Â is a value higher than zero, you know, the solution that we found is not

Â feasible. It's, the configuration that we found is

Â not a feasible solution. Okay?

Â So, there are many ways to measure this constraint violation.

Â And once again, this is a topic that we will return to, but what we have done so

Â far is basically looking at the constraints, and deciding if the

Â constraints is violated or not. There are other ways to actually measure

Â these violations. You can consider how violated that

Â constraint is, and we'll talk about that later on as well.

Â