0:00

Okay, so last lecture on constraint programming.

Â This is the square lecture. So, we're going to see a lot of problems

Â on squares, magic squares, perfect squares.

Â It's a really interesting thing. we are in search again.

Â Okay, so trying to see various techniques for doing search.

Â And once again you know, this is just introduction okay, so there are a lot

Â more to this area, it's a very active research area.

Â But I'm touching upon a number of topics that are interesting, okay.

Â So we're going to try with value variable you know, labeling.

Â Most people are going to do variable value labeling, and at some point you

Â know, it's boring. So what we're going to do is something

Â very different, which is called value/variable labeling.

Â So instead of choosing the variable and then assigning the value, we want to look

Â at the problem in a completely different fashion, right?

Â We want to look at the value, and then choose a variable to which to assign the

Â value, that value, okay? So take a value and then we take the

Â variables to which we want to assign that value, okay?

Â Now you're going to say, this is crazy, right?

Â So this makes absolutely no sense, okay? But in practice they are a lot of

Â applications where you know that a particular value has to be assigned,

Â okay? This is typically happens in scheduling,

Â this also happens. In time tabling problems where you know

Â that a class has to assigned to something, a professor has to be assigned

Â to particular classes and so on. Or in scheduling, you know that class has

Â to start at a particular point in time, okay?

Â So it's very useful in many applications, okay?

Â So what I want to illustrate is that we've a really nice example.

Â I'm going to get out of the way, okay? So what you see on the screen are 21

Â different squares, okay? They are squares, and they all have a

Â different size. Hello, okay, so I'm on the other side.

Â Okay, and so the goal here is to look at all these squares, okay?

Â And make them into one big square. Okay?

Â So we have to pack them and arrange them in such a way that we make this big

Â square. Okay?

Â Now, I assume that you are completely bored at this point.

Â You can't sleep. I'll let you look at this thing and you

Â can spend the next 20 minutes trying to put all these squares inside the big

Â square. It is very interesting, okay?

Â So 20 minutes, okay? So and what I want, so this is one of the

Â solutions, okay? You know won't let you look at it very

Â quickly, you know, I won't let you look at it very long because I want you to be

Â able to solve this puzzle so you can sleep right.

Â So, so if we try to solve that using you know a constraint program, we have first

Â to decide what the decision variables are going to be, okay?

Â And they're going to be either x and y coordinates of every one of these

Â squares. Okay the bottom left corner of one of

Â every square. It could be the top right corner if you

Â want, but you have to choose one and that's where you going to basically.

Â That's what, the convention that you're going to use.

Â In all particular case, we take the bottom left corner and that's the

Â position of the square. As soon as you know these two, the x and

Â y-coordinate of that corner, you know where the square is.

Â Okay, what are there going to be the constraints?

Â There are two type of constraints. This first one is easy.

Â The squares have to fit in the, the small squares have to fit in the bigger square,

Â and then obviously the square can't overlap.

Â You want to make this big square, but you, you, you, you can't have the squares

Â overlap, okay? Now, there are also some redundant

Â constraints. Okay, so I won't go into all the details,

Â but I want to give you the intuition. So here is the attrition, so if you look

Â at that vertical line here, so that vertical line corresponds to X

Â correlation and it's basically intersecting a number of squares, so what

Â you want to be sure is essentially that the sum of the sizes of the square that

Â this line is intersecting is equal to the size of the big square, ok so that is the

Â redundant constraint that you have OK and this is essentially a model, its a you

Â know a very wide model. OK expressing everything that I've told

Â you about. OK so you have the decision variables

Â which are the x and y coordinates there for everyone in the square then you have

Â essentially a set of easy constraints there that are basically telling you that

Â the square have to fit into large square and then you have two types of

Â constraints that I mentioned. These are the redundant constraints.

Â And they're basically, raise fine constraints for a particular position P,

Â you're going to look at the square which are basically intersecting with that

