Narrator: Cao Cao and Lu Bei successfully led the coalition in several strikes against Dong Zhou's army and persisted with their attacks in order to pursue a complete victory. Dong Zhou sent his best general, Lu Bu, to fight back. Lu Bu was the mightiest warrior at that time and rushed into the battlefield by himself quickly defeating several generals from the coalition. Liu Bei, Guan Yu, and Zhang Fei challenged Lu Bu to fight against them. There were five weak points in Lu Bu's body the brothers could attack causing different damage. The brothers could only attack one weak point each and this needed to be different points, and therefore, wanted to know which weak point they could each attack in order to cause the greatest damage overall. Liu Bei took out his magical tablet to determine the best plan of attack. Presenter: Our three heroes, Liu Bei, Guan Yu, and Zhang Fei have to combat Lu Bu and the way they're going to do this is attacking his weak spots, which are centered around his body. Now, each of them have different abilities so they can do more damage or different kinds of damage to different weak spots and obviously there's some correlation here. So his head will do more damage or each of them will do quite a bit of damage to his head typically. Our problem here is that they'll each attack a different spot. Otherwise, they're going to get in each other's way and so that won't be as effective. The problem is to find the spots they should attack in order to maximize the damage to Lu Bu. The Lu Bu problem actually is the form of a pure assignment problem, where we have three heroes and five spots to attack and we've got to assign to each hero a spot so as to maximize the damage, and of course, none of them can attack the same spot. So this is a pure assignment problem, very we'll studied problem. And indeed, many of the combinatorial problems have the same kind of form. We've got to assign to each object in one set, the domain, a value from another set, the codomain. We can interpret this as defining a function from the domain to the codomain so basically, we're deciding this function from the domain to the codomain or we can think about on a different way as partitioning the set of domain into sets labeled by the codomain. These are two different ways, in some sense, of understanding this building of function. So you can think of it as building this, mapping from domain to codomain, or another way of just looking at these sets, which was sets labeled by the codomain values, which define which domain values fall into that set and those different viewpoints will help us in understanding different kinds of ways of solving the problem. So the function that we are building here could be an injective problem, which will give us an assignment problem, the one we're looking at today or bijective problem. That's where the domain and the codomain are the same or the same size and it'll give us the matching problem, and we'll look at those problems later on in the course. So, in the Lu Bu problem, the domain is the set of heroes and the codomain is the weak spots of Lu Bu. As I said before, what we're going to look at in this case is an assignment problem. Let's look at the MiniZinc model for the LuBu.problem. The data is we've got two enumerated types. We've got the heroes and we've got the spots like an attack, and the essential data is this damage matrix, says for each hero and for each spot, how much damage will we do if that hero attacks that spot? And then, what are the decisions we have to make? Well, that's fairly straightforward. For each hero, we have to decide which spot are we going to attack, which position on the Lu Bu are we going to attack with that hero? What's the objective? Well, the objective is fairly straightforward. What we want to do is for each hero we want to sum up the amount of damage that I do, how much damage should I do? Well, we look up the matrix for that hero and the position that they attacked and look at that much damage, that's the damage that hero did and we sum them up and that will give us the total damage and we're trying to maximize the total damage. Again, notice the way we're using here a decision variable to index into an array. That's one of the nice things about using a higher level modeling language like this where we can use decision variables as indexes to arise. Let's look at the problem constraints. There's only one constraint, which is to make sure that each of our hero attacks a different spot. We can express it this way, that each spot is assigned to at most one hero. We can write that this way, for all of the spots that there are the number of heroes, whose position is assigned to that spot is less and equal to one. That's one way that we could write down this constraint. Alternatively, we can think about it this way each two heroes that we look at, they're assigned different spots to attack so we could write this way. We could say for any two heroes, which are different, we order them so we don't have to look at the pace, every two pace once, the position of h of where hero one attacks is different for the position h2 attacks. These are two different ways of writing down the same constraint so, which is better? The answer is we're not going to choose. In fact, different solvers will actually prefer a different representations. The top representation would be good typically for mixing digital programming solver, and the bottom representation for a constraint programming solver. Instead, what we want to do in a modeling language, a high level modeling language, is record the structure of the problem and let the solver determine the best way it knows how to handle that structure. In modeling these substructures, what we're going to do is use global constraints. The global constraint version that we're going to use is one we've already seen, this is alldifferent (pos). Basically, every hero is assigned a different spot to attack and then the solver can make use of this substructure to solve better. This is an example of a global constraint, which we saw earlier in the course, and we'll see many more. It captures this assignment substructure or, alternatively, it captures the idea of deciding an injective function, and the alldifferent constraint is one of the most important global constraints there are because this assignment substructure is very, very common in combinatorial problems. If we come back to our full model now, we can see the only constraint we have here is this alldifferent (pos) and remember when we are using a global constraint, we typically have to include the library file which defines it and each solver, which makes use of this global constraint will use a different definition of it depending on the solver itself. We put that all together and there's our entire model. The pure assignment problem is very well-studied and indeed, if we wanted to solve a pure assignment problem, there's a specialized faster algorithms using maximal weighted matching, and if you only want to solve the pure assignment problem, you shouldn't use MiniZinc or these kind of models. You should use these specialized algorithms, they're much, much faster. But the world is rarely pure and we only have to add some side constraints and these specialized algorithms will break, and then addling a side constraint to our MiniZinc model would be very simple and indeed, then everything would still work. That's the reason why we want to capture this combinatorial substructure of the pure assignment problem in a way that we can add arbitrary side constraints and still solve the problem. That's one of the powers of having a high level modeling language. We can capture this specialized substructure of the problem. The solvers will make use of that to solve as quickly as they can, but yet we can add extra side constraints so we can still sold even though we didn't have a pure algorithm to solve the perfect problem. Designing a finite function is a very common occurrence in combinatorial problems and deciding an injective function, this is the assignment (sub)problem, is also very, very common. The global constraint alldifferent captures this and this is one of the most commonly used global constraints and we'll see it used in many examples throughout this course. In global constraints. Now, we're going to start talking about them and we'll see many of them throughout the course I give. That's the names of these combinatorial substructures and the point of naming and placing these combinatorial substructures in our models is that then the solvers can then use their best method for solving that particular combinatorial substructure, and each solver will have different ways of handling that combinatorial substructure. As I've said before, there's plenty more global constraints to come.
