Okay, this back, back to discrete optimization constrain programming part one. Okay so what we are going to see today is, we are going to introduce one more trick in our bags. Okay, so I told you, you know optimization is a bag of tricks. Okay. We don't call them tricks we call them methodologies or, you know paradigms, or computational paradigms or something. So this is one of the main paradigms to actually tackle optimization problems. Okay? So what I'm going to do today is basically giving you a very highlighted introduction to constraint programming. Okay? So the basic principles. Okay, very simple stuff, okay? And in subsequent lectures, I'm going to go into more and more detail, and more complicated things. But, the, the key today is intuition and what is really the essence of constraint programming, okay? And so this is, in two words, you know, in one slide, what, what we going to see, okay? So, constraint programming is two things, which are interesting. First, it's a computational paradigm, okay? Which is very different from dynamic programming, and branch and bond that we have seen so far. So, the key idea is, what you want to do is look at the problem constraints, okay? And try to use them to reduce the search space, okay? So remember, when we saw branch and bond, we had this bonding technique, optimistic evaluation. And the goal there was to prune the search space by using the objective function. Here, we are going to prune the search space by looking at the constraints. And the constraints are going to tell you, ooh, that value. If this sort of value's taking that value, you know, that volume cannot take that volume. Okay? So that's what's going to happen. We going to look at values which cannot appear in any you know, solution any feasible configuration and we are going to remove them okay. And therefore we going to reuse the search base okay. Completely octagonal to the bonding techniques and these things work together nicely okay. Now, there is a another thing which is very nice about constraint programming. And that's why we are starting with this one. It's that we can model problems at a very high level. Okay? So, essentially the, the key to designing good constraint programming is to try to tell the server, have as much of the problem as possible. Reveal the structure. Okay? Tell, you know, don't try to go, you know, use irrelevant coding. Give the structure to the server, then the server can actually explore it. So you'll see what that means, but essentially what you want to do. Is express, you know, large problems in terms of sub-structure, things that building blocks. It's like playing Lego. Okay. So you have basically they are assembling these Lego together. Okay, and the reason is that you want to give the solver as much information as possible. Okay, so I'm going to start with a very simple problem, which is the eight queens problem. So what you want to do is to place eight queens on a chessboard, okay? Now, the first time, you know when I tried to introduce you know, that problem to my dad to explain you know, what I was doing he told me, but I don't have eight queens. I told him just pretend that you have eight queens. But I don't have eight queens. Now look, I have eight queens now. Ooh, look, I have all of them. Daddy you can actually play the game. Okay? So we have eight queens, that's so beautiful of 3D printing, okay? Disclaimer, I have no you know, shares in 3D printing companies. But this is, this is kind of nice. Okay? Anyways, so this is what we are trying to do. Okay? So placing these eight queens on a chessboard says that no two queens are actually attacking each other. Which basically means they cannot be in the same row, they cannot be on the same column, and they cannot be on the same diagonal, upper and lower diagonal. Okay, so that's what we are trying to do. So this is the chess board. Okay, there, and we are trying to place these queens. Okay, so let's look at what we're going to do. So this is the first queen. Okay, we place it there. Now the goal of constraint programming is to reduce the search base. We want to be sure that we remove values that are impossible. In this particular case, these values are impossible. No, we can't place any queens there. Why? Because they are on the same column. You can't place anything on the same row. That's what you see. And then we cannot place anything on the same diagonal. That's what you see there. OK? So we place a second queen. There's a second queen that you see there. OK, so once again we do the same thing. We remove the values which are infeasible. You know, look, this search place is getting smaller and smaller, okay, so we place the third queen, and now nice things are going to happen, okay. So you remove all your same row same color, and what you see at that point, okay, is something which is kind of interesting, right? So what do you see, is that there is one queen here, one particular column which has only one value left. So you know that, you know, you have to place that queen over there. So you can place it, okay? So you place that queen there, because this is the only value that can be placed on that particular column, okay? And then you remove values. And then now, what you can see, is that, okay, so here you have to place a queen again, because this is the only queen that can place on this column, and you know that there has to be a queen on every column, because you know, you have eight queens and they cannot be on the same column, okay? and so, essentially, you place the queen over there, okay? And once again, you prune the search space. You see that again, you have to place that particular queen over there. You place it. Okay? Now you propagate the constraints again, and you see that oh, but at this point, these are the two cells that are left and I have two queens to place. So, I know that, you know, given the first position of my three, first three queens, I can't place, you know, queens on these two stairs because they are going to attack each other. So at this point, if I place the first three queens over there, I know there are no feasible solution. Okay, so what I have done here, okay, is, is, is beautiful, right. So I if I place these three queens, just like propagating the constraints by reducing the search space, I can detect that there are no solutions with these three queens, okay. So I made, three positioned the way they are. So placing three queens here is basically, automatically, by propagating this constraint, this covering that there are no feasible solutions. I don't have to branch on the fourth, on the fifth, on the sixth, on the seventh, on the eighth you know, and the last queen, okay. So what am I going to do? I can say I can place this queen over there. I'm going to reconsider a new position. Let's say this one And I'm going to restart the process, propagating the constraints again. Okay, and trying to see if I can find a solution. Okay, so you have seen the essence of constraint programming at this point. And the essence of constraint programming is essentially using the constraint to reduce the search base. And the search base here is essentially the set of values that the variables can take. So what we have done is basically looking at which values can be removed without removing any feasible solution. We will, we were always conservative, only removing the things that we know cannot be placed there. And when you do there, that, essentially you reduce the search space as much as you can. And then, once you are stuck, you will make a choice, okay. And that choice is going to start another set of propagation. And another set of deductions. Okay? And that's the computational paradigm. Now, there are many choices. Okay? So, what is the choice, you know, it's going to depend on the various problems. But, you know, at the beginning, we simply are going to assume that the choices that we deal with are basically assigning a value to a particular variable. Now, there are many choices, and one of the things that you know is that in optimization many of them will be wrong. Okay, so if you have a choice and if its wrong we'll then do exactly what we've done in branch [INAUDIBLE]. We're going to go back to a previous choice and you know, you know reconsider it and lets say assign a new variety to a particular variable. Okay, so that's the two assets here that we have, okay. So we essentially constraint propagation for removing infeasible values. The from the domain of the variable, the set of values that a variable can take, and then we have the ability to make choices when we are stuck, when we can't deduce anything else, okay? So let me illustrate this. So what I want to do now, so you have the essence. So, this is, this is essentially what capture, what constraint programming can do. So what I want to do now is use an even simpler example, okay? And then look at the model and how essentially you can actually use the constraint for pruning in such spaces. So what we're going to look is, you know coloring a, a, a map. And so the key idea is that you have a set of territories here. They can be state, countries, whatever. Okay? And you will want to color them such that two adjacent territories are not colored with the same color. They don't receive the same color. Okay. Now there is a beautiful theorem. Actually this is the first theorem that was proven with the help of a computer. That every map can be colored with four colors. So we never need more than four colors. Okay so and essentially what we have to do is write a program which given a map okay. And you know list of you know adjacent territories. Is going to color the map such that no two adjacent territories are going to receive the same color. So this is so this is essentially what we're going to do. And so once again, you know, what we do is we have to find what the decision variables are. Any, with any kind of methodologies, you know, that we will explore, like local search, like constraint programming, like mixing teacher program. The first step is always going to be choosing, choosing the decision variables, okay, and then expressing the constraints in some sort of decision variables. What are going to be the decision variables here? Well, for every one of these territories, you will have a decision variable, and that decision variable is going to tell you what is the color of that particular territory, or country, if you're modeling a map of countries, right? And then, the domain of these decision variables are all going to be all the colors, okay? So since we are in the map, okay, we know that we need only four colors. So we'll choose them, you know, blue, red, green, and brown, right? Whatever. OK. So four different colors, that's what, that's all we need. And now the constraints are going to basically specify that two adjacent territories can all have the same color. Okay, and the best way to do this is to use a non-equality restraint. Okay, so this is a model. Okay, so this is a model in a higher level modeling language and I'm going to go over here some of these aspects. So what you have there, is that you have an enumerated title that tells you what other countries that we are interested in. Okay, so this is a tiny subset of you know the European countries. Okay. And in this particular case we're going to use also a list of colors that's basically the values that the variables are going to take. And we take black, yellow, red and blue. Okay, that's what you see over there. And the next line is basically telling you what the decision variables are. Okay. So what you see here is that you have a set of colors. For every country there will be one color okay, decision variable. Which is associated with every country, okay? And thus, essentially the color that that country's going to receive. And this is a variable which is ranging over a set of colors. Okay? So the, the this, the values that every countries can take is basically black, yellow, red and blue. Now, what you, what you are trying to do is solve, okay, this is a feasibility problem. Okay? We are trying to solve. You know, and find a solution which essentially uses these four colors and satisfy all these adjacent c constraints. Okay? So, you know that Belgium is adjacent to France, so we want to be sure that the color of Belgium is going to be different from the color of France. Okay? So, you these not equal constraints saying okay, the value of these two variables have to be different. Same thing you know between you know, Belgium and Germany up to the very last which is basically between Germany and Luxembourg. These two countries are adjacent so you don't want them to be colored with the same value. Okay so that's essentially a high level model of a constraint problem okay, and you have these constraints that are basically specifying the relationship between these decision variables. Okay? So this is essentially the, the, the, the small part of Europe where you see all the countries. Okay? And at the beginning what the constraint program is going to do is trying to prune the search space. But at the beginning you can't prune anything in a sense because all the countries can take all the values. Okay? And so nothing is going to happen at the beginning. So these are all the possible values that these guys can take. All the possible colors. And then at some point you're going to make a decision because you can't propagate anything, you cannot reuse a search space. And you color, you are going to color, you know, beige and black. Okay, so, once you do that you can start pruning the search space. Because, essentially, now, you know all the adjacent countries Okay. Cannot take the value black. Okay. And this is what is happening. Okay. You remove the value from the set, from the domain of these values so they can't take that value anymore. Okay. Now you color Luxemburg in yellow. That's the tiny pieces that you see over there, right. And so the adjacent countries to Luxemburg, okay, Germany, France. Cannot be colored with yellow, so you're going to remove these values from, you know, Germany and, and, and France. And then you're going to color Germany, let's say in red. You're going to remove all red from all the adjacent countries, okay, Denmark, you know, the Netherlands and, and, and France. France is going to become blue, okay. Then you will have to choose a color for the Netherlands and Denmark, which in this particular case are easy to do. Okay? So, that's the way the constraint program is going to work, okay? So, once again, so those constraints, and I will tell you exactly the pruning that they do later on, but that's, that's the, they will basically prune the search base the way I've shown you. Okay, once again, the computational paradigm is using the constraint to reuse the search space when you're stuck, okay. You basically make a choice. The first choice that I've shown you is coloring Belgium in black. Okay, so in the particular coloring problem, at the beginning there was no space search reduction, there was nothing you could propagate, and I will tell you why later on, right? And then afterwards, you know, what happens is you give a particular color to Belgium. Okay so you gave the color black, okay? So, when that happens, you look at these constraints in which Belgium appears. Okay? And so essentially these constraints can be, can be rewritten you, by replacing you know, the decision variables of Belgium by black. And now, what you see is that these constraints are turning into, ooh, France has to be different from black. Ooh, Germany has to be different from black. And those are very easy, you know, constraints to deal with, because at this point, if you want to satisfy these constraints, what, the only thing that you have to do, to do is say, ooh, France can take all these colors. If France can still take the color black, I have to remove it, because if it takes the value black. Is, this constraint is not going to be satisfied. So, you can use these constraints to start pruning the search base. And that's where the constraint programming system does, okay? So, that's what going to happen. Oops. Look at this, so oops, I'm go back, so you give that, and you remove the value of these variables. Okay, so once again when you think about constraint programming, it's not a branch and bond framework. It's called a branch and prune framework. In the sense that what you do is you prune the search base but you don't use a bonding technique to do that. What you do is you use the constraints to remove the value from the variables, from the domain of the variables. And once again when you start to decompose the problem, it's like the branching part of branch and bond. Okay? And the pruning is based on essentially feasibility information. You look at the constraints and you try to remove value that cannot appear in any solution. Okay? Remember when we discuss France to be different from black. The color of France has to be different from black. What that means is that, you know, we want to, when we remove the value black from the domain of France, we know that this is a value, is the valid inference that we can do that. We are not removing any solution, because if France was blocked that constraint would be violated. Okay? So, so one of the, a couple of things that I have to mention. You know, constraint programming is a complete method, okay? So, it's going to find a solution if one solution exists. It can find all solutions if you want all of them. And if you are in an optimization problem, it will find the optimal solution. And I will come back to this later on and how we do optimization using constraint programming. But one of the key things is that this, this technique, this methodology, this computational paradigm can find optimal solutions. Can always, there's always a guarantee that it will find a feasible solution or the optimal solution. Of course, you know, it may have an exponential behavior, which means that it can actually take a long, long time to get it. But, if you give it enough time, it will always find a feasible solution, it will always find an optimal solution in an optimization problem. Okay? The focus, this is the other things that I have to tell you, the focus in, in constraint programming is on feasibility. Okay? It's basically, you know how to use constraints to prune the search space, okay? So it's a very different focus than branch and bond. Where the focus is on bonding. Is finding these optimistic evaluation. And, and is relaxation. Here it's, it's a different kinds of relaxation, in a sense. And what we focused on in feasibility, and removing as many values as we can from the domain of these variables. Okay? So, this is a, this is a way you can view a constraint programming system. You have a search, okay, and you have a constraint store. What you are trying to do all the time is ooh, can I study [INAUDIBLE] this constraint, can I study [INAUDIBLE] this constraint? Okay? And then when you start, when you say okay, I can study [INAUDIBLE] constraint, but I cannot prune the search space. What the search is going to do is order a new constraint. And the constraint store is going to say yes or no. Okay, am I still satisfiable or not okay? And so in this particular case, it's yes, I'm satisfied, you can continue. Okay, and sometimes you know the search is going to send another constraint, and then you say, no, no, no, no, no, no I have violated, my constraints are violated you know give me another constraint, okay. Remove that one and give me another one, okay? So this is inside of a constraint programming system, okay. So what you see there is essentially the search base representation, the domain store. That's essentially the domain of all of the variables. And what you see gravitating around it are the constraints, okay? And this is kind of interesting, right? These constraints are only interacting with the search base. They are always trying to say ooh, can I remove values there. Ooh, am I feasible, but we'll come back to that in a moment. But, they don't know about each other, and that's both a strength and a weakness, okay? So it's easy to add new constraints, because they don't interact with the other one. They just interact with this representation of the search space. Okay. So, so, so I alluded to this already, what does a constraint do. A constraint has two goals in life. One of them is checking feasibility so the constraint is always looking at the domain store. The set of possible values that a variables can take. And is always asking, ooh, am I feasible? You know, can I, can I find a solution to myself? Okay? So, that's feasibility checking. So, we always try to see if any one of these constraints is feasible, independently of the other ones. Right? So, you look at one constraint in isolation, and you ask yourself can I satisfy this constraint? Can I find a solution? That's the first thing you always do with these constraints. And the second goal in life for a constraint is to prune the search space. They're going to look at the search space and then say can I knock down some values there? Because then my search becomes, you know, smaller, and that's how you can curtail this exponential growth, okay? So the second goal of pruning is basically looking once again, you know, constraint evaluation, and saying, ooh, to be satisfied I have to remove these values in the domain of those variables. Okay? And that's what you do, that's what the constraint does. You have these two things, very, very it's checking, making sure that the note that you're exploring is potentially feasible. And then pruning, trying to reduce the set of values of the various variables. Okay? I talked about this, basically you know, this is basically summarizing of what I just said. Okay? Of course, you only prune when you know that you are feasible. You will never try to prune when you are already in infeasible state. Okay? Now, the core, the core of a constraint programming system, is the, is propagation engine, okay. And the way to think about is it's, it's a very simple iterative algorithm, fixed point algorithm where, you know, the constraint engine is going to take one constraint, and say, are you feasible? OK, and if the constraint is feasible it's going to tell the constraint, true! And so the constraint is going to prune the search space. And then the engine is going to say, select another constraint, and say, are you still feasible, okay? Can you prune the search space? And the engine is going to continue doing that with all these constraints. You know, are you feasible, can you prune? OK, until there is no values that can be removed from the domain of any variables. So there you reached this stable state which is called a fixed point, right? And then you know that at this point you've inferred as much information as you can, okay? And so the system will typically go back to the search component and ask Ooh, make a choice because I'm stuck at this point if you haven't found a solution so far. Okay? So that's basically the key. So the key is basically this propagation engine which is basically selecting constraints asking if they are feasible, and then, if they are feasible, asking if they can prune their search base. Okay so if you come back to this beautiful eight queens problem, right? So my beautiful queen, right? And so I'm basically asking so what are the decision variables. And I told you that before, there are many, many different modelings, okay, of any kind of optimization problems. And the eight queens problem is one of these problems where you have many modelings. So I'm, so I'm going to show you one of them, okay. But there are many, many, others, and that's what makes optimization very interesting in general, because you have to find out, you know, which model am I going to use, is it going to be good or not, you know, and so on and so forth okay. And we'll see what it means to be good or not, but in a sense, it's kind of, will I be efficient, will I explore a small part of the search space. So I'm going to show you one modeling of the eight queen problems. And the key idea there is that I'm going to associate a decision variables with every column. I know that I have to place you know, eight queens. I know that you know, the queens can not be on the same column otherwise you, they will attack each other. So I know by definition that I can associate a queen with every column, okay. And therefore, the only, the, the, what the decision variable is going to do, for every column is, is going to decide which row the queen on that column is going to be placed on, okay? So decision variable, one queen per column, and the, the decision variable is denoting the row for that column on which the queen is going to be placed. Okay? So these are my decision variables in this particular case. Now what are the constraints? There are three types of constraints so know that we have a queen which is associated with everyone in the column. We have to make sure that they are not placed on the same row, otherwise they would attack each other. And not on an upward and a downward diagonal. Okay, so, yeah that's what I said. Okay and so what you see here is once again a high level constraint programming model to do that. Okay, so we basically this is for the eight queen, so we have a range from one to eight. Okay, That's basically the eight column. Okay, so now we have a decision variable which is called row okay, for every one of this column I have to associate a row with that column, and there are eight rows so that's a set of values. That, that particular, that particular variable can take, and what you see over here are all the constraints, and what I'm basically doing for stating these constraints, I take two, you know, two rows two columns i and j. Okay? And I'm basically assuming that i is, you know smaller than j, and then I'm basically specifying that they cannot be on the same row, they cannot be on the same, you know, upper diagonal and, and lower diagonal. And that's what you see over here, okay? So these are basically the constraints. And once again they are like in the coloring. They are, you know, not equal constraints. I'm basically saying that the row of i, has to be different from the row of, of j. Okay? And then that, you know, the row of i, is different from the row of j, plus j minus i, which is basically giving you one of the diagonals. Okay. So these are the rows, this is the upwards diagonals that I was mentioning and this is the lower diagonal, okay? And I do that for every pair of queens you know, ordering them by you know, I take i and then I take j, which is greater, okay. So when you have that what you may wonder is, you know, what happens when I give the value one to a popular queen? When I place, you know, the queen on column one to row one. Well these are essentially, what you see there, are essentially all the constraints. Okay? I just explained that model here into this set of constraints. When you give the value one to the part of the row, so this is the expansion right, so this is not on the same row. This is not on the same diagonal, this upward diagonal. This is not on the downward diagonal. Okay? And so now, if I give the value one to row one, what's going to happen? Well, this is, this constraint is going to become you know, row two has to be different from one. Okay, so you will make sure that the second queen, the queen on the second column, okay, cannot be placed on row one. That's what this constraint will do. The next constraint that you will see here is going to say that, you know, row two is different from row zero. That's not useful because we know that zero is not part of its domain. And the last one here is basically going to tell you that row two has to be different from two. That is essentially, the diagonal that's going up there, right? And so, well, it actually, it depends the way you see this, the, the test. But it's basically saying that it cannot be placed on, on the second row, on the second row, okay? And you can use that for removing the search base from that value from the domain and therefore reducing the search base, Okay? Once again I told you that the two things that it does is visibility checking and pruning, OK. Lets skip this slide but what I want to do here is basically telling you a little bit How this is done for the very simple constraint that we have considered here. For the map coloring and for the, the, the queens the, the, the queens problem. Okay? So, essentially we'll consider two variables, x and y, and we going to say that x can take the value between zero and two. And that y can take the value between one and three. Okay? Typically what we do and in many of lectures that concern programming that's what I'm going to use. We are basically saying that x, the variable x, has this domain, zero, one, two. And that y has this domain, one, two, three. Okay? And so, the domain essentially is, the domain of x okay, is going to be represented by dx, is a set of these values, okay? And so one of the goals is going to be trying to knock down values from this domain all the time. Okay? Sometimes I'm going to use intervals as well to denote you know, 1 through 5. To denote the value one, two, three, four, five. Boring, right? So, but this is a notation that I'm going to use from time to time. Okay? So, let's look at the constraints. x has to be different from y. Okay? So, that, that constraint, and assume that the domain of the variables are this. Okay? So, one of the things that I have to do is to do feasibility checking. Is this constraint feasible? Obviously here I can see that it's feasible. Right? I can take zero there and three there, and it's going to be feasible. Okay? So, the general rule here is that what you do is you basically take the union of these two domains. Right? And, and you look, if the size of that union is greater than one. If it's greater than one, okay? So what that means is that I can take at least two values. Okay? And therefore, you know, I can, I can, the constraints is going to be feasible, okay. So in this particular case, I can see that you know, the size of this thing is four, the union of that is obviously greater than one, and therefore, or greater or equal to two like I'm writing there. And then you are sure that this constraint is feasible. Okay? So, this is all, so feasibility here is going to be very, very simple to to achieve. now how do we do pruning. This is what I've shown you before. Right? So, essentially the pruning in the examples that I've shown is happening when the variables can take only one value. Okay? If it has two values, essentially you can't prune. It happens only when a variable has only one value that you can start pruning the search space. If a variable can take only one value, you have to make sure that the other variable cannot take that value, and you remove it. And of course that's, you know, that's symmetric whatever the value is. Whatever the variable is,it will go from one direction to the other, or you know, from the first variable to the next one. Okay? So if Y is, if Y is to have the value two, you will remove two from the value, from the value of x. Okay? So that's how you do pruning. Now this is very, very simple, right? So this is a very, very simple constraint. One of the beautiful thing about constraint programming is that constraints can be arbitrarily complex. And we'll see examples where the constraints itself is an optimization problem and you still can use polynomial algorithm for actually pruning the search spaces and we'll go into that, okay. So this is a really, really tiny example to show you the principle feasibility to checking pruning, but we'll see much more interesting examples with feasibility checking and pruning I'm going to use very interesting algorithm. Okay? So, see you next time. This was the first lecture on constraint programming. There will be many more to come, with many more interesting things.
