[MUSIC] Battles between Cao Cao and Yuan Shao's armies were becoming increasingly fierce. Yuan Shao therefore sent two mighty generals, Yan Liang and Wen Chou, to the battlefield. They soon defeated several opposing generals and killed many soldiers in Cao Cao's army. After hearing about this, Guan Yu, along with two other generals in Cao's camp, Zhang Liao and Xu Huang, went to the battlefield to assist. Guan Yu suggested that they could attack Yan Liang and Wen Chou's weak points, causing different damage by targeting different weak points. But the first General they would encounter, Yan Liang, had an impenetrable helmet. So it was meaningless to attack any weak points on his head. While the second general, Wen Chuo, was particularly good at defending his lower body. So the moves for attacking Yan Liang's weak points from his lower body were useless against Wen Chuo. Guan Yu then took out the tablet to decide the best attacking strategy but it gave the wrong solution. And thus, Guan Yu called for help. [SOUND] >> So Guan Yu is sent off by Cao Cao to attack two fearsome generals, and he's got two supporting generals to help him. And they're going to attack Yan Liang first, and then Wen Chou. So, each of the generals have their weak spots. We've seen these weak spots. They're common to all humans. And we have our Damage Matrix. We've seen something similar before. So, Guan Yu when he attacks this position will do 6 damage. And so, these other two supporting generals, not as great combatters as Guan Yu, but they'll do different damages at different places. But we have to be aware that these generals have special abilities. So Yan Liang has an invincible helmet. So any attack in this head position here will do no damage. So it doesn't make any sense, we shouldn't attack the head. Wen Chou has a different skill. He is very good at lower body Kung Fu. So if he sees our attacking generals attack Yan Liang in the lower body, then he'll be able to adjust and defend against any lower body attacks against himself. So basically there's a constraint about attacking his lower body if we have attacked Yan Liang in the lower body beforehand. So let's have a look at our model. We have enumerated type for our heroes that are attacking and the spots that they're attacking. And we have this damage array which we map every hero in the different spots to how much damage they do. And the decisions are, for each hero, whether they attack Yen Liang, that's first position, and whether they attack Wen Chao, that's the second position. And what we're trying to do is maximize the damage, of course, so we're just summing up the damage of the first attack and the damage of the second attack for each hero. So we also have that they have to strike a different position on each general that they're attacking, otherwise they'll get in each other's way. So all the positions for Yan Liang have to be different, and all the positions for Wen Chou have to be different. And we also have that no one strikes the first general's head. So the pos1 can't be equal to BAIHUI. And if they strike the first general low, they must strike the second general high. So if they strike the first general in the low position, that's these two positions, then they must strike the second general in a high position, which is just the difference, any other position. So if we run the model, we get this answer. So certainly we're attacking different positions, each of them. But there's something very odd going on here. We're attacking the first general in the head position, and no one was meant to strike them in the head position. We added a constraint to make sure that didn't happen. So what's going on? So of course, there's a problem with our model, and this is a skill that we need to learn to be able to correctly model, is to be able to debug models. And there's many things that could go wrong, but here there's the most common kinds of things. We have too many solutions so we get a superoptimal answers. So here is an example of too many solutions. We've actually got back an answer which shouldn't be a solution. So we're actually getting a better amount of damage than is possible. We could also get missing solutions and then we get a suboptimal answer. We miss out on the best possible solution or, even worse, no solutions. And that's possibly the worst thing can happen, you run your model, it sits here for a long time, and nothing happens. But here we got the easier case, which is too many solutions. So there's a problem in our model that's allowing solutions which don't satisfy the desired constraints. So we desire some constraint to hold but what we've written in our model doesn't actually do that. There's another possibility for too many solutions and that is where the problem has lots and lots of solutions that are not very interesting. And we'll talk about how to fix that problem in a little bit later. So, what do we do with too many solutions? Well basically, we've got to look at the constraint definition which we expected to remove the solution we've got back, the one which we didn't expect, examine that definition and fix it. So the nice thing is we basically have a solution which is pointing us at something going wrong in our model. If we understand why that solution shouldn't be a solution, then we should understand which constraint removes that solution from the problem. So let's look. This is clearly the constraint which is meant to get rid of the first general being attacked in the head, right? So what's wrong with this constraint? Well, we have to remember precedence of operators. So when we write down this expression here, what we've written down is this. The and binds tighter than the implication and so we've actually said, if both of these conditions hold, then we should attack the second general in the higher position. So we've basically, we have not written down what we were trying to write down, which was this. So this says two things. Don't attack the first general in the head. And if you attack the first general in a low position, then you should attack the second general in a high position. So here we need to add these explicit brackets to make sure we got the meaning that we expected, all right. So that would fix our model. So just going back to the other problem where we have too many solutions but they were all correct. So it's not that we've got something error in our model in terms of we have got a constraint which doesn't do what we think it does. But we just have a problem which has way too many solutions. An example is this, we take an array[1..10] of var 1..10 and just say solve satisfy, well there's 10 to the 10 solutions. If you ask for all solutions, you're really going to see too much. So usually we want to do this by reducing the amount of solutions that there are. And one way of doing this is the saying, well, it's a variable symmetry let's say, so each of these variables really acts the same in this model which has no constraints, so that's pretty obvious. And this will get rid of a lot of the solutions, so we'll only see very few of them. Or another way is to add an objective function. Just to pick one out the very, very many solutions. So let's minimize the sum of the a's and then we'll just get one possible solution. So we can think about a sensible objective function, or any objective function, just to get rid of all those solutions if we don't really care which one we get. In summary, too many solutions is a very common problem when modeling and usually it's this case that what you've written down in your model doesn't actually capture the constraint of the problem. And what the idea is you should look the solution of the model is returning and it's not meant to be a solution, find the constraint that should remove that erroneous solution and fix them. So the nice thing about this case is really the solution we get back is basically a guide of where the error is in our model. So as long as we can work out what constraints should remove that solution, we can go directly to where the error is in our model and fix it. Less common is this, the model having too many correct solutions. And basically the simple thing is don't ask for all solutions. Just ask for one. Or add some constraints to select only some of these solutions, or add an objective.