0:01

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.

Â