Â particular we've, we've I, actually intersecting with P okay, containing P in

Â the sense and making sure that the size is the side of the big square.

Â So this a [INAUDIBLE] constraints. And then you have the overlap constraint

Â which are easy to save. Essentially if you have two square you

Â have to make sure the square, one of the square is on the left, on the right, on

Â top or on below the other square. Okay, so once again it's a big [UNKNOWN]

Â of the various cases. Okay.

Â So, but this is just a statement of the problem.

Â What is interesting here is the value variable labeling.

Â Why do we do that? Why, why don't we just place, you know,

Â the various squares dis, different position?

Â And the basic idea here is that we know that we have to fill this big square.

Â And it's going to be completely filled, okay?

Â So there is no empty space in that particular big square at the end.

Â So we know that every time there is an empty space we have to place a particular

Â square over there, okay? And that's why we are using a value

Â labeling here. Okay, value variable labeling.

Â Because, as soon as there is an empty space, you know, I know that I have to

Â choose one particular square to be put there.

Â And therefore I can just look at the square and choose which one is going to

Â be placed there. Okay, visually, okay.

Â So look at this, I placed one square, I placed another square.

Â You know I know, I know for sure that one square will have to be placed there.

Â Which one is it going to be? Okay, so another one and then a tiny one

Â there. Oh, there is an empty space there which

Â is the square that I'm going to have to place there, and that's the basic idea

Â behind the value labeling procedure that I'm going to show you.

Â Now you can write very complex one, or you can write a very simple one, I'm

Â going to show you a very simple one which works almost as well as the most

Â complicated well the most complicated ones.

Â But it's actually very simple to state. So, so that's what I want to show you.

Â Okay. So what we are going to do?

Â Essentially what we are going to do is, what we are going to do is we're going to

Â take this vertical slice. Let's say p, okay.

Â And then we are going to decide, for all the square, do I place p there or not?

Â Okay? So it's very, very simple, okay?

Â I take all the x coordinate p. And on this side whether I place, you

Â know, which squares do I place there? And then I move to the next coordinate, I

Â do the same, and the same, and the same, and the same.

Â And then I do the same for the y, and the y, and the y.

Â And that's what I do, okay? So this is the search procedure, okay?

Â Very simple I told you. We could do a more complicated one.

Â But it doesn't bring very much, you know, benefit in practice.

Â So I take, basically, all the X coordinates, okay, and then I need to

Â read for all the squares that you see there, and then I decide, you know, do I

Â place the particular square in that position, or not?

Â Okay, and most of the time, it's going to be no's.

Â But essentially that's all I have to do. Okay?

Â So, these are for the x coordinate, and the bottom here is for the y coordinate.

Â That's all I have to do in this particular case.

Â Okay? So, it's a value variable labeling.

Â I take a value and I decide you know, do I place it, is this square being placed

Â at that particular location or not, okay? And this is very, very effective on this

Â particular application, okay? So this is, basically what you're seeing

Â now is variable/value labeling and value/variable labeling, okay?

Â What I'm going to talk about now is a very complete, completely different way

Â of actually branching which is called domain splitting and I'm going to use

Â another square example which is called the magic square example, okay?

Â So essentially, you have the number, okay?

Â You have a num an, a set of numbers to be placed in a particular square.

Â All the numbers have to be different, and then all the rows, columns and diagonals

Â you know have to sum, you know with, when you look at the numbers, have to sum to

Â the exact same number, okay? So this is a magic square of side three,

Â okay? So you see the value 2, and 9, and 4,

Â okay? So if you look at the sum of every one of

Â these lines, okay? So this is one of these rows, okay?

Â No, it's going to sum to, in this particular case, 15 so all these rules

Â are going to sum to 15. You're going to look at all these columns

Â now, they are also going to sum to 15 and the two diagnols are also going to solve

Â to 15 so you see two, five and eight there that's basically fifteen and the

