After stopping the rain Zhuge Liang needed to satisfy one final requirement for launching a successful fire attack. He needed a strong wind to blow towards Cao Cao's army. In Xubi the wind was currently blowing in Cao Cao's direction towards Eastern Wu. [MUSIC] Zhuge Liang adopted a method from the tower of peace, involving an alter with a tribute, to call for a strong wind to blow in the opposite direction. The altar was three levels high, each level in the shape of a hexagon. Different tributes are put on the vertices of these hexagons and they were of different ranks. [MUSIC] Magic coins are placed on the edges connecting the three levels of the altar, the number of which was determined by the difference in rank between the tributes. According to the book, the calling power was stronger when more magic coins are put in position. [MUSIC] To ensure strong wind, Zhuge Liang wanted to put as many magic coins as possible and he pulled out the tablet to figure out how. [SOUND] >> So as Zhuge Liang has managed to stop the rain but now the wind is blowing in the wrong direction. So, consulting with Dao, Phi sees that by decorating in an altar in a particular way, he can actually hopefully change the wind to be what he wants. So he's going to decorate an altar like this with various tributes. So if we look at it from above, we're going to have these tributes and each of the tributes is of a different rank. We have a number of tributes of each different possible rank. And what he has to do is put down magical coins in between each two tributes, and the number of magical coins between two tributes is their difference in rank. Here, this is rank one and rank five, the difference is four, he needs to put for magical coins in there. With these two, is rank six and rank four, the difference is two and notice it doesn't matter which order. It's the absolute value of the difference that we're worried about and of course if we have two of the same rank then we put no coins. And towards the divine arrangement to get the Gods to answer his prayer for the wind. Then he wants to put them down to maximize the number of coins, so here's an example where there are 27 magic coins placed in the array. And he's trying to get the most possible to make the prayer as strong as possible. So here's our problem, we've got an m level altar containing m concentric regular n-sided polygons. And basically a different tribute has to placed on each of the vertex's of these polygons. And there's these tributes and each of them are divided into m groups, each with a given rank. And between any two corresponding vertices we have to play k magic coins where that's the difference in the ranks of the tributes almost two vertices. So here's the data and decisions basically we've got one variable per vertex to denote which tribute being placed there. So here's a set of vertex n, the rank which is also the same n and number of polygons m and then we have our enumerator type of tributes and they're going to be ordered in rank order. So we're going to have all the ranks ones, then the rank twos, then the ranks threes, and that's what this rank array is giving us. Basically building an array for each tribute what it's rank is and then our critical decisions here, for each polygon on each vertex of the polygon which tribute goes at that position. So our data file we had a six gon and three levels of hexagon and then here is attributes in rank order. So all of the rank one tribute at first and the rank two ones, rank three, etc. All right, we're going to think about constraints, obviously we're going to place a different tribute at each vertex. So, we're just going to use an all_different constraint and we're just going to take this 2D array and coerce it to a 1D array because that's what all_different expects. We're going to want to count the number of coins that we need and so we're basically building up this in coins array. Between adjacent levels and we're going to set it basically as the absolute value of the tributes in polygon I and the tributes in polygon I plus one at that position J. For the different vertex positions around the polygon and what we're trying to do is maximize the total number of coins so we can sum them up and then that's what we're trying to maximize. All right, now we've got to worry about symmetries. This is in the symmetry part of the course and you should see clearly that there's some clear symmetries here. So if we take the three vertices in a line and another three vertices in a line. And we could swap them and we'd still get the solution, right? Because the tributes are designed about what happens in between these two things, if we swap them over here, the same set of tributes apply. So this is a symmetry. We can swap any two of these lines around the polygon and we'll get another symmetric solution and we can do another thing which is we can reverse all of the lines. So, if we reverse this line, so we take the blue in the middle and the purple and change it to the blue on the inside and the purple on the outside, the same thing in the middle. Obviously, you can see that nothing's changed in terms of a number of coins all right. So swapping the inside and outside polygon, for three, is the same as reversing all of these lines. If we had more polygons then the reverse law is a bit more complicated and that's another variable symmetry. So we're going to add some lex leader constraints to do this. So again, there's, we're going to just force that, this each line is lexicographically less than the one after it, all right? So here we're looking at line j and line j plus one and basically requiring this lex less than equal to constraint. So for our example here it's basically the same that this line here is lexicographically less than this line here in terms of the tributes that are placed there. But we should think about this a little bit more because we know something about all of these tributes, they're all different. Which means that the lexicographic constraint only remember looks of the second pair if the first two are equal. Well, they can't be equal, so really this constraint is exactly the same, it's just requiring that the first one here is less than or equal to the first one there. But they can't be equal, so it's just less than. So we can replace this complex less than or equal to lex_lesseq constraints by just simple less thans. We haven't changed the problem because we're making use of the fact that all the tributes are different. And we have to swap the order of the lines and basically the way to do that with a lex least is to take the first half of the line and the second half of the line in reverse order. And we make sure that the first half of the line is lexicographically less than the second half in reverse order. You can see it's in reverse order because we're iterating through this order, the opposite way. So that's really just a simplification of saying that the order if I take it the whole thing and flip it will be the same. And what we've talked about in the previous lecture how we can simplify lex less than or equal tos. So for look at that example here we're basically looking at the inside row to be before the outside row. But again because we now they're all different then simplifies in fact just to a single less than constraint that the first thing in the first row is less than the first thing in the m-th row. We know the difference so that any other comparison will never happen. Right, so we solve this model and we managed to find a solution with 12 coins after 10 minutes of solving. We find a solution with 23 coins after 20 minutes of solving. So, things aren't going that well even though we've done a lot of symmetry breaking, so what's missing? Well, we're missing a whole class of other symmetries. So up to know we've been talking about variable symmetries, where we had to bijection on the variables that present solutions. We also want to think about value symmetries, so know, if we take a solution, we're going to permute where the values go. In a consistent way and this will also give a solution. Now, we've seen examples of value symmetry all ready in the catapult problem, the names of the clusters were irrelevant. So they were basically all symmetric, and in the table setting problem, the numbers of the table were irrelevant. So, we've all ready seen a bit of value symmetry breaking but we'll see the different way here. So the value symmetry is now problem arise because all the tributes with the same ranks are interchangeable, if I tribute of rank three, and replace it with another one in rank three. Obviously the number of coins doesn't change because it only depends on the rank and still a solution because we just swapped to old different. So now we have to step back a little and think, so when we break symmetries, multiple symmetries we have to be careful. That we live at least one solution of it's symmetry class behind. So when were using lex leader what we're trying to do there is always leave the lex least solution behind. And if we do that, we're going to make sure that at least one solution in each symmetry class is left, so that's what we've done so far. Note that if we changed the way we solve the reversal symmetry of the polygons to this one, right? So, we just said that the tribute one in polygon one is greater than tribute one polygon in. Then we wouldn't leave the lex least solution behind and maybe we could remove all possible solutions. So we have to be very careful when breaking symmetries. It's going to be even more problematic when we're combining variable symmetries and very symmetries as we're about to do. So, value symmetries we can actually map to variable symmetries in the case that we have a permutation problem like we do here. So, tribute placement is a permutation of the numbers one and end by n by m, so that's where it should be placed. So another view on this is to think about, for each tribute, where does it go, so rather than for each position, what tribute goes in it. And we're already seeing this kind of permutations problems before and we know that if we're going to have these two viewpoints on the solution then we need to make them agree. By adding this inverse constraints, so basically saying that tribute position and the position arrays are inversely to each other. We can do that with the global inverse straightforwardly. Once we've done that, we can now think about symmetries, variable symmetries on these position variables. So position i and j are interchangeable if the tributes that are in those that we're talking about, i and j are of the same rank. So if we think of these three positions, which all have rank six and they're at positions 5, 11, and 8. Then we can swap any of these values, 5, 11, 8, around, and we'll still get a solution which is exactly the same. So we've now changed, basically are using these position variables, we can use LexLeader symmetry breaking to solve this value symmetry problem. So the value symmetries and the original viewpoint become variable symmetries in this second viewpoint, the inverse viewpoint. So, we're going to add LexLeader constraints to make sure that interchangeable variables can be simplified. So basically for each rank, all right? We're looking at the first, the position of the first thing of that rank is less than the position of the second thing. The position of the second thing of that rank is less then in equal position to the third thing. And generalized for when we have more than three polygons or more than three in a rank. All right but again so we've now run this and now we actually get a solution. And indeed we get an optimal solution of 42, much bigger than the solution we found without having the value symmetry taken into account. But we could of course go back and use another way of removing value symmetries in the original model. So we already introduced the value precede chain global, which is a global to remove value symmetries directly. And all we need to say is for every rank the we add this value precede chain over the values which are the tributes of that rank. Right and we make sure basically that this is going to do exactly the same constraint solving as the previous example. But here we're just talking about it in the original variable space, and if we solve with this version instead we're going to solve solution much quicker. Basically, the value precedence chain is quite strong and we get the same solution, so value symmetries arise commonly in discrete optimization. In fact, we saw them before we talked about variable symmetries. But one thing we have to be very careful about is once we have multiple symmetries, that they are all compatible. That in every symmetry class, at least one solution is left and the usual way we do that is make sure that the lexicographically least solution is left over. So we have to be careful when we're doing a value symmetries to make sure that the lexicographically least solution was left over which in fact we did. And indeed for permutation problems, value symmetries are variable symmetries just from different viewpoints.
