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