Â other diagnaol is going to sum to 15. That's what you have to do.

Â Okay, So basically, if you have, if you have a, if you have a square you know, 3

Â by 3, okay? You know that you have to place a number

Â between 1 and 9 in the square such that the sum of all the rows, the sum of all

Â the columns, the sum of all the rows, and the sum of the two diagonals are equal to

Â 15 in this popular case. Okay, now this seem easy enough right so

Â we could do that by hand okay what I wanted you to think about is can you do

Â that for a square of 11 by 11 so we are going to place essentially 121 number in

Â this particular square and we have to make sure that all the rows, all the

Â rows, all the columns and all the two diagonals are going to sum to the same

Â value, okay So how do you do that, okay. Now actually what you should really think

Â is that can you actually serve that for a square which is a million by million,

Â okay. And this can be done, okay.

Â This can be actually can be done efficiently.

Â Like you know for today, let us think of 11 by 11, okay?

Â Now the key question here is that when you try to do that, which variable are

Â you going to assign? So do you want really to assign?

Â So, this is the solution to this one. So so, so one of the things that we need

Â to think about is how you, how you are going to do the search for this

Â particular example, okay? So before thinking about this, let's just

Â think about what the statement of the problem here, okay?

Â So what you see there basically the decision variable s, okay?

Â That basically means for every square, you have to decide which values you give,

Â okay? The values in this particular case are

Â going to be between you know, if the square is of size 11 by 11, is going to

Â be 11 square, so 121, okay? So, that's the domain of the variables,

Â and then what you see here are the various constraints, okay?

Â All the rows and the columns and the two diagonals and to sum to the same value T

Â that can easily be pre-computed at the beginning, okay?

Â And then you are forced to make sure that all the numbers, all the slots inside the

Â square are different so you assign different values to every one of the

Â slots. So, that's a statement of the problem,

Â which is easy now. What is of course is the most interesting

Â part is how do you actually, how do you actually do the search?

Â Okay, so one of the things you could do is, you could, you know, select one of

Â these squares. Okay, this one looks nice, okay?

Â Well let's start there. And you could decide, oh I'm going to

Â assign a value to that possible variable there.

Â Okay, but essentially when you look at this thing, right, so this is the big

Â square, right, you are going to take this variable and assign it a value, okay?

Â But this is essentially completely random at this point, right?

Â So you have absolutely no clue what you're doing, right?

Â So, you're going to take a particular variable, take a value, but it's, you

Â know, it's a completely random guess. And in addition to being very random

Â guess, it's going to be a very strong commitment.

Â You're basically saying, I want that particular variable to be that value,

Â okay? So can we do something which is like a

Â weaker commitment, okay. And that's what we're going to do.

Â So, domain splitting is basically you're going to select a variable, and instead

Â of assigning a particular value, you're going to say ooh, wait a minute, right?

Â So, I don't want to make a big decision here, right?

Â So, what I'm going to say is that I'm going to you know, see if I can actually

Â find a solution if I assign you know, a value which is in the upper half of my

Â domain or the bottom half of my domain. Okay, so you split the domain in two, and

Â you say, okay, so I'm going to try to place this particular value, that this

Â particle, I'm going to basically assume that that variable is in the upper domain

Â or the lower domain of, of, of its actual domain.

Â Okay, and this is what we can do. And this is a search procedure expressing

Â you that. Once again you are going to, you are

Â going to loop until you assign all the variables, okay?

Â At every one you select a variable using the first [UNKNOWN] principle, so a

Â variable which is very tough to actually assign, and what this is doing here, here

Â is not assigning a popular value to that variable.

Â What you do is you take the midpoint in the domain.

Â That's the mid value that you see there, okay?

Â And then you basically say, oh, the variable has to be smaller than the mid

Â value, or greater than the mid value. So the choice that you do here, okay, is

Â much weaker. You are basically assuming that the

