Okay guys, welcome back. So, what we have seen in the last couple of lectures are basically many of the tools that are offered by constraint programming. So, what I want to do in the next couple of lectures is actually tell you how you can use these tools to do interesting things, okay? And the first thing today is going to be about symmetries, okay? So a lot of problems in practice of natural symmetry, okay? There are things that are just the same. And therefore you want to actually explore that information to do search in a better fashion. So, essentially you want to bring this symmetry so that you are to get always a smaller search string, okay? So, so what I'm basically saying here is that there are a lot of problems, with a lot of symmetries. Naturally, when you express them, they have these symmetries. And exploring these symmetrical part of the search trees is completely useless. If you have explored one part and then you explore the part which is really symmetrical to it, it's just a waste of time. If there was no solution to that part, there will be no solution to the, to the symmetrical part, okay? So, there are many kinds of symmetries. In these lectures I will basically only talk about two of them, variable symmetries and value symmetries, okay? And the way we're going to break these symmetries in this lecture is using symmetry-breaking constraints. There are other ways to do this, but this is the only one thing that I want to focus, one thing at the time, okay? And so what I'm going to talk about is, oh, you know, we can break variable symmetries and how we can break you know value symmetry. So, once again, right, so this is an introduction. There are thousands of papers on this topic, okay, thousand ways of doing this. But I'll give you an introduction to this technique, okay?. So, we'll start with you know variable symmetries, and I'm going to introduce a very simple example, which is called Balance Incomplete Block Design, BIBDs for, you know, those of us who actually work on this. So, the input is a set of five numbers that probably mean nothing to you, okay? So v, b, r, k, l, okay? Now forget about them, okay. So what we are really looking for is a matrix, okay, 0, 1 matrix that the value in that matrix are going to be 0, 1. So we'll have 0, 1 decision variables, in a sense. And the matrix of size v, v, okay, v rows, v columns, okay. And what we want is that this matrix satisfies three kinds of constraints. The first one is that the number of one on every row, okay, of that matrix, has to be r. The number of one on every column has to be k, okay? And then the scalar product, or every two rows, okay? Has to be exactly l okay? So this is for instance a simple example of a BIBD, okay? So this is a BIBD which has a value 3, 3, 2, 2, 1, okay? 3, 3, 2, 2, 1, okay? So that means that it has three rows, okay, we can see that, you have three columns, okay? And then on every row, you see exactly 1, 1, or, 2, 1, sorry. So that's because you have a 2 over there, 2, 1, okay? And on every column you have also 2, 1, and when you do the Cartesian product of these, of every two rows, you will have exactly, the value of that Cartesian product, that, that, the value of that scalar product, sorry, is going to be exactly 1, okay? Which essentially means that if you do the intersection of these guys, they have only one position where they intersect, okay? So that's, that's what we want to do. We want to find, you know, BIBDs like this, okay? Now this is, so why, why, why, why are we interested in this? And one of the reasons is that this is an example of combinatorial design. There are a lot of people searching for these kinds of things, and what they always have is a lot of symmetry. And I want to show you that on a bigger example after you know, showing you the model, okay? The model is actually very simple, right? We are looking for the matrix of 0, 1 variables, okay? So, essentially the decision variable are going to be n i j, okay, telling you what is the value of position i and j in the matrix. And then, essentially, the constraints are going to be really simple, alright? So, the first set of constraints are going to express the number of ones that you want on every row, then the number of 1's that you want on every column. And then the last constraint is a little bit more sophisticated, is basically computing the scale of product. What you see over there is basically you take the product of MIX and MGX, okay? So, that basically means I take row I and the column X, I take row J and value in column X. You know, I do it all logical and between the two, okay? And that's going to give me a 1 if both of them are 1, okay? And, and essentially what I want is that the sum of all these things in this particular case are going to be equal to l. I put a 1 in this example because that, you know, that was essentially the example that I've shown you before. So this is a bigger BIBD, okay? So this is seven rows, seven column, okay? I want three ones on every column, three ones on every, on every, on every column, three ones on every row. And I want once again that the scalar product be equal to 1, okay? Now this is a beautful solution, but now you're going to see all the symmetries, right? So, if I take, you know, these two rows and I swap them, okay? What do I get? I get another solution to the BIBDs, okay? So essentially, every time I take two of these row and I swap them, I still have a solution. Because essentially, there is nothing distinguishing these rows, okay? The only thing that I said about the rows is that they have to have a certain number of r. And then when I take two of them together, the scalar product should be a value, okay? There is nothing that tells me that row i is different from row j, okay? So essentially, every time I permute them, I have a solution. Plenty of symmetries, right? So now you look at the columns and this is exactly the same. There is nothing specific about column i and column j, right? So I can swap them and then I get another solution, okay? And so that's what, you know, the drawing here is basically showing you, okay? So, in a sense at this point, I told you that, you know, I can swap every column, I can swap every row. And so what I want is to avoid exploring all thse set of configuration. I want to find, you know, you know, solution without exploring them all, okay? Otherwise, I could try a particular route, and then another route, and then I could swap them and try again, and if there are no feasible solution for every two of them, I would essentially explore the search space twice, okay? So how do I break this these variable symmetries? So the the very very nice way of doing that is actually imposing an ordering of the variables, okay? So in this particular case so we are looking at the rows, and we want to make sure that the rows are essentially lexicographically ordered okay? We want the first row to be lexicographically smaller than the second one, and know that the second one is smaller than the third one, which is smaller than the fourth one, and so on, okay? So, I want to impose a lexicographic constraints on the various rows. What does that really mean? Okay? So, look at this thing, okay? So, what you see there is a and b, okay? Which are basically two, you know, two of the rows, okay? And I'm going to say that a is smaller than b, lexicograhically, if it's you know, more significant value is smaller. Than the most significant value of b, okay? So, this is the case in this particular example, okay? I have a 0 and a 1, which basically means that in this particular case, a is smaller than b, okay? But you know, it may be the case that if, if I had a one, it may be the case that these guys are actually the same. And that's you see in the next example here, okay? So, in this particular case, you see that both have a value 1, so I can decide at this point which one is lexicographically smaller than the other one. I move to the next element, and then I see a 1 and a 0, and what that means in this particular case is that a is actually lexicographically greater than b, okay? So, in this particular, so this is essentially what the lexicographical order is telling you. Compared to the first two, if the first, if the, you know, if this guy is three [INAUDIBLE] smaller than the other one, you know that a is smaller than b. If they are equal move to the next digit, if it's smaller or equal okay, it's smaller, if it greater or equal it's greater and so on, and so forth, okay? So that's essentially imposing a lexicographic constraints on these guys, okay? Now, in this particular case, you see these guys, okay? So this is what I, so this is essentially a solution. Now, this solution is not lexicograhically order, why? Because I have a 1 here, and a 0 there. I know that this guy, you know the row two is not lexicographically smaller than row three, okay? So, this is on the other side now, okay? So this is a lexicographically ordered solution. You see that rows, the first row, is lexicographically smaller than the second one, why? Well, look at this number, this is a 1, on top you have a 0, okay? You look at the next row, it's lexicographically greater than the previous one, you have a 0 there, oh you have a 1 and this guy is a 0. And so on and so forth, okay? So this is essentially a solution now which is lexicographically order. And that's what I want to search for, okay? Because I'm removing all the symmetries, okay? Now I can't swap these two guys, okay? Because this is lexicographically greater than that. So, I reduce the search base tremendously, okay? Now in this particular example, okay, so what I want to do as well is actually breaking all sort of column symmetries, okay? And actually, this is an interesting problem, because I can break both the vari, the rows, and the column symmetries at the same time I preserve at least one solution per symmetry group, okay? So that's what you see over there, okay, so you see that this column here, okay, is not lexicographically smaller than this one, okay. So, why because you see, where am I? So you see a 1 over there and a 0 there, okay? So, therefore you have to essentially order them as well. Now, you see there is two column there, and you see that they are lexicographically smaller than each other. Well the, the left most is lexicographically smaller than the right one. Okay, so in a sense what I want is to impose this lexicographic order on the rows and, and impose lexicographically order on the column. And search for the solution satisfying these lexicographic constraints. So essentially the only thing that I have to do in this model okay is basically add you know for every pair of rows, a lexicographically, a lexicographic constraint, okay? So this is a constraint taking all the elements of the row. You know, of 1, of, of row, of row i, and then all the late, all the, all the, all, all the elements of row i plus 1, and I'm basically saying that row i has to be lexicographically smaller than row i plus 1, okay? And of course I'm going to do the same for the next thing, which is row i plus 1, has to be greater, smaller than row i plus 2 and so on and so forth, kay? And I do the same for the column And then essentially I have all the, all the rows and all the columns in a lexicographic order. Now, this lex, you know, constraints, is actually very efficient to implement in practice. You can find feasibility very fast, and you can prune and achieve the optimum pruning very fast. This is one of the interesting global constraints that we have in constraint programming, okay? So, that's basically you know, how we can break variable symmetry. A lot of the techniques for breaking variable symmetries are following a similar pattern, okay? Now I want to move now, to to value symmetries and I want to reintroduce you these beautiful actors. We were missing them, right? and so the problem is going to be different though. Okay, so it's going to be a scene allocation problem, and this time we, we don't care about marrying these guys, what we want is actually making a movie, okay? that's what these actors do for a living, right? And so this movie has a number of scene that it has to to, to shoot. And you know, an actor plays in some scenes and not in some others and things like this. And we have a very strong constraint which is that at most k scene can actually be shot on a particular day, okay? So, you can shoot k scene per day, not more than that, okay? Now every actor is paid by the day, whether he shoots one scene on that day of you know, k scene on that particular day. So as soon as the actor is on set for a particular day you have to pay his fees, and of course various actors have different fees, right, so that's what makes the problem interesting, okay? So the objective is, of course, the producer of this thing, you want to minimize your cost, okay. So you want to essentially to schedule the actors so that they don't spend too much time on the set. And you cluster the scenes in which they appear at the same time. But of course different actors are playing in different scenes so you have this tension, okay. And of course they have different fees. So how do we do that, okay? So I'm going to show you the model in a moment, but before that think about it. You know, what are the symmetries that we have in this problem? Okay? Obviously these actors are different, right? So, you know, you can't tell George Clooney that he's the same as Clive Owen. So it's not going to be the actors. So it's not going to be that. So the scene are going to be different as well. They will have different types of actor. So there is no symmetries on the scene. So what are the symmetries? Okay? So the symmetries are going to be on the days, okay? So essentially the days in which the scenes are going to be shot, okay. So this is the model, let me go over the model so that we can understand the symmetries afterwards. So what you have is a set of scenes, you have a set of days, you have a set of actors. Every actor is going to have a fee, that's how much you pay the actor per day, okay? No we also know that every scene you know we'll have a set of actors, okay? So that's what you see over there, okay? And then we learn also, we've got a computer particular value which is which are the scene in which the actor is actually appearing. This is going to be important, we derive this information from, you know, from the information we have about the scene. And then the recision variables, you see them there, okay? They basically specify for every scene, which is the day, you know, you know, for which, during which the scene is going to, is going to be shot, okay? So, essentially, for every scene, you have to find which day is going to be shot, okay? So, what you have there are two things, the objective function and then the constraints. The constraints is very simple, It's kind of an different constraints. It's the generalization of that is the cardinality constraints. And what it says is that, you know, If you look at the array shot, okay? So what we know about that array is that we want, at most, five in this particular case. So, so, you know every scene, you know, every day we'll be able to shoot essentially five scenes. So, every day, you know, every day, I can choose exactly five scenes. That's what this constraint is actually expressing. Now, once again, this is a very interesting constraints, global constraints and constraint programming. It can be, you know, tests will satisfy, it will be very efficiently and prune optimally. Now, the objective function is also very interesting. What you are doing is that you look at every actor, okay, you look at every day, and if the actor is actually shooting on that day, you would have to pay his fee, okay. So, you see the fee over there. And this expression that you see there, you know, which has the array [UNKNOWN] constraints, is basically looking at all the scene in which the actor is actually playing, and seeing if that scene is actually play on that particular day, okay? So for every day, every actor, you look if the actor is actually playing a scene on that particular day. And if that's the case, you have to pay the fee, okay? So that's essentially the model, okay? And as I told you, in this particular model we have no value symmetries, the days are the same. So in this particular model, I have't told you that Tuesday is different from Wednesday, for this actor, it doesn't matter, okay, Thursday is the same as Monday, okay? So in the sense, if I schedule, if I give a solution, okay? Where you know, with a bunch of scenes which are played on day one, and a bunch of scenes which are played on day two. Oops, you don't see me, right? So then essentially, you can swap these two things, and you still have a solution. So these things are completely inter, interchangeable, okay? So I can't distinguish them, so in a sense now I want to break these symmetries, okay? So I know that if I have a solution any permutation of the day is going to be also a solution, but I don't want to explore it. How am I going to do that? Okay. Now this is the reasoning, okay. So look at the first scene S1, okay? I want to schedule that scene, okay? I have let's say these five days, Monday to Friday. Which day am I going to schedule that scene? Okay, which day do I have to consider? Well, there is only one that I need to consider, right? Okay. So, and this is the first day, let's say day one. Why? Because at that point, all the days are the same, okay? Whether it's Monday or Tuesday or Wednesday, there are no difference between them. So the first thing, I can decide forever, that I'm going to schedule it on day one. It doesn't do anything okay? Now let's look at the second thing, okay? So the second thing, the second, let's, let's, sorry, let's look at the second scene, okay. The second scene, where can I schedule the second scene? well, I can schedule it on the first day, right, it's like the, the scene that I just schedule. And maybe that's interesting because there are a lot of common actors. Or I can decide to schedule it on a day where nothing is scheduled yet, okay, which is let's say day two, day three, day four, day five, okay. So they are essentially, but, but, day two, day three, day four, day five, they are all the same at this point. I can't distinguish them, so essentially the two days that I have to consider are day one and then day two, let's say. Only one of the other days, okay? So I have only two days okay? So in general, okay, so if I look at the particular scene, okay, the only thing that I have to do, is to look at the days in which I have already scheduled something, okay. Those are, those I have to consider, okay, and then I can choose one new day, a day when nothing is scheduled. And so if you do that, you remove all these values symmetries, okay? So, once again this is easy to do. You take the model okay, and what you do is you add these beautiful symmetry constraints here. Okay,so what do they say? They say that the scene one is to be schedules on day one. No brainer right? So we knew that there was you know absolutely no distinction between the various days at that point. And then the other constraints is basically taking all the other scenes and what is it doing? It's basically looking at the days which have been scheduled for the previous variables and then adding a new day, okay? So the new day that you see there, this beautiful plus one there, okay? So that's essentially what you're saying. You're saying that scene one is equal to one, and the next scene. You know let's say scene s, is to be smaller than, or is to be smaller than all the days that have been scheduled before, plus one new day. Okay, and so essentially what you're doing in this model is setting these constraints that are removing all the value symmetries. You will never explore the fact that scene one can actually be scheduled on the second day. You will never explore the fact that you know scene two can be scheduled on the third day, okay? So that's how you can break symmetries. Now this particular technique is very useful in practice. It has one limitation that I will talk about later in class, and that you can actually you know, you can actually remove that limitation by being a little bit clever. But I will come to that later on, okay? That's it.