0:02

After acquiring the horse's need for

Â their army, Liu Bei started to consider producing weapons.

Â He planned to produce five different types of weapons of different power.

Â Axes, swords, pikes, spears and clubs to boost up the army's strength.

Â Had limited materials available, iron and wood, to make the weapons and

Â a certain number of woodsmiths and carpenters who could create them for him.

Â Each weapon consumed different amounts of these resources during production.

Â With this in mind, [INAUDIBLE] wanted to determine how many weapons he could

Â produce to maximize the total power of the army.

Â Based on the amount of resources at his disposal.

Â 0:42

In front of this complicated problem he took out his magical tablet.

Â [SOUND] >> Our heroes have gathered the army.

Â They've improved the morale.

Â Now it's time to make sure that the army has weapons to fight with.

Â So they're going to build five different kinds of weapons.

Â So they're shown here.

Â And each of them has a different strength.

Â Here's the strength of the various different weapons.

Â So some are stronger than others.

Â 1:12

And they've got a limited amount of resources to use.

Â So they've got 5,000 units of iron, 7,500 units of wood,

Â 4,000 hours of blacksmith time and 3,000 hours of carpentry time.

Â 1:27

And so there's going to be a resource consumption for building each weapon.

Â So, for example, for the sword, we're going to need two units of iron,

Â no wood, two units of blacksmith time, and no units of the carpenter's time.

Â And for the club, we're going to need 0.1 units of iron, 2.5 units of wood,

Â 0.1 units of the blacksmiths time, and 2.5 units of the carpenters time.

Â So we basically have this array of each of the resources and

Â how much each of the weapons needs to build it.

Â 2:08

And of course what we're trying to do is optimize the strength of all the weapons

Â that we build together.

Â So if we sum up for each weapon how much its strength is then we're going to have

Â the strongest possible army to use those weapons.

Â So we should notice that this problem looks very similar to some earlier

Â problems we've seen.

Â So we have our products, which are the weapons.

Â And each of them consumes some amount of resources.

Â Here we have multiple different resources that they can consume part of.

Â And the constraint and the objective are also similar.

Â We basically have one kind of constraint which is that we can't use more of

Â a resource than we have.

Â And our objective is to maximize something.

Â In this case, we can call it profit, but here we're maximizing strength.

Â If we look back at some of the earlier problems we've looked at,

Â they fit right into this framework of problems.

Â So we have gathering an army.

Â So what did we have?

Â We had one resource,

Â which was the budget, how much we could spend to hire the soldiers.

Â And we had one product, which was the soldiers.

Â 3:04

And in the peach garden banquet problem, we had one resource,

Â which was the table space, the amount which could fit in the table.

Â And the products that we were designing or choosing about were the dishes.

Â So basically, all of these problems, gathering an army, the Peach Garden

Â banquet and choosing the weapon production are all examples of the same model.

Â And we can build one generic model to do all of these.

Â So let's have a look at that model.

Â So basically we have this enumerator type talking about the products that we want to

Â build, or we want to choose how much of we're going to do.

Â And we have a profit that we make for each of those products.

Â So in this case we're maximizing strength, our profit is basically that strength.

Â 3:48

And we have a number of resources that we're going to have a capacity for.

Â So in this case we have four initial resources which is iron,

Â wood, blacksmith time and carpentry time.

Â So then we have this array basically for each product and

Â each resource how much does it consume to build one unit of that product?

Â And that's the array that we saw earlier.

Â So notice here, we're also using floats, rather than integers.

Â So we're using floating point numbers here.

Â So that we can talk about consumptions like .5 and

Â 2.5 that we saw in the example right earlier.

Â 4:26

So here is a two dimensional array declaration.

Â So for each product and for each resource,

Â we're going to give you that consumption amount.

Â So that's the first time we've seen a two dimensional array.

Â Now, we have the rest of the model.

Â So what are we deciding?

Â We are deciding for each product how much do we produce.

Â So that's basically the decisions that we're going to make in all of these

Â examples.

Â And we have to produce a non-negative amount of each product, so

Â there's our example here, for

Â constraint exactly like we saw in the Peach Garden banquet problem.

Â And then the one real constraint is that we can't

Â use more than the available resources.

Â So basically we're going to say, for every resource,

Â we got to have this capacity constraint problem which says, I'm going to sum up.

Â For each product,

Â the consumption of that product on that resource times the amount that we produce.

Â That's going to give me the total amount of that resource which we use for

Â building this particular product.

Â I'll sum those all up over all products and

