With a strong wind, the Sun-Liu Alliance launched a huge fire attack on Cao Cao's army, causing them to lose the war. Left with a very small army, Cao Cao fled from Xubi to Huarong. Anticipating that this would happen, Zhuge Liang arranged 14 generals to guard the roads, with one general for each road. To increase the chances of capturing Cao Cao, generals on two adjacent roads needed to have a good relationship with each other so that they could work well together in their capturing effort. Taking into account the relationships between the generals, Zhuge Liang pulled out the tablet to determine the most appropriate way to allocate the generals to guard the road. >> After Cao Cao's defeat, Liu Bei realizes that he is going to have to enter into Huarong. And he decides to put 14 generals guarding each of the 14 roads into Huarong. Now, these generals each have relationships between each other. Some get along very well and they have a really good person-to-person relationship, and others don't. And this is rating here which is a symmetric matrix showing how any pair of generals interact with each other. That's going to be important for making the best blocking of Cao Cao's army. So rather than use the generals themselves, we're just going to use numbers, because it'll make our model simpler to illustrate. And the idea, what Liu Bei is trying to do, is maximize the cooperation of adjacent generals. Because basically every two adjacent generals are going to have to cooperate about how they block the area between their two roads. And if they get along well then they'll do that well, if they get along badly they'll do that badly. And so this will give us the best chance of capturing Cao Cao and his army. So for example, here is a cooperation of 61 and we're just adding up this 4 cooperation here, 9 plus 4, add those all up we're going to get a cooperation of 61. And what Liu Bei wants to do is of course maximize their cooperation. So, here's our problem. We've got n generals and n roads. There's the cooperativeness array, which is the cooperativeness between general i and general j, we've seen an example of that. And so our model is rather simple, right? So we have n, the number of generals and the number of roads. This cooperativeness array is the one piece of data. And then our decisions are, for each road, which general goes on that road. And then the constraints, fairly simple, it's all different so we want that each general and each road is different. We can't have the same general guarding two roads at once. And then we're just trying to maximize a cooperativeness of the adjacent generals. So we're just summing overall road pairs that are next to each other from i up to n-1, the cooperativeness of the general on this road, road i, with the general on the road after it. And we just kind of maximize that total cooperativeness. So it's a fairly simple model. So, because we are thinking about symmetry, we should understand that there's a symmetry in this problem as well. That if we reverse the order of all the generals, then we're not going to change any cooperativeness, because the set of adjacencies of generals be exactly the same. So you can see it on this small example of four generals, we have these four generals here and we reverse the order. All we do is reverse the order of the cooperativeness, we get the same value solution. So we can add a LexLeader constraint saying that the road array should be less than or equal to the reverse of the road array. But of course, because the generals are all different, we know that these two generals here that we'll compare will never be the same. So we just need that the general on road 1 is less than the general on road n, and that will make sure that'll get rid of the symmetry. So, we can solve our model, we can find an optimal solution in a few minutes. And so, all looks good, but can we improve the model? So, now we're going to introduce a new idea which is the idea of dominance. So let's think about a solution here where we've got all these generals like this, and let's take this sub-sequence from Xi to Xj and flip it. All right, so obviously this is another solution because every general on the road is different, so we haven't changed anything. Really, the only thing that's changed is, so we can look here, that the difference. This is not as good as solution, because these values here, the 5 and 4, which were at the 2 ends of this flipped part, is less than the 13 and the 11 we got after we flipped. And of course, everything in the middle basically stayed the same, we just reversed the order. So the only things that changed, in terms of working out how good these two solutions are, is comparing these 2 numbers here, between r minus 1 and i and j plus 1, with these two numbers here, after we did the flip. So that's why this solution is worse than this one. because everything else stayed the same. So, in this case, we've generated a better solution by flipping these pairs. So we can think about what that is in terms of the model by saying, well what's the value of this here? That's the cooperativeness between Xi minus 1 and Xi, and the value here, which is Xj and Xj plus 1. And that is less than the cooperativeness of Xi minus 1 and Xj, because this is now the general who's next to me. And Xi and Xj plus 1, because now we've moved Xi to be next to that general. So obviously, if that's the case, then this solution is not really one we're interested in, because we know there is a better solution by doing the flip. So what we're going to do is add some constraints to avoid this. So we can do that by just inverting this equation. So we're going to force that the case that if I did the flip, I would get no better a solution, all right. So here is the result before the flip, and here is the result after the flip, and this is going to make sure that I get no better solution by doing the flip. So that, we do not want to allow. So what we've got here is an example of dominance. So dominance is about seeing, if we had this solution and there's a solution, there's always a way of getting a better solution, then that solution is not very interesting. So, we can say a feasible solution dominates another one if it's better in terms of objective function. And so we can say this in two ways, that theta dominates phi, and phi is dominated by theta. And since we're optimizing, we're not interested in dominated solutions, because obviously, there's a better solution for each dominated solution. And so if we can transform a feasible solution into another feasible one that dominates it, then we should disallow this phi. So what we're going to do to do that, is add dominance breaking constraints. So basically we're going to add a dominance breaking constraint that says there's no transformation of a feasible solution which would lead to a better solution. And for our example, guarding the roads to Huarong, this is about reversing the subsequence i to j. Now, actually symmetries are really just a special kind of dominance. So symmetry breaking is ensuring that no transformation leads to a symmetric solution, where a sea of dominance is weaker than that, it's just saying no transformation leads to a better solution. So, we can add the dominance breaking constraints to our model fairly straightforwardly. We're going to look at all ij pairs between 2 and n minus 1 for j. Basically we're going to look at every pair in the middle of this sequence and make sure that this dominance breaking constraint holds. That basically, the original arrangement of the generals would be better than or no worse than if we flipped the ij sequence. That's everything that's going to happen in this array, we're going to start off with i is 2 and j is 3. So we'll look at this pair and we'll extend j to this pair, this pair, this pair, and I will increase the look at this. We'll look at all of these subsequence, so as to make sure that none of them would make the solution better. And if we do that we're going to find a solution quicker, not that much quicker in this example. We'll find exactly the same solution, or at least a solution that is as good, but this is one of these problems where if the problem gets bigger then we get more and more advantage out of these dominance breaking constraints. So dominances are often harder to find than symmetries. We don't have a dominance breaking library because dominance breaking is much more specific to the problem. But when it's available, it can be very, very powerful. So to give you another example in scheduling problems. Often if we have a schedule where there's a gap between the start of one task and the end of another task, then there's going to be no constraints which are forcing this second task to be late. So we can push it back to be next to the end of another task, and so this solution here is dominated by the one where the start time of this task is at the end of another task. And so we can add a dominance breaking constraint which effectively forces the start time of every task to be either at time 0, obviously, which is the first possible task, or at the end of another task. So that's another example of a dominance breaking constraint. So just as for symmetries, we have to be careful about multiple dominance breaking. That we always leave some non-dominated solution. If we have two that disagree, we might actually eliminate all solutions and make the problem unsatisfiable. So in summary, dominance is actually a generalization of symmetry, and they actually when they're available, allow us to reduce our search very effectively, particularly in optimization problems where that really the concept makes sense. But just like in symmetry, there can be overheads. If we add a lot of dominance breaking constraints, maybe the cost of handling all those constraints doesn't pay off in terms of reducing the amount of search. So we have to be aware that dominance breaking may not help us. And the theory of dominance is much less well understood than of symmetry, so it's much more specific to a particular model. And just like with symmetries, we have to be careful when we try to break multiple dominances to make sure that at least one solution is left behind.
