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].