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.