Â variable is inside a subtle value. But you haven't specified which one.

Â So it's a much weaker commitment, and since we have absolutely no clue in this,

Â no clue in this particular problem, what to do, this is going to be a very

Â effective strategy in this particular example, okay?

Â So you're going to say oh yeah, but this is a puzzle.

Â Now this strategy, is actually extremely good For very hard car sequencing

Â problems. So remember we showed that before a

Â couple of lectures ago. So you cars on an assembly line.

Â Every one of these beautiful cars okay, is basically requiring some options you

Â know, a moon roof or leather seats and things like this Now to actually prune

Â these options on the cars you have these production units, which are basically

Â putting these thing as the car is moving in front of the production unit, and

Â therefor you have to be careful. You have to sequence the, the car in such

Â a way that you have the time to actually put the various options on every one as

Â the car is moving in front of the production unit, okay?

Â So we add the first time I've shown you that.

Â Essentially a simple, variable value strategy, okay?

Â Which for a lot of instances is actually working pretty nicely.

Â But on some of the very hard instances, and some of the instances which are

Â actually invisible, it's not the best strategy that you could use.

Â And one of the things that you have to recognize here is that the options that

Â you see here, okay? They have different strengths, some of

Â them are really tight. Okay, so lets say the first two here are

Â really tight. There is essentially no slack.

Â It is very difficult to insert a new car. With that popular option.

Â And when you look at the some of the, the other options that you see there, okay?

Â Especially, the fourth option, for instance, it's a very, you know, loose

Â option in a sense, there are many ways you could actually place all the cars,

Â there are plenty of areas where you see essentially no cars being placed.

Â Okay, so in a sense when you are trying to solve these problems you know what you

Â want to do, and this is once again the first real principle, is focus on the

Â options that are really really difficult, okay.

Â But once again, you don't really care about the various types of cars.

Â What you really care about is you know, do I you know, do I place a car in this

Â particular slot, requiring that options or not, okay?

Â So, what you want is not reasoning about the different types of car, you want to

Â reason about the various options, okay? And you want to focus first on the

Â options that are very difficult. And then you decide you know if you place

Â a car requesting that option, okay? In that particular site but you are not

Â actually placing car you are saying aw there will be a car in that particular

Â option but I don't want to commit to which car at this point.

Â Okay, and this is the key idea that you are focusing on all the options and for

Â the option that are really difficult. And so in a sense, the way to do this is,

Â is, is very natural. Okay, so what you do, is that you do a

Â search procedure which iterates over the options.

Â We are not iterating over the various types of count.

Â We are looking at the various options, and then for every line of the assembly,

Â every slot of the assembly line, we are deciding if that particular slot in the

Â assembly line is taking the option, does the first That's the first that's, that's

Â the first choice that you can make there or it's not taking the option.

Â Okay, so why does it work? Because you look at every one of the

Â options, and if that for every one of the slot in the assembly line, you're going

Â to decide do I think that option is enough, okay?

Â Not assigning the car, but then you take the next option, you do the same thing.

Â And so at the end of the day what we are going to do, is for every one of these

Â things, you are going to choose very specific configuration because

Â essentially the other constraints are forcing you to choose between which,

Â which they are basically forcing the type of car you have to produce.

Â Okay, so very interesting here. What you do is essentially domain

Â splitting. Every time you make a choice here, you

Â are basically splitting for the particle of slot variable, the set of cars in two

Â parts. The one that they are requiring the

Â options, or the one not requiring the options, okay?

Â So then you choose first to assigne cars for the options, and then the car not

Â taking the options. Okay, so essentially, this is once again

Â a domain splitting. You have a mutual commitment.

Â The only thing you are doing is deciding whether you add that option for that

Â particular slot or not. Okay, very effective on some of the most

Â difficult car sequencing instances, especially when you want to prove

Â infeasibility, okay? So, so far we have seen a lot of

