To motivate their soldiers, Liu Bei, Guan Yu, and
Zhang Fei decided to treat themselves and their army to a nice feast.
For their own meal, the brothers wanted to have three of their favorite dishes.
Each dish with its own satisfaction rating and plate size.
They needed to determine the number of these three dishes to maximize their
culinary satisfaction without exceeding the table space available.
For the soldiers, five different types of dishes would be served with wider tables.
So, the brothers needed to solve a similar problem.
They pulled out their magical tablet.
[MUSIC]
In order to increase the moral of the army,
our heroes want to organize a banquet for both themselves and the rest of the army.
So in order to do that,
they're going to try to make the most pleasing banquet possible.
So on their own table, they want to fill the table with their three favorite
dishes, which is snake soup, kung pao frogs, and mapo tofu.
But each of these has a satisfaction rating,
how much it's going to make them enjoy the meal.
But each of them has a size as well.
And the table that they're going to put them on has limited capacity.
So basically, they want to put as many of these dishes on the table as they can to
maximize their satisfaction in the meal.
So for this example, if the capacity of the table is 18, then we can see that
what we're really trying to do is solve this simple linear program.
I'm trying to maximize this satisfaction,
which is 29 times the number of snake soup dishes plus
19 times the number of kung pao frogs plus 8 times the number of mapo tofus.
So that's the satisfaction that we're trying to maximize subject to these
capacity constraints.
So basically we have to have those dishes fit onto the table.
But they also have to make a banquet for the rest of army with different dishes,
much cheaper dishes of course since they're going to feed many more people but
a much larger table.
So here we have five different dishes with different satisfaction ratings and sizes.
And so what we want to do is, since this is really the same problem,
is we want to model to be reused with different sized data.
So here we have five dishes.
For the heroes table we have three dishes.
We want to use the same model.
So let's build an minizinc model, which allows us to use differently sized data.
So, here's that model.
We've got an enumerator type telling us which sort of dish we're talking about and
then the capacity of the table.
And we have two arrays here.
So, this is the first time we've seen array declarations.
Basically, associating with each dish a satisfaction rating and
with each dish, a size.
So, there's an array declaration how to clear an array, so
we have one of these satisfaction values for each dish.
Now the important decisions we have to make is how many of each dish,
what amount of each dish, we’re going to put on the table?
And so here is an array declaration of variable integers.
So this is an array for decisions.
So those are the decisions we’re going to make.
And we can look at the rest of the model, we're saying that
the amount of each thing is going to have to be greater than or equal to zero.
And we're going to sum up for each dish the size times the amount of that dish,
and say it's less than the capacity.
And our objective is, of course, to maximize the total satisfaction.
And you can see here that we're introducing some new concepts.
So first of all, we've got an array look up.
So if I have an array amount, how do I get the ith amount, so the amount for
the ith DISH.
Then I just write it like that, like you do in most languages.
Next we have a forall expression.
So here we're saying forall (i in DISH) ( amt [i] >= 0).
So this is going to add a constraint to every dish's amount.
So basically we're forcing this constraint amount of i is greater than or
equal to 0 for each of the amount decision variables in this array
and we also have a sum expression here.
So we're summing up over a variable sized array.
So we're summing up over all the dishes, the satisfaction for
that dish, times the amount of that dish, and
that's going to give us the total satisfaction for the meal.
So this sum expression generates information over all of the dishes.
That's what we're doing over there.
So we've seen some new amazing features here, so
we have seen ranges before when we declared the initial ranges of a variable.
We also, we can use ranges from l to u which we did in here, or enumerated types,
which is what we did here, when we were summing over all the dishes.
We have arrays of parameters and variables, so we had examples of
parameters for the size of a dish and variables for the amount that we'd pick.
And we wrote this as array, then the range of and
then the variable declaration that we wanted.
So we basically got a copy of the variable for each element in this range.
And we've had array lookup here, where we have the array name and
index expression, just like we do array lookup in most languages.
And then, we've also seen, for the first time, some generator expressions.
So this allows us to build something which is dependent on the size of the data.
So here we've got a forall expressions, so forall (i in range)(bool-expression) is
going to force this Boolean expression to be true for every value i in that range.
And usually i would be somewhere int his bool-expression doing some array lookup or
something like that.
And then we have the sum expression, so sum(i in range)(expression) and
this will return the sum of all the expressions for all the i's in that range.
It'll add them all up and return that value.
And that's what we've used here in this simple model.
So now we can run our model with the two different data files for
the two different problems we want to solve.
So here's the data file for the heroes table.
Here's the three dishes that they have, the capacity of the table,
the satisfaction of each of those dishes and the size.
And we can run this by asking with the minizinc model and
the particular data file we have, banquet1.dzn here.
And we'll get this solution.
That's how much they should put on the table.
Then we can run it with the different data files.
So here's the data file for the rest of the army.
So we have our five different dishes, our capacities, our satisfaction amounts and
our size.
Again, we can run that by now just saying that
a different data file on the command line to minizinc, and
we'll get back a different solution for this particular problem.
And of course you can do the same in the IDE, we can just load up the banquet.mzn.
And then we can select one of the two data files that we have loaded into the IDE and
run it simply by hitting the run button.
So what have we seen here?
We've see basically how we model objects in minizinc.
So typically we want to do this.
We want to create a enumerated type that names the object.
In this case, it's the DISH, that is the enumerated type.
Then we're going to create a parameter array for
each attribute of the object that we're going to need to reason about.
So here we had two different parameters of our dishes.
We have their size and their satisfaction amount.
Then we're going to create a variable array for
each decision we need to make about that object.
So in this case, we had to decide how many of each dish to get.
So we built a variable array amount,
which decided how much of each of those dishes we're going to get.
And then we're going to build constraints over the objects using comprehensions.
And we saw two kinds of comprehensions, foralls and sums in this example.
So, we should note that a model has very many sets of objects typically,
not just one complicated model.
We'll have many sets of objects and we'll be building up different enumerated types
and building up different parameter arrays, etc, over these things.
And we'll see more examples of complicated arrays soon.
So in summary, we've seen enumerated types to represent sets of objects and what they
gave us is the ability to build a data file which was independent of the size.
The size could change with the data file.
And then we had arrays of the object to represent the attributes of that object
and the decisions about that object.
And in order to work with these arrays, we needed some way of building
expressions which involve an unknown number of objects.
And so we had forall and some as examples of generator expressions.
So they allow us to build expressions over multiple objects, in fact,
a number of objects which we don't know until we see the data file.
And of course, the Peach Garden Banquet problem is a version of the well-known
knapsack problem, that we've seen before.