0:00

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.

Â