Â that better be less than the capacity for this particular resource.

Â And we'll do that for all resources, so basically, we're adding one constraint for

Â each resource.

Â Saying we don't use more than that resource.

Â And then finally, we're trying to maximize our profit.

Â So basically, we're summing up over all products, the profit that we get

Â out of building one of that product times the number that we produced.

Â 5:57

So here we have an example of a two dimensional array lookup which is not

Â very different from in most languages.

Â All right, we're looking for each product and each resource, the consumption.

Â So as we have seen in the previous slide, arrays can be multi dimensional and

Â that can be declared by this array index_set1, index_set2, 3, 4, 5,

Â 6 etc of type whatever kind of array that you are building.

Â 6:24

And the index set of the array, these need to be an integer range or an enumerated

Â type, and it can also be a fixed set expression whose value is a range.

Â So basically, those need to be ranges, or

Â enumerated types when we're declaring the size of an array.

Â 6:38

And the elements of the array can basically be anything

Â except another array.

Â So, our array product resource of integers Is how much we consume.

Â Another useful thing we'll see, not in this model but in other models is

Â the length function which gives you the length of a one dimensional array.

Â Since we'll be building one dimensional arrays quite frequently in models.

Â 6:59

So let's talk about how we initialize arrays.

Â So one dimensional arrays are initialized using a list.

Â So you could initialize the profit for two different items like this.

Â And we've seen this already in the Peach Garden banquet, where we initialized our

Â one dimension arrays for satisfaction and size using lists.

Â 7:17

Two dimensional arrays are initialized using a special 2D syntax.

Â So it starts with this, which tells that its the start of a 2D array,

Â so its square brackets and vertical bar.

Â And the vertical bar for separating the different rows, which is the first

Â dimension, and it ends with this thing, the vertical bar, closed brace.

Â And you can see here, here's our consumption array which has

Â one row to product and one column per resource.

Â That's our two dimensional row which is product times resource.

Â 7:48

So you can initialize any array of dimension less than equal to six,also

Â using this array and family built in functions.

Â Which will turn a 1D array into an nD array.

Â So here's another way of building a consumption array,so we are building

Â an array 2D.

Â It's first dimension is size five,it's second dimension is size four.

Â And here's the 20 elements of the array in this row, column order.

Â So, here's the things for the first product, the second product,

Â third product, fourth product, fifth product.

Â And it's basically being broken up into one dimensional array.

Â If you know anything about how arrays are stored in memory in languages like c,

Â these should be familiar with you.

Â It's just a way of revisiting that memory.

Â 20 numbers in a row in a two-dimensional format.

Â So once we have arrays, we can do many, many things with them, and

Â one of the things we can do in MiniZinc is use array comprehensions.

Â So array comprehensions are like array comprehensions in other languages like

Â Haskell ML, and they allow us to build arrays of various different forms.

Â So an array comprehension looks like this.

Â It could be an expression and then a number of generators and

Â we'll talk briefly about what generators look like.

Â And basically each of these generators is going to generate different

Â sets of values.

Â And we're going to generate a copy of this expression for

Â each of these sets of values.

Â 9:06

We can also have an array expression with the generators here, an aware clause, and

Â the test.

Â And then we're going to generate all the possible ways these generators convey.

Â And those which pass the test will cause the creation of one of these expressions

Â In this array.

Â So it's probably easiest to look at an example, so here is a generated expression

Â which says i and j are going to take the values from 1 to 4.

Â Now, I will vary most slowly so the first value you will get is i is 1, and

Â then you will try j is one two three four, and then you would try i is two,

Â and j is one two three four.

Â But here we're only going to allow the possibilities where i is less than j to

Â pass this to actually generate a copy of this expression here.

Â So of the 16 possible values combinations of I and J and one to four,

Â basically only six of those will pass the test.

Â So when I takes the value one, we'll try setting J to take the value one.

Â It'll fail the test.

Â And we'll try setting J to value two.

Â That will pass the test and will generate our first expression here 1 + 2.

Â Then we'll set j to 3 will generate 1 + 3 and j to 4 will generate 1 + 4.

Â Now we've run out of j values then we'll go back to i generating value 2.

Â We will try setting j to 1 and 2 neither of those will pass the test then we'll

Â generate the next expression 2 + 3 and j will go to 4 will generate 2 + 4.

Â Then we'll run out of j values.

Â We'll try generating new value of i of three.

Â We'll try j values one, two, three.

Â All of those will fail the test.

Â And when we try four, it will pass the test.

Â And then we run out of j values here, we'll try generating i as four.

