0:11

Learning from a book named the Tao of Peace,

Â Zhuge Liang had to light up a special kind of lamp formation.

Â The lamp from the big dipper to stop the rain.

Â The lamps are positioned in a grid and

Â only a limited amount could be lit up according to five parameters.

Â Concerning, one, the number of lamps positioned in each row.

Â Two, the number of lamps positioned in each column.

Â Three, the number of lamps needed to light up in each row.

Â Four, the number of lamps needed to light up in each column and

Â five, the number of commonly lit up lamps in two rows.

Â Zhuge Liang found it challenging to work out which lamps to light up.

Â He turned to the magical tablet for some help.

Â [MUSIC]

Â >> So Zhuge Liang consulting the Tao of Peace decided that in order to stop

Â the rain,

Â he's going to need to light the lamps of the big dipper in a particular pattern.

Â 1:42

And finally, lambda is the number of columns which two rows have

Â a lamp lit in common.

Â So here, you can see in these two rows,

Â these two rows have these two lamps lit in common.

Â In these two rows, they have these two lamps lit in common and

Â you have to look at all pairs of rows not just the ones that are adjacent.

Â These two have these two lit in common.

Â So, this was a solution for

Â a small version of this Tao of Peace solution to stopping the rain.

Â But in fact,

Â Zhuge Liang's going to have to solve this one to stop the rain which he needs.

Â So that's our problem, we need to light lamps in this v by b matrix.

Â Each row has exactly r lit lamps.

Â Each column has exactly k lit lamps and between any two

Â distinct rows, the number of rows in common is lambda.

Â So, it's a fairly simple model.

Â In terms of data, we've just got this v, b, r, k and lambda.

Â We're just defining the rows and columns using those and

Â then our decisions are straightforward.

Â Basically, we've got this table full of lamps and we've got a Boolean for

Â each lamp.

Â Is it lit or not?

Â Now, we want the constraints.

Â Again, they're fairly straight forward.

Â For every row, we add up the number of lamps lit in that row.

Â It has to be r.

Â For every column, we add up the number of lamps lit in that column and

Â it has to be k.

Â And then for every pair of rows, i1, i2 and then we just sum up the number of

Â positions, j where they both have the lamp lit and that has to be equal to lambda.

Â 3:30

So, the problem is there's too many symmetries in this problem.

Â So, let's think about what's happening in this matrix problem.

Â So, this is a problem where the answer is a matrix of Booleans.

Â We can take any two rows and we'll get another solutions over.

Â I have a solution here and I swapped these two rows and

Â this will be another solution, you can see that straightforwardly.

Â Obviously, the number of lamps lit in each row will still be the same.

Â The number of lamps lit in each column will still be the same and

Â the number of lamps in common in any two rows will still be the same,

Â because the rows haven't changed.

Â Similarly, we can interchange columns.

Â So if I interchange two columns here, then again,

Â the number of lamps lit in each row will still be the same.

Â The number of lamps lit in each column will still be the same and

Â the number of lamps in common in each two rows will still be the same, as well.

Â So worse than that, we can compose these symmetries.

Â So I can do a column flip and then a row flip and I'll still get another

Â symmetric solution, which will still satisfy all the constraints.

Â And I can take that solution and do another column flip, another row flip and

Â I'll still get another solution.

Â And so the problem is if we're going to use our LexLeader Symmetry Breaking

Â constraint, we need to add one LexLeader constraint per symmetry.

Â So, let's look at how big that is for this tiny example of two rows and

Â three columns.

Â So the first one here is as vacuous of no flipping, but we leave it in,

Â because it'll show you the total number correctly and then the first three

Â of these LexLeader constraints we generate are from flipping two columns.

Â So here, we flipped the second column and the third column that gives you this.

Â And obviously, we need the original order to be lex less than that.

Â This is flipping the first two columns.

Â This is flipping the first and the third column.

Â The fifth and the sixth row are talking about flipping three columns at once.

Â So, we flip three columns around that gives us these other two ways of doing

Â that and then this second set of LexLeader constraint we haven't looked at so far.

Â First, do a row swap and then do the same thing as what happened over here.

Â And that gives you all 12 possible ways of permutations, basically,

Â of taking this matrix and flipping rows and columns.

Â 5:49

So the problem with this is, it's n factorial,

Â m factorial symmetries for an n by m matrix.

Â And if we wanted to add a LexLeader constraint to our problem for

Â each of these possible symmetries, we'd basically adding n factorial,

Â m factorial LexLeader constraints.

Â I guess we can ignore the first one.

Â So we can subtract one, but that's too many constraints to add and

Â it's too many constraints to handle.

Â It's going to make our solver go much, much slower.

