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.

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.

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.

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.

And we've got a capacity constraint so basically we've got to build a number of

weapons that still fit within the budget of each of our four different resources.

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.

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.

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.

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.

And then we're going to have output statements saying,

how much do we produce of each product?

Because that's what we need to know.

That's their decisions.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

So here you see a two dimensional array constant

using the syntax that we explained last time.

One per row and one column per resource.

When we run this weapon production data we can get an answer seeing how

much of this weapon we need to build, and how much profit we are going to make and

so the hero is already down the army.

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.

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.

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.

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.

1.1.6 Arrays and Comprehensions

Basic Modeling for Discrete Optimization

Meet the Instructors