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.