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.