Â different things, okay? Variable/value symmetry.

Â Value/variable symmetry, okay? We have seen that we can use a first

Â weighted principle by using physical linking formation, and sometime using

Â the, the objective function. And we have seen that in some instances,

Â okay, we, we wanted a weaker commitment and new domain splitting What I want to

Â do now is come back to, you know I promised you that, come back to symmetry

Â breaking and look at how we can actually break symmetry breaking, not by using

Â constraints, but during the search, okay? You will see why this is important, okay?

Â And we going to go back to this scene allocation problem, right?

Â So these beautiful people, you know, Georges, and Julia, and Clyde.

Â You know, I like Clive a lot, so you do it, it was almost James Bond.

Â Or maybe that was just a marketing, you know, ploy that he had.

Â But he would have been really great James Bond.

Â Anyway, Dan Craig is a great James Bond too.

Â But anyway, so I'm getting ahead of myself here.

Â So what we are trying to do is shoot these beautiful movies, okay.

Â And the actor plays in different scenes, and remember, they were paid by the scene

Â that they They play with. And they were not, you know, paid by the

Â scene they played with, they were paid by the number of days that they were on the

Â set, okay? And we had constraints on the number of

Â scenes that you can...that you can shoot every day.

Â So you can shoot at most k scenes every day And the objective was obviously to

Â minimize the cost, and one way to do that is make sure that the actors when they

Â spend a day on the cast are basically shooting as many scenes as possible.

Â Note there were a lot of symmetries on this particular product.

Â Do you remember? Okay, so the symmetries were about the

Â various days, right? So, The days, at the beginning, were all

Â interchangeable, Monday and Tuesday, they were no difference for these actors,

Â okay? So the way we eliminated those symmetries

Â by putting constraints, okay? So the first scene that we wanted to

Â assign, okay? The things that we said was that, you

Â know, it was day one. It could be only assigned to day one,

Â because at that point, all the days were the same.

Â For the second scene we were considering, we were basically saying okay, that scene

Â can be assigned to day one, that's where scene one has been allocated.

Â Or a new day, which is basically day two because all the other days are the same,

Â at this point, are essentially [UNKNOWN]. And so in a general fashion, when you

Â look at saying I, you were basically looking at the day that were assigned

Â before, plus a new day. And that's what this beautiful formula

Â was telling you. And so what we did was, you know, doing

Â this nice model, and then you have the symmetry breaking constraints where, you

Â are basically saying that scene 1 is allocated to 1, and then all the other

Â scenes were allocating to the values assigned to the previous scene plus a new

Â one. Okay, and so you were basically, what we

Â were doing, what basically putting all these constraints Inside the model, okay?

Â So there are symmetry breaking constraints.

Â They were getting rid of the symmetries in the popular instant, in the popular

Â problem. And, and, and, and, and these symmetries

Â were basically taken care of by putting these additional constraints, okay?

Â Now, when you think about this and you think about search.

Â These constraints have the dramatic effect on search, right?

Â So if you use the first [INAUDIBLE] principle, what's going to happen, okay?

Â Essentially, these constraints are going to dictate the, mostly the way you

Â are basically doing search, why? Because the first scene is already

Â allocating, there is no choice. Then you look at the second scene, which

Â is in the positive order in which we stated the problem, right?

Â So, that 2nd scene is the domain of 2. The 3rd scene, as the most domain of 3.

Â The, the 4th scene most a domain of 4. So essentially, from a, when you use the

Â first stated principal, you are basically, by stating these constraints,

Â you are basically choosing the order in which you have to assign the variable.

Â Is that good? Well sometimes yes, sometimes no.

Â But in this particularly case, it essentially prevents you from using any

Â kind of sophisticated characteristic because it's basically you know, you're

Â basically constrained by this, this, this constraint that I'm basically reusing the

Â domain of the variable. So can we avoid it?

