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.