Optimization is a common form of decision making, and is ubiquitous in our society. Its applications range from solving Sudoku puzzles to arranging seating in a wedding banquet. The same technology can schedule planes and their crews, coordinate the production of steel, and organize the transportation of iron ore from the mines to the ports. Good decisions in manpower and material resources management also allow corporations to improve profit by millions of dollars. Similar problems also underpin much of our daily lives and are part of determining daily delivery routes for packages, making school timetables, and delivering power to our homes. Despite their fundamental importance, all of these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students interested in tackling all facets of optimization applications. You will learn an entirely new way to think about solving these challenging problems by stating the problem in a state-of-the-art high level modeling language, and letting library constraint solving software do the rest. This will allow you to unlock the power of industrial solving technologies, which have been perfected over decades by hundreds of PhD researchers. With access to this advanced technology, problems that are considered inconceivable to solve before will suddenly become easy. Watch the course promotional video here: https://www.youtube.com/watch?v=hc3cBvtrem0&t=8s
1.1.6 Arrays and Comprehensions
Loading...
From the course by The University of Melbourne
Basic Modeling for Discrete Optimization
122 ratings
From the lesson
MiniZinc introduction
In this first module, you will learn the basics of MiniZinc, a high-level modeling language for discrete optimization problems. Combining the simplicity of MiniZinc with the power of open-source industrial solving technologies, you will learn how to solve applications such as knapsack problems, graph coloring, production planning and tricky Cryptarithm puzzles, with great ease.
Meet the Instructors
Prof. Peter James StuckeyProfessor
Computing and Information Systems
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
