>> The planet launching a fire attack on Cao Cao's army was negatively affected by unexpected and continuous heavy rain. 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. So, let's look at the pattern of lights that he's going to light in a very small example. So, these five parameters to define the problem. So v is the number of rows of the table of lamps that it has to light and b is the number of columns, then r is a number of lamps lit on each row. So, you can see that each row has four lamps lit and k is the number of lamps lit in each column. So, each column has two lamps lit. 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. So, it's very easy model. Now, we run the data file that Zhuge Liang has to solve. And we wait, no solution in ten minutes. So, what's the problem? 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. 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. 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. 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. 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. Now that brings us to a very important discussion, which is that sometimes symmetry breaking is bad. 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.