Â So there is an interferance between the symmetry breaking constraints and the

Â search heuristic that you could use. If you wanted for instance to use a

Â heuristic that was using the first principal, the smallest domain and they

Â save the [UNKNOWN] most expensive ones first, you are not doing that.

Â Because essentially these symmetry you know these symmetry breaking constraints

Â were imposing a particular order. So can we actually get rid of this and

Â the, the answer is yes. And what we have to do is take the

Â symmetry breaking constraints and not impose them in the modern but kind of

Â introduce them dynamically during the search.

Â So we're going to impose essentially the same, same symmetry breaking constraints.

Â But dynamically during the search. Okay, so in a sense what we the big

Â difference between imposing them inside the model and imposing them doing the

Â search is that the ordering is going to be different and its going to be

Â discovered incrementally by looking at the variables which are the most

Â difficult to assign. Okay, so, so in a sense what we're

Â going to do. The, the search heuristic is going to be

Â the search heuristic is going to be, you know, choosing the next scene and that

Â next scene will take the one which is the smallest domain between [UNKNOWN] the

Â first fail principle and in case of time we'll take the most expensive scene.

Â What, why would, would we do that? Because those [UNKNOWN] if, if they are

Â many of these actors that are very expensive, we want to start with these

Â scenes because essentially, you know, that will give us a, that will increase

Â the directly the value of the objective function.

Â If we place that particular thing and some of the actors, you know this is a

Â new day for them or no, this is not a new day for them.

Â That will have a dramatic effect on the objective function.

Â So the heuristic is going to take the scenes which have the smallest domain and

Â in case of ties we're going to break that by looking at the scene which is

Â expansive, which basically means, you know, the scene which contains a lot of

Â actors whose fees are very high, okay? So, now essentially we have to choose

Â what we are going to do, so we have to break the symmetries during the search.

Â So when we take it, when we take a scene like this, we're left to decide which

Â days we will consider for that particular scene.

Â And, once again, we're going to do exactly the same trick as we did for the

Â static constraint. We're going to take the existing days

Â plus one, a new one, okay? But now, we are not imposing these

Â constraints inside the model, right? So we are imposing them during the

Â search, okay? So when we label the scene with the only

Â values we will consider for that particular scene, so the values of the

Â days that we have used before, plus one, okay?

Â And the advantages here is that you essentially break the same symmetries.

Â You break the same symmetries, you break, you sometimes, you use the constraints a

Â little bit later, but they don't interfere with the search heuristic at

Â this point. They don't change your euristic by simply

Â by putting by putting these constraint dynamically during the search, you don't

Â change the euristic. Okay, so this is what you can do here.

Â This is essentially the search procedure expressing that.

Â So what you see here is that when you try the value for the particular variable you

Â take the exitsing data to compute it above there.

Â Okay, that's the days you have already used.

Â And then you take a new one, okay? So, that's how you're going to break the

Â symmetries there. You don't consider all the possible value

Â in the domain of the variables. The only thing that you do is you take

Â the existing days plus a new one. That's the only value that you select for

Â that [INAUDIBLE]. Of course, what you see on top of there

Â is basically selecting the, the minimum value.

Â the minimum value, the, what you do there is select sine, which is the smallest

Â domain, and then in case of [UNKNOWN] the most expansive, okay?

Â So, that, you see a basically a dynamic coloring there, choosing the one which is

Â the smallest domain and this is not actually influenced or impacted.

Â By the Symmetry Breaking constraint and then the one and in case of tie the one

Â that is the most expensive. Okay, so once again this is the

Â essentially the same Symmetry Breaking ID, the difference is that we don't

Â impose any static in the model what we do is we actually introduce this constraint

Â dynamically during the search by limiting the set of values that we consider for

Â everyone of the variables. Okay, so this is the, the, the last

Â technique though that I want to talk about, which is randomization and

Â restarts. Okay, so we'll come back to this when we

