discrete optimization, before last lecture on constraint programming, okay?
So, one of the things that I told you in the beginning is that there are two
aspects which are really critical in a constraint programming system.
One of them is constraint propagation, and we spend a lot of looking at that in
the, in the past lectures. And what I'm going to, the other, the
other one is search. And that's what we're going to talk about
in the next two lectures. It's also a very active area of research.
And if for what I'm going to talk about today is basically an introduction to
some of the concepts. Basic introduction once again, to make
you curious, right? So, the key idea in constraint
programming is that search is based on feasibility information, okay?
So what the constraint programming system is doing very well is basically pruning
the search base, based on constraints and feasibility, making sure that, you know,
as many of these constraints are feasible.
And the search, of course, is going to explore that information, because that's
the big information that we have in a constraint programming system.
Okay? So what does it mean to explore this,
this feasibility information? So we, we have this, very high level
principle that we want to apply, which is called the first-fail principle.
And it's very counterintuitive. But actually, it makes a lot of sense.
So, so what you are trying to do. So, the, the, the principle tells you.
Try first where you are the most likely to fail, okay?
So, and the way to think about this is that you have a bunch of tasks that you
have to accomplish. And you get a reward if you accomplish
them all. And one of them is really hard.
Don't postpone it, focus on it. Because the easy stuff, you know, you can
do the easy stuff but you are wasting your time if you can't do the hard stuff.
That's what this principle is telling you.
Try first, you know, where it's the most, when you are the most likely to fail,
because you want to fail early, okay? And so, essentially what it means is
that, you don't want to spend time doing the early stuff, and then go to the tough
stuff and see that, no I can't do the tough stuff, go back and try to do the
easy stuff in another way, such that, in the hope that the hard stuff is going to
be a little bit easier. That's not what we want to do, okay?
We want to start with the hard stuff as quickly as possible.
And of course by starting with the hard stuff what we hope is that we'll have a
very small search tree. And that easy stuff we can take care of
at the end. So, that's the first-fail principle.
You want to start first with where you are the most likely to fail.
Okay? Now, what does it mean?
Well, look at this beautiful queens example that we have.
Okay? So, what does it mean to, to look at
something which is though, where you are most likely to fail?
Okay, now all these queens, they have different set of values, okay?
And what you want to do is to start with one, which is as few values as possible.
This one is only one value. You know that you have to place the
queens there, okay? Now, if there are some values which have,
some queens have four values, and some which have two, you want to start with
the ones which have only two values. They're harder to place and that's where
you want to start from. Now we're also constructing smaller
searchbase because you only have a branching, you know, factor of two
instead of four, okay? Now, sometimes all the variables have the
same set of values at the beginning. Okay?
So this is what we see in this particular graph coloring example.
At the beginning, I can use all the colors for actually, all these countries.
Right? And so which one do I start first?
Okay? Now I can say, oh I'm going to start with
Denmark. Okay?
But Denmark, in this particular case is easy.
Right? So it only connected to Germany.
So there is only one color that it won't be able to take and therefore, I don't
want to start there because I'm going to give it a color that's going to remove a
color from Germany. But that doesn't mean anything, right?
So, what I have to start from is someplace which is essentially connected
to many, many, many different countries, and that's where it's going to be the
most difficult to color. In this particular case, guess which
country it is, right? So, we'll start with Belgium, okay?
For instance, okay, so I want to illustrate or sort of first-fail
principle on a very interesting example. It's a puzzle.
It's called the Euler Knight problem, okay?
It's basically having a knight in chess, and making sure that you visit all the
places in the chess board, and visit them exactly once, okay?
Following the rules of chess. Okay?
Now, its pretty tough to do but, that manually.
I know only one girl who actually did it, did that.
She was in a computer science class, computer architecture, you know, she was
completely bored and so she was playing this thing during class and some point
she said, yeah! And she found it, okay?
So if you can't sleep at night, try this. It's not easy.
Okay? Now, it's an interesting problem because
it's connected to a lot of problems in routing.
It's kind of an abstraction for these problems, okay?
So, but essentially, what I want to show you is the first-fail principle on this
particular example because it's very intriguing, okay?
So this is the model. You see a very simple model for this.
The decision variables are the jump variable, okay basically for every
position in the chess board. Okay, you have to, you have to know where
the knight is going to jump next. Okay, and so you are basically 64
variable, one for every, you know, position on the chest board and that
tells you where you jump next. Once you've those you can follow the path
of the knight. Okay, and the only constraints that you
have is that all these variables have to make up a circuit, okay?
So, if you start from one place and follow this, this path, you're going to
go back to exactly the same place, okay? And you will visit every position in the
chess board exactly once. Okay?
Now this is a tough constraint to implement.
We can just think about it and we'll come back to that later on, okay?
But this is essentially how the model is stated here.
Now, one more thing that we have to do is we have to now basically specify for
every position where the knight can jump, that follows basically the rules of chess
and this is this boring set of positions that you see over there.
you know don't try to spend your time understanding it, but you know you just
have to know that this can be done, okay? Now what I want to show you is
essentially how the first-fail principle is working on this particular example,
okay? So let's look at the chess board.
This is the chess board at the beginning, okay?
So, where do we start? Okay?
Are we starting at the middle? Are we starting here?
Are we starting over there? Okay?
Well, the first-fail principle is telling you.
Start first where you are the most likely to fail.
You know? Where are the position where it's
difficult to actually, you know, jump, okay?
Well, these are the corners, right? So when you look at this guy here, okay?
There are only two position where we can jump.
And as soon as it jumps to one. Okay, you know that the, you know, you
know where the previous, you know where, essentially, the previous position was.
Okay? So essentially, there are only two
positions. And as soon as you choose one, you also
fix the value of another variable's. Okay?
That's where you're going to stop. These corners are tough, because there
are only two places where they can jump. If you're in the middle, there are these
eight places where you can jump. Many more positions.
Okay? So, we know where to start.
Okay? So, the key, the key question here is
where do we go next? Okay?
And every time you know, I, I've, I, I've been teaching a class on combinatorial
optimization and ask this question. People always tell me, okay well you have
to take this guy probably because it has very few positions.
Okay? But this is not what the system is
going to do. Once again, the system is going to look
at all the position, and find out the one which is the toughest to assign.
And where is that? Well, that's in the other corner, okay?
Because, once again, there are only two position.
Where for this guy, there are at least three or four positions, four for that
particular one, okay? So, essentially, what's the system is
going to do? Is built some small parts all over the,
the places. And the constraint is essentially trained
to make sure that you can connect them into a big circuit.
Okay? At every, every stage and after every
assignment. So this is a partial state of the system.
You see we built a couple of interesting paths all over the place.
Okay? And this is a solution at the end.
Okay. Beautiful, right?
And so this is what the first-fail principle is actually doing on the Euler
Knight problem, finding the variables which are the toughest to assign.
They have a small domain. That means that they are tough to assign,
okay? So let's put this principle in
perspective now and let's look how you program this search and how you can
express them, okay? So I am going to start with the eight
queens problems again so that I can illustrate a little bit how you write
this search procedure. So what you see here at the bottom.
Is a search procedure for the queens problem, okay?
And there are various things that you can see there.
So the first instruction is a for instruction, and basically it's telling
the system iterate for every one of the queens.
I want to assign a value to every queen, so I have to iterate over all the queens.
The second instruction is actually pretty interesting, it's the try all
instruction, and essentially that instruction is a non-deterministic
instruction, it's not a loop. What it's trying to do, is to assign a
value to the particular variable. It's to choose a value in a
non-deterministic fashion in this particular case.
Okay? Now it's going to try to do that, find
one popular value. But he's not going to try them all at
this point, okay? It's just going to pick a point, okay, in
a non-deterministic fashion. And then execute whatever the body is
below. Okay?
But in, but if, if later on, okay, the execution fail, okay, it's going to come
back to this instruction and try another one.
Okay, so the for loop is kind of iterating over all the values, a try all
knows that it has many possibilities to actually do something, and it's going to
pick up one. And if later on you are, you know,
basically in the failure mode, you're going to come back and try another one,
okay? That's non-deterministic instruction.
The last string that you see in this string is essentially, as soon as you, as
you have a variable, you have selected a value for the variable, you are going to
basically add a constraint to the constraint stock.
Stating that that variable is basically assigned to that value, okay?
So that's three component that we'll see in a lot of the search procedures that
we're going to see in this lecture. You start by iterating over the variable,
you non-deterministically choose a value for them, and you add a constraints
inside a constraint store, okay? Remember the computational paradigm,
okay? So what you have is basically a
constraint store that's pruning the search base.
And then a search, okay? What a search is doing is always adding
constraint to the constraint store. Okay?
The search is adding constraint to the constraint store and the constraint store
is basically sending a razor back to the search saying okay, yeah, good.
Success. Okay?
Or sometimes you have the constraints and they say failure, okay?
You, you can't satisfy your constraints, when something like that happens you go
back to non-deterministic instruction, and try another value for the variable.
Okay? So in a sense, what you need to do, is
that every time a constraint fails, okay? So, you go back to a non-deterministic
instruction and try a value which has not been tried again.
Okay? If there is no possibility for that
non-deterministic instruction, what you will do is go back to another one.
That was, you know, the previous one, and try that and, and try another value for
that non-deterministic instruction, okay? I'm going to go into, into, into the
details of this a little bit more such that you see how basically the syntax
corresponds to the semantics that I'm talking eh, talking about, okay?
So when you look at the full instruction essentially what you are doing, you can
view that, you can unfold this loop. And what you're really doing is do a
bunch of try instruction for the first variable, for the second variable and so
on. Okay?
Now if at any point you fail for one of these, you're going to go back to the
previous one and try another value. If that, if there are no values left,
you're going to go back to the previous one, try another value and so on.
That's what the system is doing, is basically, you know,
non-deterministically selecting some of these values.
If at some point you fail, you go back to the previous one and try another value
for that one. If there are no one left, you go back one
more level up, okay? So essentially that's what the system is
doing there. Okay, for every queen, there will be this
non-deterministic instruction and you are trying to see which values you can assign
to that queen. Okay?
Now, let's look a little bit into a, into more detail on how the trial instruction
is working. It's a non-deterministic construction,
which can potentially explore all the values.
But it only does so when basically activated because of a failure, right?
So in a sense, what you can do is this try all instruction is a big try
instruction, okay, and which is basically telling you, oh try first the value one,
the value two, the value three, and so on and so forth, okay?
And in this particular case, if you fill for the value 1, okay, so if for instance
the value 1, when you put it inside a constrained system, the constrained
system is telling you oh, I have a failure.
You will go and move to the next instruction in the try, okay?
And try the second value, and so on and so forth, until you arrive at the bottom.
If none of these values are actually successful, you will go back to a
previous try all instruction. And select the next try in the list where
you had left out. At the you know, at, at the previous
execution of that try all. Okay?
So, that's essentially what these try and follow you know, the way they are
interacting, and the way non-deterministic computations are
basically computed. Okay?
So, what I want to talk about now, are the various ways you can use these
primitive to do various kinds of search. And I'm going to talk about variable
value ordering. Value variable labeling.
Okay? I'm going to talk about domain splitting.
I'm going to say how you can focus some of the search on the objective function.
I'm going to talk about symmetry breaking during searching and randomization and
restart. Okay?
In this lecture, we'll do only the first one, which is basically variable and
value labeling. We're also looking at the value of the
objective function at the very end of the lecture.
Okay? So variable value labeling are probably
the most simple search procedure that you can design in a constraint programming
system. It basically has two stamps, the first is
you choose a variable that you want to assign and then you choose a value.
The first step you have to reiterate for the valuable, the second step is a
non-deterministic step. Now, once again, you want to apply the
first-fail principal, which means that you want to find the ordering of these
variables in a very, in a very, in a very specific way.
You want to start with the one which have the toughest.
Toughest to, to, to give a value to. And typically, you know, the size of the
domain of the variable is going to be a good indicator of what is tough and what
is not tough. Okay?
The variable which has the smallest domain means that you have remove a lot
of value from that variable. It means that it is probably interacting
with a lot of other constraints. It's probably a variable which is very
difficult to instantiate, okay, to give a value to.
Okay? So the ordering that we will want in
general is going to be dynamic. You just don't want to fix the ordering
of this variable. You want to choose a variable which has
the smallest domain, then you propagate all the constraints, that reduces the
search space again and then now you want to look for the next variable with the
smallest domain. Okay?
And that variable may not be, it may not have been the second most attractive
variable the first time around because now more values have been removed.
Okay? So what you want to do is iterate this,
you know? Choosing the variable with the smallest
domain, propagating. Choosing the variable with the smallest
domain, propagating, okay? And so this is essentially all you can do
that in a, in a constraint programming system.
The forward instruction, though, is capturing an order.
And in this particular case, what I do is that I look at the variable, row r.
And I take the size of its domain. And that basically tells me what, at this
particular point in time, the domain size of that variable is.
Okay? So, in a sense, you have to view this
iteration now as look at all the variables, okay, which have not been
given a value so far. Take the one which is the smallest
domain, and execute the body. Okay?
So take the variable which has the smallest domain, no?
You execute the body. So which basically will assign a
non-deterministic, will assign non-deterministically a value to that
variable. Then you're going to go back to the loop
and look at all the variables that you have not selected, you know, at this
point, and take the one which has the smallest domain now.
Okay? Why am I saying now?
Because essentially the constraint that we added, it started constraint
propagation in the constraint engine, okay?
In the constraint propagation part of the system and has reduced the size of the
domains, okay? So basically what you have to see
compared to what we have seen before, what we are doing though, is choosing the
order of variables that we're going to give value to in a dynamic fashion.
Taking the one which has the smallest domain with every time, okay?
So essentially what we are seeing is a two steps.
First step is choosing the variable. And typically the variable which has the
smallest domain. That's the first-fail principle.
Know at any point in time, you may have several variables which have the smallest
domain. Which one do you choose?
Okay? One of the good principle that you have
to try, that, that you can try to apply, is choose the one which is the most
constrained. Remember the graph coloring at the
beginning, all the variables, all the countries, have exactly the same color,
possible colors. Okay?
Which one did we choose? We chose a country which was connected to
many other ones. It was very constrained.
That's what we can do. Okay?
Now, in the particular case of the queens problem, for instance.
We can choose the queens which has the smallest domain.
And if there are ties, we can choose the one which is as close as the middle of
the board as possible. Why?
Because when you place a queens in middle, it has a tendency to remove more
values than when you place a queen on, on the sides of the chessboard.
Okay, so how to do that well essentially this is easy you take the for all
construction that you've seen before and know you're using a lexicographic you
know criteria. You take the viable which is the smallest
domain and in case of ties the one which is closer to the middle of the chest
wall, okay? So, essentially, same thing as before
except that now instead of choosing the value with one criterion, I'm basically
using two criterion, okay? One starting with the smallest domain and
then the variable which is the most constrained.
Okay? Now remember also one of the things that
we had on, on the, on the queens problem, was this dual modeling, where you had
variable fold associated with a column, and then variable associated with the
row, okay? Now, that's a good example to show how
you can both choose a variable ordering in a dynamic fashion, and a value
ordering in a dynamic fashion, okay? So what you see here, okay, is that we
look at the raw variables as the one that we want to assign.
Okay, and we choose the one which is the smallest domain and then we have to
assign a value okay, and when we assign a value essentially this is equivalent is
in giving a value to a color. So we can try the value in an authoring
which is also the first-fail principle which says oh but choose the value which
corresponds to the column variable which has the smallest domain because that.
Column is thought to instantiate as well. And that's what you, that's what you are
doing here okay? You choose a dynamic holder for the
variables. Then you choose a dynamic holder for the
values. In both cases, you're actually applying,
you know, the first-fail principal, okay? So that's the kind of things that you can
do in a constraint programming system. Choose a dynamic ordering for the
variable. Choose a dynamic ordering for the values.
A very interesting thing that you can do. Okay, so in general, okay so when you
have a variable value labeling what you're going to do is to choose the most
constrained variable, okay first. That basically means the smallest domain
of the variable that fails very often. Okay that's the kind of things that you
want to do. And the value ordering is going to be
generally a little bit different. What you want to do is try to maximize
the probability of finding a solution. So we're going to try to value which
actually leaves as many options as possible in the future.
Okay? Because that helps you find a solution.
You leave flexibility for the variables. So in a sense here we are trying to find,
trying to, you know, look at the region which is the toughest, but also trying to
find a feasible solutions. of course, sometimes this is, you know,
this is just a heuristic, this is not, you know, a rule that you have to apply
generally, but this is typically something which is useful in practice, in
many, in many applications. Okay?
So essentially, what, what I've shown you so far is that in constraint programming,
most of the time, okay, we try to use feasibility information for branching.
And why? Because that's essentially what a
constraint programming system is doing. It's basically reasoning about
feasibility, pruning the search base, and that gives you a lot of information about
which variables are tough, which variables are central to actually the
problem that we are trying to solve. But sometimes we have an optimization
problem and it's very. So you're trying to find an optimal
solution for an objective function and it's important to look at the value of
the objective function as well. Okay now as I told you before, when we
start the optimization problem now the optimization function becomes the
constraints. Every time you find a solution.
So either we use this search base, sort of, the feasible information is still
very important. But we can do it better than just
exploiting the feasible information. I also, you know, reasoning about the
objective function itself. And what I want to do now is illustrate
that on a very interesting problem. And which is generally very challenging
for optimization system. And constraint programming is really nice
for solving these problems. So it's called Serializable Data
Services, and it's essentially implementing protocol that gives you that
gives you software which is reliable. Okay so this is something that we did
with some colleagues at UConn, and the protocol that we were trying to implement
is called eventually serialized data services.
And the way to think about this is that you have a set of components, okay,
software components that you have to map on a set of hard, on a set of machines.
So a set a set of hardware, okay, and what you do, and, and, and to do that,
you have to satisfy some reliability conditions so there will be different
components that have to be located on the same machine, some components that have
to be located on different machine. But you want this protocol to be as
efficient as possible so you want basically to minimize the traffic the
communication traffic between these various, various component.
If you place them on different machine, its going to cost you more to accurately
exchange data between them. Okay, so to, so when you formalize this
problem, okay in a mathematical programming sense.
It become what is called a generalized quadratic assignment problem.
So, this is the data that you have. You have a communication frequency
matrices which tells you how much two components are interacting with each
other. That's the, the data f.
You have a, a, a matrix which tells you the distance between the various hardware
components this is a distance matrix. H, okay, its essentially the number of
hops that you have to do from you're moving from one hallway to another one.
Then the decision variables are going to be this vector x and x is going to tell
you for every component on which hardware that particular software components is
going to be placed. And c is a set of components and then you
have two types of constraints. You have the colocation constraints and
the separation constraints. The separation constraints are telling
you that two components cannot be on the same machine.
If they are you know, the, the protocol wouldn't be reliable.
And then you have these colocation constraints just saying the opposite,
these two things have to be on the same machine.
And the objective function is going to be minimizing the traffic in the network.
So you have the frequency matrix that you see there, and then you have the number
of hops and Xa and Xb are basically the decision variables.
It's where do you place component a, where do you place component b?
And what you are trying to do is to minimize the communication between all
the components, okay? And that, of course, depends on how much
they communicate, and how far away from each other they are basically placed ins,
on, on the, on the hardware. So this is the model, okay?
This is the model that we have for this partical, these, these generalized,
quadratic assignment problem. Okay, the model is essentially a
straightforward implementation of what I just presented on the next slide.
You see the objective function, which is a direct translation of the objective
function that you saw on the previous slide.
You see the matrix H there, H Matrix, index by two variables, so that's the
element constraint that we saw a couple of lecture back.
Then what you see, the two types of constraints, the colocation constraints,
which are basically telling that, you know, two components in, which have to be
colocated have this, are assigned to the same component.
And then for the separation constraints, what you have is basically all different
constraint. What is really interesting in this
particular example is the search procedure, because it's going to focus on
the objective function. So this is what you do.
At every step, until all of the components have been placed, you will
take a component i, which is interact, which has not been assigned so far, and
which is interacting with as many components as possible.
It is a very high, essentially, it is a very high communication um,it maximized
the communication with another component, okay?
So that's what you see there. Select i which is the maximum frequency
of communication with another component chain.
Why do you want to focus on that particular component?
Because its interacting heavily with somebody else and therefore it will have
a big effect on the objective function once you place it, okay?
And therefore, that's why you want to focus on this one.
You will gain a lot of information as soon as you place that component.
Okay? The way you will place it, is obviously,
by trying to make sure that you don't make this objective function increase too
much. You basically want to find a value, such
that you minimize. The communication, the number of hops
with respect to the other components that it, that it's interacting with, okay, and
that's what you see in this particular instruction.
And then you assign the particular component to that particular location.
So in a sense what is important here is that you are using information on the
objective function. To drive the search, and this is a
critical aspect on this problem. If you don't do that, essentially the,
the execution time is going to increase by an order of magnitude, okay?
So let me try to summarize what we have seen in this lecture.
What we have seen is a, a one type of, of search procedure which is very frequently
used in practice, it's called variable labeling procedure.
We saw the first-fail principal, which tells you to try first.
When its very, where, where it's hot. Okay, where you are most likely to fail.
And that's, you know a first-fail principle typically is using feasibility
information you know, which variables have the smallest domain.
But, it can also use information from the objective function.
By looking at which components are difficult to place, and would increase
the objective function which would make some of the other constraints much more
difficult to, to satisfy, okay? So we'll more sophisticated search
procedure during the next lecture, but this gives you a first taste on what you
can do in a constraint programming system.
Thank you.