2:34

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.

Â