Â talk about large number root search, which is the most sophisticated use of

Â this. But what I'm going to talk about now is

Â very simple, but it can be very powerful for some example, okay?

Â And so, the basic key intuition here is that sometimes there is no obvious search

Â ordering, but the structure of the problem is such that there is one.

Â We just don't know which one it is, okay? Alright, so this kind of interesting

Â problems where there is a good ordering but it's very difficult to find it.

Â So, what do you do when you are in a situation like that?

Â You know that there is a good ordering, but you don't know which one.

Â We, you don't know where it is. So what we going to have to use is brute

Â force, right? Completely stupid.

Â What we are going to do, is we going to randomize, okay?

Â We going to randomly generate it some ordering.

Â Hopefully we'll, we'll try to find it good ones.

Â And then if this doesn't work, if we can't find the solution in a reasonable

Â time, we're just going to restart, generate another ordering, and try, and

Â try, and try to see if we can find solution with that ordering, okay?

Â So, the key idea is that we try, you know, we try something, if it doesn't

Â work, we stop early, right? So we say ooh this is looking really bad

Â and you try another ordering and we try to see if we can do better with that

Â ordering, okay? So in a sense the key idea is to try a

Â variety of random ordering. We execute the search with those

Â ordering. If it doesn't work after a, after a

Â certain time limit or a number limits on the number of failures.

Â You restart the search and you see if we have another ordering you can do better,

Â okay? So this is very useful for this magic

Â square problem for instance. So when you so, look at this thing, I

Â told you before, we can assign a value to a variable we also in no clue what we are

Â doing. Even when we do domain splitting, we

Â basically have no clue what we are doing. But on this particular problem, sometimes

Â you have good orderings that aren't going to make a big difference, okay?

Â So where do we start? We don't know, so what we're going to do

Â is we basically going to randomize okay? So instead of choosing essentially the

Â variable which has the smallest domain, okay, we're going to select let's say,

Â one of the tree of best variables, one of the tree variable we should have a

Â smallest domain. We just randomize the search a little

Â bit, we don't commit to the variable which has the smallest domain.

Â And then we're going to limit the amount of time we spend, and if we exhaust the

Â time limit we're just going to basically restart the search, possibly by

Â increasing the time limit so that we Improve the, you know, the chance of you

Â actually finding a solution. And this is the only thing that you have

Â to do, okay? To do that, so what you see you know, in

Â shadow gray over there, are basically you know, the search procedures that I've

Â shown you before. And we are making very, very few changes.

Â One of the changes that you see there is that you are randomizing.

Â Instead of selecting the variable with the smallest domain, we are selecting one

Â of the three variables, which have the smallest domain you know?

Â And then essentially we have these repeat loop which is basically restarting this

Â search. Okay, and we are making sure that we can

Â only search for a certain time limit. Okay, and if we fail, you know, finding a

Â solution, when we restart, we increase the time limit.

Â That's all we have to do for actually implementing this, okay?

Â So what we do, basically we do the search here, you know, it's randomized, so we're

Â going to pick up the variable ordering in a random fashion.

Â If you find the solution great. Okay, if we don't after a certain time we

Â restart. We increase the time limit.

Â We re execute this procedure. Which basically means that we're going to

Â find another random ordering for this particular variable, okay?

Â And, and we're going to search with that particular random ordering and if you

Â find that solution great. Otherwise we'll redo this thing until we

Â find the partiuclar solution. Okay, so this is kind of brute force,

Â okay? Once again, it's combining all the

Â techniques that we've seen before. We can put anything in there.

Â But on top of this, we are basically introducing this restart and

Â randomization, which can be very powerful for some classes of application.

Â Okay, so at this point we have basically covered all the lectures on constraint

Â programming. The next set of lectures are going to

Â look at local search and look at very, some of the same problems using a

Â different technology. Thank you very much.

Â [BLANK_AUDIO].

Â