Â And then we try all of the j values and none of them pass the test.

Â So basically these are the only six values which we generate.

Â These six expressions are generated and

Â of course they can be evaluated to this array here.

Â 10:54

So, arrays can also be built using this nd family.

Â So we've already seen this where we can take this one dimensional array and

Â convert it into a multi-dimensional array.

Â In this case here a two dimensional array,

Â we can go the other way using a comprehension.

Â So if I wanted to flatten a two dimensional array or an n dimensional

Â array into a one dimensional array, then I can build a comprehension.

Â So, here's a way of taking the two dimensional version of consumption and

Â converting it back into this list here, a one dimensional array.

Â Going to be an array of one to 20 of integers, our list.

Â And what are we going to do?

Â We're going to look at every consumption value that occurs where i ranges from 1

Â to 5, that's the number of products, and j is one to four.

Â So basically this array comprehension here is the one generated, and

Â the second generated, no way to test here.

Â So we're just going to generate all 20 combinations of the consumption array.

Â Actually, we're going to build this one-dimensional array we see here out of

Â the two-dimensional array we saw earlier for consumption.

Â 11:55

So iteration is basically done through

Â these built in functions that operate over a list or a set.

Â And so we have already seen some of them some operate on a list of numbers a sum

Â and one which operates on a list of constraints is for all but

Â there are other ones, product, min, and max.

Â These are most popular ones that we are going to use,

Â which operate over a list of numbers.

Â And exists is another generator which operates over lists of constraints.

Â And basically, really, MiniZinc provides special syntax for

Â calls to these functions.

Â So when we write down this forall expression here.

Â So this says, i and j are going to vary from 1 to 10 where i is less than j,

Â and we're generating this constraint, a[i] is not equal to a[j].

Â Then actually where really this is just syntactic sugar for writing down this list

Â comprehension, or array comprehension, followed by an application of foralll.

Â So we're building up this a of i not equal to a of j as an expression.

Â And we're doing that for all i, j pairs in 1 to 10, where i is less than j.

Â So basically, when we write down this forall expression,

Â we're just writing actually down this list or

Â array generation expression followed by a call to forall.

Â So this is really just special syntax for this generator function.

Â 13:17

So now we can come back to our weapon production problem.

Â So here is our data.

Â We have our five different products, the different profits for each product.

Â We have four different resources.

Â And the capacity of each resource and then we have our consumption array,

Â which is basically for each product and each different resource how much we need.

Â 13:58

But remember we said that this general model could work for other problems that

Â we've looked at, we can look back at the problems we've looked at before.

Â So here was gathering an army, here are our four product c.

Â Which were the different villages here is the profits so

Â that was the strength of each of the villages that we were going to recruit.

Â We had one resource which is just the amount of money we could spend at

Â of 10,000 in the original gathering and army problem.

Â And then our consumption array so this note is a two dimensional array but

Â one of the is only of size one because we've only got one resource.

Â So basically it looks a bit strange, but basically it's a two dimensional array

Â with one row per product and just one column.

Â 14:40

So we can do the same with a Peach Garden Banquet problem.

Â So here's the hero's table version.

Â We had our three different products which were the different dishes we can serve.

Â The profit or satisfaction in this case for each of those,

Â there is only one resource here which is the size of the table,

Â had a capacity of 18 and again a two dimensional array of consumptions.

Â And notice here, we're also using point numbers where as before we used integers.

Â So we could use a default solver Gecode, and

Â it would actually work correctly because it does handle point numbers correctly.

Â But, we would rather solve this problem using a mixed integer programming solver

Â like G12 MIP.

Â Because the solving is almost instantaneous, because in fact this

Â production planning problem is a mixed integer programming problem.

Â So, a MIP integer programming solver is ideal.

Â So it can control these solvers if we go into the preferences part of our IDE,

Â we can see which solver we're using by the way.

Â 15:37

So we have to be careful when we start using floating point numbers that we

Â may not always get accurate results.

Â And this is true of basically any use of floating point solvers.

Â They don't always give you accurate answers.

Â 15:51

So, what we've seen here is how to build a model which applies to

Â differently sized data.

Â And that's important because the real world is full of solving the same problem

Â again and again and the data may change every time.

Â And basically, the usual approach to this is we'll define it enumerated type to name

Â outside of objects that we want to reason about.

Â And that may be a different type.

Â It's set up differently in a different data fall.

Â We use arrays to capture information about those objects, and

Â then we use comprehensions to build the constraints and

Â expressions that reason about this different sized data.

Â