The Yellow Turban Army were well trained in a special blade move, which allowed them to defeat the government army that were sent to suppress them. To combat the Yellow Turban Army, Liu Bei, Guan Yu, and Zhang Fei's army joined forces with the government army. Liu Bei came up with five sword moves with different powers. The five sword moves require different amounts of time for the soldiers to learn. Liu Bei had limited time to train the soldiers and wanted to maximise the total power of the sword moves being taught. To figure out the best choices of sword moves, Liu Bei took out his magical tablet to call for the help from a mysterious master. Liu Bei, Guan Yu, and Zhang Fei have to train their army. So let's look at the MiniZinc model they use to do that. So first, there's set of moves that they are going to train their army with. And then, there is the time that they have in order to train their army. And for each move, they have power, how good that move is in defeating the Yellow Turban Army and how long it takes to train that move. And then, we have the decisions that we're going to make is which of those moves we're going to train. Now, of course, it only make sense to train those moves between 0 and 1 time. We're not going to train to move twice or 3 times. And we're not going to train to move negative number of times. So, it constraints forcing that we are trained the move 0 or 1 time. And then we have a constraint saying that we can only train a number of moves whose total duration is less than the time bound. So if we sum up all of the moves that we train. So where our current's variable is true is one per sum variable duration is less than the time bound, and then of course what we're trying to do is maximise the power of the moves that we actually trained. So there's our 0-1 Yellow Turban Model. Now if we think about this decision here, we're deciding this occurrence., how many times we train to move, as an integer. But actually that was rather nonsensical. We really only needed to decide whether we're going to train a move 0 or 1 time. So we could replace that by just saying these constraints could be removed and we could say we're going to have this variable between 0 and 1. And then when we do that we could also say, well, what we're really doing is making a decision. True or false. Do we train that move or not? And we can rewrite the model this way, saying okay, the constraint on the duration is the duration times the occurrence, the moves that we do train converting that to 1. If it's true that we do train it and 0 if it's false, that what this bool2int does and simply using the same thing to calculate the total power of the moves that we do train. And this is introducing an important function in MiniZinc called bool2int which basically is defined this way. It converts (false) to 0 and (true) to 1. And indeed many solvers will treat these two things the same, 0-1 integers and Booleans. And indeed you won't see that much of bool2int in using models because if you ever use a boolean where MiniZinc expects an integer, then MiniZinc will automatically add this bool2int function in. So if we go back to our model and we use these boolean variables here, these occurrences which MOVES that we're actually going to train, then you can omit these bool2ints and these brackets around them. And this MiniZinc model will work exactly the same way because, effectively, MiniZinc will insert these bool2int for you. So there’s our model. So what we're doing here is choosing from a set of objects, effectively. A Yellow Turban Rebellion story is basically a typical problem, requiring us to choose a subset of a set of objects that meets some criteria. All right, so we're trying to choose a set of moves which fit within the time bound and it optimizes some objective function. So here we're trying to maximise the power of the moves that we train, and all together, we put those together, in this case we can train three moves to maximise the army that we have. So this is really what we've generated, a possible ways of representing this problem as an array of 0-1 variables. That was how we started off. Or an array of Boolean variables. That was how we finally end it. Or we'll see later on we can use a set variable. So, a set variable allows you to represent or choose a set from a given fixed superset. So we can declare a variable set like this. This variable x here is going to take as a subset of the values of the set 1, 2, 3. So these are the possible set values that the variable x could take. So we can do another version of our model. Instead of using this Boolean version that we ended up with here, we can think about choosing a whole set of which, set of moves, we're going to train. So here we've said okay, occurrence is now the set of moves that we are going to train. We're going to train and that is a decision that we're going to make. And then we have replaced this occur of i which was saying was it true or false that we chose to train that move. By this decision, does this move i occur in the chosen set? i in occur. And otherwise, everything else is the same. So, here we've got a different representation. So now, occur is a set variable and rather than saying, occur of i. where i was before a boolean, saying true and false, did we choose to train it? Now, we're saying, does this i, this particular move occur in the set of chosen moves that we train? So there's another way of building that model, now using a variable set. And we can now do a better version of this, a more natural version, by saying well, where before when we were iterating over all the possible moves and just selecting out those ones which are in the set that we chose, and adding up their duration. Well lets instead just say, well lets sum over all the moves in the set that we chose and their duration, so a much more natural way of writing down the same thing. And we can simply do the same thing for working out the total power of the moves we chose. So here we are iterating over a variable, a decision variable it's writing over, which moves we actually chose, and adding up their duration in here, adding up their power. So you can see that other representations of that model that we did, so the original model, 0..1 Integers, they correspond to the variable set. So the 0, 1 model for the set 1, 2, 3 corresponds to having 1 that we chose the value 1, 1 that we chose the value of 2, and 1 that we chose a value of 3. And similar if we look at the set here. We chose the value 1, we chose the value 2, but we didn't choose the value 3. So these other set representation model this variable set. So MiniZinc provides a lot of set operations and we'll see various of them throughout the course. So we can ask for membership, subset, superset, intersection, union. Cardinality of the sets, set difference which is set of traction, symmetric differences where you take two sets and you keep only the things which are not in their intersection. So, which model is best? So this is a question that will always arise when we're talking about models. So, many solvers will treat the last model when we have the set variables better than other models because it can combine reasoning about the cardinality of the sets with other kinds of set reasoning. So particularly CP solvers can do this. But for many other kinds of solvers, the 0-1 integer version will be just as good as any other version. And indeed, for most any solvers, all of the version that we've shown here will be converted to a 0-1 integer version. So the argument about which model is best was depend upon what solvers are you going to end up using to solve this problem, but I think the highest level version is the last version, which we showed you. The set version and in some sense that can be considered the best model because that's the most natural model to write down, the easiest to understand. And it should really be the job of MiniZinc to translate that to a model which your solver understands best. So in summary, modelling with sets is very common in combinatorial problems. And the Yellow Turban Rebellion story is actually a 0-1 knapsack problem, which is one of the most frequently occurring combinatorial problems and it appears in the real world in lots and lots of places. Knapsack crypto systems is one of the most interesting ones. And there are at least three modelling approaches for looking at this kind of choosing a set problem. Indicator variables which can be 0-1, or Boolean variables and indeed, native set variables.
