Cao Cao defeated Yuan Shao in the Guandu battle. Liu Bei, Guan Yu, and Zhang Fei, who were previously in Yuan Shao's camp, had to move to the Jing Province, whose ruler was Liu Biao, one of Liu Bei's relatives. Liu Biao welcomed them and left them a portion of his army. He ordered Liu Bei to be in charge of the administration of the city, Xinye, the outpost of the Jing province. Lie Bei, Guan Yu and Zhang Fei would lead one army unit each. The army unit consisted of cavalry, archers and infantry soldiers. For each army unit, there was a leading team of six, in which there were at least two cavalrymen, one archer, and two infantry soldiers. The brothers planned to divide 18 elitely qualified soldiers into 3 leading teams for their army units. Each soldier had their own evaluation rating, so Liu Bei wanted to come up with a plan to form leading teams with the highest evaluation ratings. This was something he could determine using the magical tablet. >> Our three heroes have to prepare to defend Jing Province from Cao Cao. Now in order to do that, they're each going to lead an army unit, and in that army unit, they're going to need leaders for the individual subunits. So there's archers, cavalry, and infantry units that are going to be part of each of their armies. And so what they're going to do is pick from the elite soldiers that they have around to be the team leaders, basically, for the various subunits in each of their armies. So they're going to have to select one archery team leader, two cavalry team leaders, two infantry team leaders, and a reserve team leader, which could be of any type. So that's basically the team leaders they have to select for each of their armies. Now each of the heroes judges each of these elite soldiers differently. So here are how good Liu Bei judges each of these soldiers to be, in terms of their ability. But, for example, Guan Yu judges the 20 elite soldiers differently, he gives them a different value. And Zhang Fei also gives them different values. So our problem is, for each of our three heroes, we're going to select this team of team leaders, so six men overall of the right types. And we're trying to maximize the total perceived value, so Liu Bei's going to maximize the best value he can get. Guan Yu and Zhang Fei the same, maximize the total perceived value of the team leaders to get the best possible army. So let's look at the data and decisions we need to make here. So we've got a enumerator type which is giving us all the elite soldiers. And then we're going to split those up into archery, cavalry and infantry soldiers. And then for each elite soldier, there's the value that Liu Bei gives to that soldier, the value that Guan Yu gives to that soldier, and the value that Zhang Fei gives to that soldier. And the decisions we have to make is basically for each of these three armies, we're going to select a set of elite soldiers which are going to be their team leaders. So we're just naming that by the hero's name. Okay, of course, we have to make sure that the armies don't overlap. We can't have one leader being a leader in Liu Bei's army unit as well as in Guan Yu's army unit. So we're using the all_disjoint global constraint which is going to allow us to do that. It's just going to force that each of these sets, none of them overlap. And then we're going to have to write down the army formation constraints. So Liu Bei needs at least one archer leader. He can have two because the reserve leader could be an archer leader. He needs at least two cavalry leaders. He could have three. And he needs at least two infantry leaders. And we know that he has to pick 16 leaders. So basically, that's going to enforce that the upper bounds on these things are enforced because we get six overall. At least one is an archer, at least two are cavalry, at least two infantry, and then that means the reserve can be anything. And we have to do the same thing for Guan Yu and for Zhang Fei. So that's tedious. So what we're going to introduce is predicates. So when you're building repeatedly a system of constraints of the same form, you really want to be able to ecapsulate it. And predicates allow you to define a complex constraint and reuse it in the model, and in fact reuse it in other models if you want. So they're important part of MiniZinc. So a predicate is a constraint relation whose definition is hidden or elsewhere. So it's analogous to a procedure or a macro and other kinds of languages. And in fact, all the global constraints in MiniZinc are defined as predicates. And they have the default definition in the library, which is how it works that they work with every solver. because it'll use a default definition even if they can't support the real global constraint which is what we prefer. Now our predicate has type var bool. It's just actually giving back a true false value and it can be used anywhere a var bool can be used in your model. Now that's not quite correct and we'll look at more of this later in this section of the course. So let's build a predicate to determine the form of an elite team of leaders. So we want that, if the team, it has at least one archer, and it has at least two cavalrymen, and it has at least two infantrymen, and the size of the team is six. So this is the constraint that we want to apply to each of our sets of team leaders. So the team leaders for Liu Bei, Guan Yu, and Zhang Fei. Of course, remember that what we're writing here is shorthand, because we often leave out the constraint keyword in the slides just for space. So that's what we would actually write. Now what we're trying to do is maximize the sum of the perceived values. And we can look over all of the soldiers in Liu Bei's army and add up their value, all the soldiers in Guan Yu's team leaders, add up their value, and some for Zhang Fei,. And that's going to give us the total objective that we're trying to do and maximize that objective. So here we've introduced a very simple example of a predicate. So we've built a predicate to, instead of having to write down a repeat copy of constraints, we name it, put it in a predicate and just use that predicate once. So obviously, this encapsulation and makes less, copy paste kind of errors, and it makes a more reusable model. So we'll talk a lot more about predicates. But also, to find all the details on predicates you need to look at the reference material.