Â So, what we're going to have to do is partial symmetry breaking.

Â We're going to choose only a subset of those symmetries to break.

Â So, let's pick these three.

Â Number two, number three and number seven and

Â we'll see why we pick those three in particular in a little while.

Â Now, one thing we can do with LexLeader constraints is we can simplify them.

Â So, if we take the second line here and think about this comparison.

Â If we're comparing ABCDEF with ACBDFE, well,

Â those two As will definitely be the same.

Â So if we throw away A that A, it's going to be the same comparison.

Â And similarly, if we get down to comparing these Ds they're in the same position, so

Â that'll definitely be the same so we can throw away those.

Â And so this comparison here is the same as this comparison BCEF,

Â CBFE and we can do some further simplifications.

Â Because remember, if these two things, if one is lex less than the other,

Â then we're only interested in the second position if the first two are equal.

Â Well, if the first two are equal than B equals C.

Â And so, we know the result for the second position C equals B.

Â And so, we can just ignore it.

Â So basically, we can take this rule if XY is less than YX and

Â it's the same as writing X less than equal to Y.

Â So, we can take each of these pairs and simplify them to a single thing.

Â So we end up with this comparison, which is a smaller version.

Â And if we go back to our three that we chose, we end up with basically these

Â three simplified forms of the symmetry breaking constraint.

Â Now we have to be aware that we've given up something,

Â we're not going to break all symmetries.

Â So if we look at this solution here 011100,

Â then it satisfies all of these solution symmetry breaking constraints.

Â So, 011 is less than equal to 100.

Â 10 is less than 10, that's this one here.

Â And 01 is listing for 10, which is that one here.

Â So it satisfies all those constraints, but

Â it doesn't satisfy all of the symmetry breaking, all of the symmetries we have.

Â Because If we take this FEDCBA which was another one, then it's actually not.

Â This gives us a lower value.

Â So, we've given up something.

Â We're only doing partial symmetry breaking, so

Â we're not getting rid of all symmetric solutions.

Â 8:28

So, what we've actually done here is picked these symmetries.

Â We've required that adjacent rows are in lexicographic order.

Â Of course, we only had two rows.

Â So, that was the first one that we looked at and

Â adjacent columns are in lexicographic order.

Â And when you see now these constraints here, you can see very clearly that,

Â that's what they do.

Â This is adjacent rows.

Â This is the second column and the third column, and this is the first column, and

Â the second column.

Â So, that's what we call DoubleLex.

Â So, we're only looking at adjacent rows and adjacent columns.

Â That gets rid of lots of lots of symmetries and

Â leaves us only effectively n plus m rather than n factorial m factorial.

Â 9:07

So we can add that symmetry break to our model, straightforwardly.

Â So here, we're just looking at a pair of rows.

Â Row i and row i plus 1 and requiring that row i is lex less than row i plus 1.

Â And similarly here, we look at column j and column j plus 1 and

Â require that lex less constraint and we can do that now.

Â Since this is a common thing to do with matrix symmetry problem,

Â then there's a global constrain in the symmetry library called double_lex,

Â which does exactly this.

Â So instead of doing this, we can just use the double_lex global constraint.

Â 9:43

Now it doesn't break all of our v factorial times b factorial symmetries,

Â but it breaks a lot of them and it doesn't take that much space.

Â So with the same data file as before, we now can get a solution in seven seconds.

Â So, that's a big improvement over ten minutes.

Â And so here is the solution or we think of it as zero,

Â once it's another way of thinking about it.

Â So, what we've looked at here is matrix problems and

Â there are quite a lot of problems that fall under this form.

Â When the answer is a 2D matrix of values and we can often have row, and

Â column symmetries where we can swap rows, and swap columns, and

Â still get a solution, and it's way too expensive to break all of them.

Â So, we can use this double_lex global constraint.

Â It's efficient and it breaks many of the symmetries not all of them.

Â And actually, the problem we've looked at here is called the Balanced Incomplete

Â Block Design problem and it's actually an important problem in experiment design.

Â 10:47

Symmetry breaking can drastically reduce the search space, but you're adding

Â symmetry breaking constraints and they slow down the computation.

Â And so especially in the case where we only want one solution as in

Â the example here, then so we might be way slower with symmetry breaking and

Â we have to be aware of that.

Â So in these problems where we're looking for one solution,

Â the really important thing is the search strategy.

Â If the search strategy will quickly drive us towards the solution,

Â then it doesn't matter how big the search space is and we'll be fine.

Â And what symmetry breaking is doing is reducing the search space,

Â but that would be an overhead if actually we can find a solution quickly,

Â even in that big search space.

Â So, we'll look later on in this course about search strategies and

Â how we can use that help us solve problems.

Â