[MUSIC]
Towards the end of the East Han Dynasty,
people suffered under the cruel rule of the government of the time.
The Yellow Turban Army, led by the Yellow Turban Army broke out, causing chaos.
Guan Yu, Liu Bei, and Zhang Fei promised to be brothers after they first met.
Together, they swore to suppress the Yellow Turban Army
in order to unify the Han Dynasty.
Impressed by their ambition, a celestial old man
came from the top of the sky to offer assistance to the brothers.
The old man gave the Swan brothers a magical tablet and
told them it could be helpful if they ever needed to solve a problem.
The brothers thanked the old man but were not aware of the power
of what they had just received.
After that, the brothers decided to gather an army.
They planned to recruit soldiers from the Feng, Liu, Zhao and Jian village.
The men that were available for
recruitment were different in terms of their power, salary and number.
Liu Bei had a budget of $10,000 to pay the soldiers,
and he wanted to maximize the total power of his recruited army.
Guan Yu, who believed excellent soldiers were critical for victory, suggested to
recruit as many of the strongest soldiers from the Jian village as possible.
However, Zhang Fei suggested to recruit as many of the cheapest
soldiers as possible from the Feng village
since he believed the scale of the army was more important for victory.
While they were arguing over the best recruitment strategy the magical tablet
given to them by the older celestial man, started to vibrate.
The brothers recalled the old man's words and tried to call for
help using the tablet.
So the very first thing that our three heroes have to do is to recruit an army.
So there are four villages available to recruit from, Jian, Zhao, Liu, and Feng.
And these villages have different characteristics,
so some villages are cheaper than others.
Some villages are much more expensive, they demand a lot and
they have different strengths.
So here on the top line, we have different strengths from very small villages and,
to the last village, which are very strong.
And, but they're going to demand different prices to work in the army.
So our very strong people are going to demand a great amount.
And of course there's a limit to how many soldiers we can get from each village.
So there's a capacity as well.
So, we have some constraints.
We have only a certain amount of money, $10000 in order to build the largest army.
And our objective is,
of course, the have the largest strength total of our soldiers.
So of course Guan Yu looks at this and says, obviously,
the way to do this is to get the most expensive, the best fighters.
Then they're the best we can afford a 100 warriors from the Jian village and
that'll be strength 4,000.
So that's Guan Yu's suggestion.
Zhang Fei's suggestion is, well no no,
we should just get the largest number of warriors so we can afford 769 warriors
from the Feng village and that would give us the strength of 4,614.
So the question is, can we do better?
So here is a MiniZinc model that's going to allow us to do that.
And without, we'll go through it in detail in a moment, but what I want you to see is
it's very similar to something I might write down in mathematics.
So here's a kind of mathematical expression.
I'm going to maximize this expression.
subject to some constraints, some linear constraints.
With some bounds on these variables,
where these are all, and the budget here of 10,000 is given.
So you can see that the MiniZinc that we've written down here is very,
very similar to this kind of mathematics.
So the order of this won't matter in MiniZinc.
And typically in a MiniZinc model, we'll write down the order more like this,
we'll write down parameters and variables at the top.
And then constraints and then objective at the bottom.
So let's go through this model in detail.
So the first thing that we have here is a parameter definition.
So we're defining a new parameter budget which takes a value of 10,000.
So really this is just a macro, saying,
Wherever we see the value budget will remain 10,000.
So that's going to give us a way of controlling the model.
We can change this number and all budgets throughout the model will be changed.
The next things we see here are decision variable declarations.
So here are our four decisions that we're making,
how many soldiers do we get from each of the four villages?
And these are integer variables where we're picking from the range
from 0 to 1,000, 0 to 400, 0 to 500 and 0 to 150.
So these integer variables picking from a particular range.
And that's the decisions that we're trying to make.
This is what the three heroes have to decide.
Then we have a constraint, so you can see the constraint keyword starts it off and
then here's the constraint written down.
This is basically forcing that we only hire a number of soldiers which fit
within our budget.
So, basically, every soldier from the Feng village cost us 13,
so, that's going to make sure that all of our soldiers fit within the budget.
And here we have the objective, so, what are we trying to do?
We're trying to maximize the strength of our army.
So, each soldier from the Feng village gives us 6 to the strength of the army,
each soldier from the Jian village gives us 40 to the strength of the army.
If we add up this expression here,
that's going to give us the total strength of the army.
So finally here, we have an output expression.
And this is what's going to be printed when we find a solution.
And so this is going to print out basically the value,
how many soldiers we get from the F village, from the L village,
from the Z village, and the J village.
And we'll see what that looks like when we run the model shortly.
So, what we're seeing here is a few things.
A MiniZinc has two kinds of variables.
So, the first kind is parameters and these are variables
like any standard programming language and they must be assigned a value.
So, basically, they're going to be given a value,
but they can only be given a single value, so they're like a mathematical thing.
This value takes a value 3, and a value 2 later on.
It's not like in some procedural programming languages,
where our variable is like a storage place.
I can put the value 3 in it, and later put the value 2 in it.
This is a mathematical thing.
The budget can value 10,000, it can't be later a value of 18,000.
It can only take a single value.
So they declared with the type so int, float and bool are the most common types
we'll see more complicated types later on in the course.
You can use a par as a prefix so this means parameter but
normally we'll ignore that so you'll never see that really in the course.
So you can do things like int i = 3, so this is declaring i to be
integer 3 wherever see i in a model we'll replace it with 3.
Par int 3 is the same thing.
And we can separate out these two things.
So it gives a int i, that's just saying i is a parameter, and
later on say i = 3, that'll save it to its value 3.
So we can separate the declaration of the integer and the value that we give it.
So that's the first kind of variable in MiniZinc,
the second kind is the decision variables.
These again are like variables in mathematics, but
these are the variables that the solver is going to work out the value to.
So they’re declared with a var, and then the type or a range.
You can see an example of range in the soldier assignment problem.
So, they can be assigned only once, again, by a fixed value expression.
So, we also seen the use of ranges.
A range is written l..u where l and u are basically integer expressions.
And this means the sequence of integers from l to u.
And so, each of this expressions here are equivalent.
We can express that i is the integer variable and we can constrain i to be
greater or equal to zero and constrain i to be less than or equal to four or
we can just say that i was an integer that ranges from zero to four.
So this one had the same effect.
What we're doing is having a variable i that we have to
choose from values from 0 to 4.
Here because we're only going to choose values which satisfy the constraints and
here because in the declaration we're saying we're only interested in values
from 0 to 4.
We could also give it a set of possible values here and that is set is 0 to 4.
So i is again a decision, has to be one of this set of integers and
it's the same set (0, 1, 2, 3, 4), is the same as the range 0..4.
And similarly these two things are equivalent.
I can declare i to be an integer and equate it to this expression x + 3,
or I could do the same by saying i is an integer like this, and then,
later on constrain i, to be equal to x + 3.
So, they are both the same.
There's just two different ways of writing down the same thing.
All right, now we also have constraints.
So, the basic arithmetic constraints, is, which we're seeing here,
in our very first model are built using standard arithmetic relational operators.
So we have equality, disequality, greater than, less than, greater than or equal to,
and less than or equal to.
And constraints in MiniZinc start with this keyword constraint and
then we write our constraint expression.
So we've seen an example of constraint in our model.
So let's talk about output.
A model can have a single output item which stands for this keyword output and
has a list of strings.
And string literals are like in C.
They're enclosed in double quotes.
And they can extend across more than one line if you try,
if you want to extend one across more than one line you need to close it and
use a string concatenation like this ++ operator down here.
There's backslash for special characters, like new line and tab, and
there are built in functions.
The most important one is this show function, which will take an expression or
a variable and show that value as a string,
basically convert that value to a string.
And the main use of it, and we've seen that in our example model, is this.
So we have \(v), then
we can use this to show the value of this expression v, inside a string literal.
So it can use that to build up the concise outputs where we've basically
showing the values of expressions inside a single string literal.
And as I already said, we have this ++ operator for build string concatenation.
So, let's run the model.
So, we can run our MiniZinc model by,
which was stored in a file called army.mzn by just typing minizinc
army.mzn at the command line and if we do, it's going to output this.
So, it's run the model and here it's found its results.
So, we can see that it's decided to take 392
soldiers from U, and 104 from Z and the strength,
although it's not printed here, you can work it out, is 4,752,
which was better than the strengths we saw from either of the suggestions,
from our heroes before and the size of course, is just adding up those two, 496.
So, this line here in the output is added by MiniZinc and
that indicates that it found a solution.
So, it printed out the output that also means it found a solution, but this,
it always adds this line to say, I found a solution.
So, if, it may print out nothing.
It'll tell you that.
And this line here of equal signs also says that it found the best solution.
It's actually showing that there is no better solution than this one here.
So this is the best possible solution.
So we were doing an optimization problem and that's what we're looking for.
We're looking for the best possible way of building an army.
So, MiniZinc models must end in mzn, so when we type minizinc army.mzn,
MiniZinc knows that this is a model it should be trying to run.
So there's also an IDE for MiniZinc, and we would expect most of you to
use the IDE throughout the course, and not use it from the command line.
So if you've loaded our model it is here.
It's been loaded into the IDE.
If that's the model that's selected, I can just hit this Run button here.
And I'll run the model.
In fact you'll see more information, actually found.
A lot of solutions on the way to the optimal solution.
It prints them out on the way.
As you can see, for each solution it found it prints out a line saying,
I found a solution and then at the last one it found a solution and it says, and
there's no better solutions.
So, MiniZinc allows us to directly describe and
solve discrete optimization problems.
And what we're seeing in this example is a linear model,
which is basically one of the most common forms of modeling.
So, linear programming has been used since shortly after World War II,
to solve many optimization problems.
But the integer case, which is what we're considering here is considerably harder.
In fact, it's an NP hard problem.
Or as in linear programming, it's polynomial time.
But still the integer linear programming is the basis of most,
we'll say, real world discrete optimization.
And we can use MiniZinc, in fact, to connect to these mixed integer programming
solvers which are expert at solving these kind of problems.