Okay, so last lecture on constraint programming. This is the square lecture. So, we're going to see a lot of problems on squares, magic squares, perfect squares. It's a really interesting thing. we are in search again. Okay, so trying to see various techniques for doing search. And once again you know, this is just introduction okay, so there are a lot more to this area, it's a very active research area. But I'm touching upon a number of topics that are interesting, okay. So we're going to try with value variable you know, labeling. Most people are going to do variable value labeling, and at some point you know, it's boring. So what we're going to do is something very different, which is called value/variable labeling. So instead of choosing the variable and then assigning the value, we want to look at the problem in a completely different fashion, right? We want to look at the value, and then choose a variable to which to assign the value, that value, okay? So take a value and then we take the variables to which we want to assign that value, okay? Now you're going to say, this is crazy, right? So this makes absolutely no sense, okay? But in practice they are a lot of applications where you know that a particular value has to be assigned, okay? This is typically happens in scheduling, this also happens. In time tabling problems where you know that a class has to assigned to something, a professor has to be assigned to particular classes and so on. Or in scheduling, you know that class has to start at a particular point in time, okay? So it's very useful in many applications, okay? So what I want to illustrate is that we've a really nice example. I'm going to get out of the way, okay? So what you see on the screen are 21 different squares, okay? They are squares, and they all have a different size. Hello, okay, so I'm on the other side. Okay, and so the goal here is to look at all these squares, okay? And make them into one big square. Okay? So we have to pack them and arrange them in such a way that we make this big square. Okay? Now, I assume that you are completely bored at this point. You can't sleep. I'll let you look at this thing and you can spend the next 20 minutes trying to put all these squares inside the big square. It is very interesting, okay? So 20 minutes, okay? So and what I want, so this is one of the solutions, okay? You know won't let you look at it very quickly, you know, I won't let you look at it very long because I want you to be able to solve this puzzle so you can sleep right. So, so if we try to solve that using you know a constraint program, we have first to decide what the decision variables are going to be, okay? And they're going to be either x and y coordinates of every one of these squares. Okay the bottom left corner of one of every square. It could be the top right corner if you want, but you have to choose one and that's where you going to basically. That's what, the convention that you're going to use. In all particular case, we take the bottom left corner and that's the position of the square. As soon as you know these two, the x and y-coordinate of that corner, you know where the square is. Okay, what are there going to be the constraints? There are two type of constraints. This first one is easy. The squares have to fit in the, the small squares have to fit in the bigger square, and then obviously the square can't overlap. You want to make this big square, but you, you, you, you can't have the squares overlap, okay? Now, there are also some redundant constraints. Okay, so I won't go into all the details, but I want to give you the intuition. So here is the attrition, so if you look at that vertical line here, so that vertical line corresponds to X correlation and it's basically intersecting a number of squares, so what you want to be sure is essentially that the sum of the sizes of the square that this line is intersecting is equal to the size of the big square, ok so that is the redundant constraint that you have OK and this is essentially a model, its a you know a very wide model. OK expressing everything that I've told you about. OK so you have the decision variables which are the x and y coordinates there for everyone in the square then you have essentially a set of easy constraints there that are basically telling you that the square have to fit into large square and then you have two types of constraints that I mentioned. These are the redundant constraints. And they're basically, raise fine constraints for a particular position P, you're going to look at the square which are basically intersecting with that particular we've, we've I, actually intersecting with P okay, containing P in the sense and making sure that the size is the side of the big square. So this a [INAUDIBLE] constraints. And then you have the overlap constraint which are easy to save. Essentially if you have two square you have to make sure the square, one of the square is on the left, on the right, on top or on below the other square. Okay, so once again it's a big [UNKNOWN] of the various cases. Okay. So, but this is just a statement of the problem. What is interesting here is the value variable labeling. Why do we do that? Why, why don't we just place, you know, the various squares dis, different position? And the basic idea here is that we know that we have to fill this big square. And it's going to be completely filled, okay? So there is no empty space in that particular big square at the end. So we know that every time there is an empty space we have to place a particular square over there, okay? And that's why we are using a value labeling here. Okay, value variable labeling. Because, as soon as there is an empty space, you know, I know that I have to choose one particular square to be put there. And therefore I can just look at the square and choose which one is going to be placed there. Okay, visually, okay. So look at this, I placed one square, I placed another square. You know I know, I know for sure that one square will have to be placed there. Which one is it going to be? Okay, so another one and then a tiny one there. Oh, there is an empty space there which is the square that I'm going to have to place there, and that's the basic idea behind the value labeling procedure that I'm going to show you. Now you can write very complex one, or you can write a very simple one, I'm going to show you a very simple one which works almost as well as the most complicated well the most complicated ones. But it's actually very simple to state. So, so that's what I want to show you. Okay. So what we are going to do? Essentially what we are going to do is, what we are going to do is we're going to take this vertical slice. Let's say p, okay. And then we are going to decide, for all the square, do I place p there or not? Okay? So it's very, very simple, okay? I take all the x coordinate p. And on this side whether I place, you know, which squares do I place there? And then I move to the next coordinate, I do the same, and the same, and the same, and the same. And then I do the same for the y, and the y, and the y. And that's what I do, okay? So this is the search procedure, okay? Very simple I told you. We could do a more complicated one. But it doesn't bring very much, you know, benefit in practice. So I take, basically, all the X coordinates, okay, and then I need to read for all the squares that you see there, and then I decide, you know, do I place the particular square in that position, or not? Okay, and most of the time, it's going to be no's. But essentially that's all I have to do. Okay? So, these are for the x coordinate, and the bottom here is for the y coordinate. That's all I have to do in this particular case. Okay? So, it's a value variable labeling. I take a value and I decide you know, do I place it, is this square being placed at that particular location or not, okay? And this is very, very effective on this particular application, okay? So this is, basically what you're seeing now is variable/value labeling and value/variable labeling, okay? What I'm going to talk about now is a very complete, completely different way of actually branching which is called domain splitting and I'm going to use another square example which is called the magic square example, okay? So essentially, you have the number, okay? You have a num an, a set of numbers to be placed in a particular square. All the numbers have to be different, and then all the rows, columns and diagonals you know have to sum, you know with, when you look at the numbers, have to sum to the exact same number, okay? So this is a magic square of side three, okay? So you see the value 2, and 9, and 4, okay? So if you look at the sum of every one of these lines, okay? So this is one of these rows, okay? No, it's going to sum to, in this particular case, 15 so all these rules are going to sum to 15. You're going to look at all these columns now, they are also going to sum to 15 and the two diagnols are also going to solve to 15 so you see two, five and eight there that's basically fifteen and the other diagnaol is going to sum to 15. That's what you have to do. Okay, So basically, if you have, if you have a, if you have a square you know, 3 by 3, okay? You know that you have to place a number between 1 and 9 in the square such that the sum of all the rows, the sum of all the columns, the sum of all the rows, and the sum of the two diagonals are equal to 15 in this popular case. Okay, now this seem easy enough right so we could do that by hand okay what I wanted you to think about is can you do that for a square of 11 by 11 so we are going to place essentially 121 number in this particular square and we have to make sure that all the rows, all the rows, all the columns and all the two diagonals are going to sum to the same value, okay So how do you do that, okay. Now actually what you should really think is that can you actually serve that for a square which is a million by million, okay. And this can be done, okay. This can be actually can be done efficiently. Like you know for today, let us think of 11 by 11, okay? Now the key question here is that when you try to do that, which variable are you going to assign? So do you want really to assign? So, this is the solution to this one. So so, so one of the things that we need to think about is how you, how you are going to do the search for this particular example, okay? So before thinking about this, let's just think about what the statement of the problem here, okay? So what you see there basically the decision variable s, okay? That basically means for every square, you have to decide which values you give, okay? The values in this particular case are going to be between you know, if the square is of size 11 by 11, is going to be 11 square, so 121, okay? So, that's the domain of the variables, and then what you see here are the various constraints, okay? All the rows and the columns and the two diagonals and to sum to the same value T that can easily be pre-computed at the beginning, okay? And then you are forced to make sure that all the numbers, all the slots inside the square are different so you assign different values to every one of the slots. So, that's a statement of the problem, which is easy now. What is of course is the most interesting part is how do you actually, how do you actually do the search? Okay, so one of the things you could do is, you could, you know, select one of these squares. Okay, this one looks nice, okay? Well let's start there. And you could decide, oh I'm going to assign a value to that possible variable there. Okay, but essentially when you look at this thing, right, so this is the big square, right, you are going to take this variable and assign it a value, okay? But this is essentially completely random at this point, right? So you have absolutely no clue what you're doing, right? So, you're going to take a particular variable, take a value, but it's, you know, it's a completely random guess. And in addition to being very random guess, it's going to be a very strong commitment. You're basically saying, I want that particular variable to be that value, okay? So can we do something which is like a weaker commitment, okay. And that's what we're going to do. So, domain splitting is basically you're going to select a variable, and instead of assigning a particular value, you're going to say ooh, wait a minute, right? So, I don't want to make a big decision here, right? So, what I'm going to say is that I'm going to you know, see if I can actually find a solution if I assign you know, a value which is in the upper half of my domain or the bottom half of my domain. Okay, so you split the domain in two, and you say, okay, so I'm going to try to place this particular value, that this particle, I'm going to basically assume that that variable is in the upper domain or the lower domain of, of, of its actual domain. Okay, and this is what we can do. And this is a search procedure expressing you that. Once again you are going to, you are going to loop until you assign all the variables, okay? At every one you select a variable using the first [UNKNOWN] principle, so a variable which is very tough to actually assign, and what this is doing here, here is not assigning a popular value to that variable. What you do is you take the midpoint in the domain. That's the mid value that you see there, okay? And then you basically say, oh, the variable has to be smaller than the mid value, or greater than the mid value. So the choice that you do here, okay, is much weaker. You are basically assuming that the variable is inside a subtle value. But you haven't specified which one. So it's a much weaker commitment, and since we have absolutely no clue in this, no clue in this particular problem, what to do, this is going to be a very effective strategy in this particular example, okay? So you're going to say oh yeah, but this is a puzzle. Now this strategy, is actually extremely good For very hard car sequencing problems. So remember we showed that before a couple of lectures ago. So you cars on an assembly line. Every one of these beautiful cars okay, is basically requiring some options you know, a moon roof or leather seats and things like this Now to actually prune these options on the cars you have these production units, which are basically putting these thing as the car is moving in front of the production unit, and therefor you have to be careful. You have to sequence the, the car in such a way that you have the time to actually put the various options on every one as the car is moving in front of the production unit, okay? So we add the first time I've shown you that. Essentially a simple, variable value strategy, okay? Which for a lot of instances is actually working pretty nicely. But on some of the very hard instances, and some of the instances which are actually invisible, it's not the best strategy that you could use. And one of the things that you have to recognize here is that the options that you see here, okay? They have different strengths, some of them are really tight. Okay, so lets say the first two here are really tight. There is essentially no slack. It is very difficult to insert a new car. With that popular option. And when you look at the some of the, the other options that you see there, okay? Especially, the fourth option, for instance, it's a very, you know, loose option in a sense, there are many ways you could actually place all the cars, there are plenty of areas where you see essentially no cars being placed. Okay, so in a sense when you are trying to solve these problems you know what you want to do, and this is once again the first real principle, is focus on the options that are really really difficult, okay. But once again, you don't really care about the various types of cars. What you really care about is you know, do I you know, do I place a car in this particular slot, requiring that options or not, okay? So, what you want is not reasoning about the different types of car, you want to reason about the various options, okay? And you want to focus first on the options that are very difficult. And then you decide you know if you place a car requesting that option, okay? In that particular site but you are not actually placing car you are saying aw there will be a car in that particular option but I don't want to commit to which car at this point. Okay, and this is the key idea that you are focusing on all the options and for the option that are really difficult. And so in a sense, the way to do this is, is, is very natural. Okay, so what you do, is that you do a search procedure which iterates over the options. We are not iterating over the various types of count. We are looking at the various options, and then for every line of the assembly, every slot of the assembly line, we are deciding if that particular slot in the assembly line is taking the option, does the first That's the first that's, that's the first choice that you can make there or it's not taking the option. Okay, so why does it work? Because you look at every one of the options, and if that for every one of the slot in the assembly line, you're going to decide do I think that option is enough, okay? Not assigning the car, but then you take the next option, you do the same thing. And so at the end of the day what we are going to do, is for every one of these things, you are going to choose very specific configuration because essentially the other constraints are forcing you to choose between which, which they are basically forcing the type of car you have to produce. Okay, so very interesting here. What you do is essentially domain splitting. Every time you make a choice here, you are basically splitting for the particle of slot variable, the set of cars in two parts. The one that they are requiring the options, or the one not requiring the options, okay? So then you choose first to assigne cars for the options, and then the car not taking the options. Okay, so essentially, this is once again a domain splitting. You have a mutual commitment. The only thing you are doing is deciding whether you add that option for that particular slot or not. Okay, very effective on some of the most difficult car sequencing instances, especially when you want to prove infeasibility, okay? So, so far we have seen a lot of different things, okay? Variable/value symmetry. Value/variable symmetry, okay? We have seen that we can use a first weighted principle by using physical linking formation, and sometime using the, the objective function. And we have seen that in some instances, okay, we, we wanted a weaker commitment and new domain splitting What I want to do now is come back to, you know I promised you that, come back to symmetry breaking and look at how we can actually break symmetry breaking, not by using constraints, but during the search, okay? You will see why this is important, okay? And we going to go back to this scene allocation problem, right? So these beautiful people, you know, Georges, and Julia, and Clyde. You know, I like Clive a lot, so you do it, it was almost James Bond. Or maybe that was just a marketing, you know, ploy that he had. But he would have been really great James Bond. Anyway, Dan Craig is a great James Bond too. But anyway, so I'm getting ahead of myself here. So what we are trying to do is shoot these beautiful movies, okay. And the actor plays in different scenes, and remember, they were paid by the scene that they They play with. And they were not, you know, paid by the scene they played with, they were paid by the number of days that they were on the set, okay? And we had constraints on the number of scenes that you can...that you can shoot every day. So you can shoot at most k scenes every day And the objective was obviously to minimize the cost, and one way to do that is make sure that the actors when they spend a day on the cast are basically shooting as many scenes as possible. Note there were a lot of symmetries on this particular product. Do you remember? Okay, so the symmetries were about the various days, right? So, The days, at the beginning, were all interchangeable, Monday and Tuesday, they were no difference for these actors, okay? So the way we eliminated those symmetries by putting constraints, okay? So the first scene that we wanted to assign, okay? The things that we said was that, you know, it was day one. It could be only assigned to day one, because at that point, all the days were the same. For the second scene we were considering, we were basically saying okay, that scene can be assigned to day one, that's where scene one has been allocated. Or a new day, which is basically day two because all the other days are the same, at this point, are essentially [UNKNOWN]. And so in a general fashion, when you look at saying I, you were basically looking at the day that were assigned before, plus a new day. And that's what this beautiful formula was telling you. And so what we did was, you know, doing this nice model, and then you have the symmetry breaking constraints where, you are basically saying that scene 1 is allocated to 1, and then all the other scenes were allocating to the values assigned to the previous scene plus a new one. Okay, and so you were basically, what we were doing, what basically putting all these constraints Inside the model, okay? So there are symmetry breaking constraints. They were getting rid of the symmetries in the popular instant, in the popular problem. And, and, and, and, and these symmetries were basically taken care of by putting these additional constraints, okay? Now, when you think about this and you think about search. These constraints have the dramatic effect on search, right? So if you use the first [INAUDIBLE] principle, what's going to happen, okay? Essentially, these constraints are going to dictate the, mostly the way you are basically doing search, why? Because the first scene is already allocating, there is no choice. Then you look at the second scene, which is in the positive order in which we stated the problem, right? So, that 2nd scene is the domain of 2. The 3rd scene, as the most domain of 3. The, the 4th scene most a domain of 4. So essentially, from a, when you use the first stated principal, you are basically, by stating these constraints, you are basically choosing the order in which you have to assign the variable. Is that good? Well sometimes yes, sometimes no. But in this particularly case, it essentially prevents you from using any kind of sophisticated characteristic because it's basically you know, you're basically constrained by this, this, this constraint that I'm basically reusing the domain of the variable. So can we avoid it? So there is an interferance between the symmetry breaking constraints and the search heuristic that you could use. If you wanted for instance to use a heuristic that was using the first principal, the smallest domain and they save the [UNKNOWN] most expensive ones first, you are not doing that. Because essentially these symmetry you know these symmetry breaking constraints were imposing a particular order. So can we actually get rid of this and the, the answer is yes. And what we have to do is take the symmetry breaking constraints and not impose them in the modern but kind of introduce them dynamically during the search. So we're going to impose essentially the same, same symmetry breaking constraints. But dynamically during the search. Okay, so in a sense what we the big difference between imposing them inside the model and imposing them doing the search is that the ordering is going to be different and its going to be discovered incrementally by looking at the variables which are the most difficult to assign. Okay, so, so in a sense what we're going to do. The, the search heuristic is going to be the search heuristic is going to be, you know, choosing the next scene and that next scene will take the one which is the smallest domain between [UNKNOWN] the first fail principle and in case of time we'll take the most expensive scene. What, why would, would we do that? Because those [UNKNOWN] if, if they are many of these actors that are very expensive, we want to start with these scenes because essentially, you know, that will give us a, that will increase the directly the value of the objective function. If we place that particular thing and some of the actors, you know this is a new day for them or no, this is not a new day for them. That will have a dramatic effect on the objective function. So the heuristic is going to take the scenes which have the smallest domain and in case of ties we're going to break that by looking at the scene which is expansive, which basically means, you know, the scene which contains a lot of actors whose fees are very high, okay? So, now essentially we have to choose what we are going to do, so we have to break the symmetries during the search. So when we take it, when we take a scene like this, we're left to decide which days we will consider for that particular scene. And, once again, we're going to do exactly the same trick as we did for the static constraint. We're going to take the existing days plus one, a new one, okay? But now, we are not imposing these constraints inside the model, right? So we are imposing them during the search, okay? So when we label the scene with the only values we will consider for that particular scene, so the values of the days that we have used before, plus one, okay? And the advantages here is that you essentially break the same symmetries. You break the same symmetries, you break, you sometimes, you use the constraints a little bit later, but they don't interfere with the search heuristic at this point. They don't change your euristic by simply by putting by putting these constraint dynamically during the search, you don't change the euristic. Okay, so this is what you can do here. This is essentially the search procedure expressing that. So what you see here is that when you try the value for the particular variable you take the exitsing data to compute it above there. Okay, that's the days you have already used. And then you take a new one, okay? So, that's how you're going to break the symmetries there. You don't consider all the possible value in the domain of the variables. The only thing that you do is you take the existing days plus a new one. That's the only value that you select for that [INAUDIBLE]. Of course, what you see on top of there is basically selecting the, the minimum value. the minimum value, the, what you do there is select sine, which is the smallest domain, and then in case of [UNKNOWN] the most expansive, okay? So, that, you see a basically a dynamic coloring there, choosing the one which is the smallest domain and this is not actually influenced or impacted. By the Symmetry Breaking constraint and then the one and in case of tie the one that is the most expensive. Okay, so once again this is the essentially the same Symmetry Breaking ID, the difference is that we don't impose any static in the model what we do is we actually introduce this constraint dynamically during the search by limiting the set of values that we consider for everyone of the variables. Okay, so this is the, the, the last technique though that I want to talk about, which is randomization and restarts. Okay, so we'll come back to this when we talk about large number root search, which is the most sophisticated use of this. But what I'm going to talk about now is very simple, but it can be very powerful for some example, okay? And so, the basic key intuition here is that sometimes there is no obvious search ordering, but the structure of the problem is such that there is one. We just don't know which one it is, okay? Alright, so this kind of interesting problems where there is a good ordering but it's very difficult to find it. So, what do you do when you are in a situation like that? You know that there is a good ordering, but you don't know which one. We, you don't know where it is. So what we going to have to use is brute force, right? Completely stupid. What we are going to do, is we going to randomize, okay? We going to randomly generate it some ordering. Hopefully we'll, we'll try to find it good ones. And then if this doesn't work, if we can't find the solution in a reasonable time, we're just going to restart, generate another ordering, and try, and try, and try to see if we can find solution with that ordering, okay? So, the key idea is that we try, you know, we try something, if it doesn't work, we stop early, right? So we say ooh this is looking really bad and you try another ordering and we try to see if we can do better with that ordering, okay? So in a sense the key idea is to try a variety of random ordering. We execute the search with those ordering. If it doesn't work after a, after a certain time limit or a number limits on the number of failures. You restart the search and you see if we have another ordering you can do better, okay? So this is very useful for this magic square problem for instance. So when you so, look at this thing, I told you before, we can assign a value to a variable we also in no clue what we are doing. Even when we do domain splitting, we basically have no clue what we are doing. But on this particular problem, sometimes you have good orderings that aren't going to make a big difference, okay? So where do we start? We don't know, so what we're going to do is we basically going to randomize okay? So instead of choosing essentially the variable which has the smallest domain, okay, we're going to select let's say, one of the tree of best variables, one of the tree variable we should have a smallest domain. We just randomize the search a little bit, we don't commit to the variable which has the smallest domain. And then we're going to limit the amount of time we spend, and if we exhaust the time limit we're just going to basically restart the search, possibly by increasing the time limit so that we Improve the, you know, the chance of you actually finding a solution. And this is the only thing that you have to do, okay? To do that, so what you see you know, in shadow gray over there, are basically you know, the search procedures that I've shown you before. And we are making very, very few changes. One of the changes that you see there is that you are randomizing. Instead of selecting the variable with the smallest domain, we are selecting one of the three variables, which have the smallest domain you know? And then essentially we have these repeat loop which is basically restarting this search. Okay, and we are making sure that we can only search for a certain time limit. Okay, and if we fail, you know, finding a solution, when we restart, we increase the time limit. That's all we have to do for actually implementing this, okay? So what we do, basically we do the search here, you know, it's randomized, so we're going to pick up the variable ordering in a random fashion. If you find the solution great. Okay, if we don't after a certain time we restart. We increase the time limit. We re execute this procedure. Which basically means that we're going to find another random ordering for this particular variable, okay? And, and we're going to search with that particular random ordering and if you find that solution great. Otherwise we'll redo this thing until we find the partiuclar solution. Okay, so this is kind of brute force, okay? Once again, it's combining all the techniques that we've seen before. We can put anything in there. But on top of this, we are basically introducing this restart and randomization, which can be very powerful for some classes of application. Okay, so at this point we have basically covered all the lectures on constraint programming. The next set of lectures are going to look at local search and look at very, some of the same problems using a different technology. Thank you very much. [BLANK_AUDIO].