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
Reference 3: Sets, Arrays, 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
So welcome to the reference section on sets, arrays, and comprehensions.
So all of these are crucial for building models,
which their size is dependent on the size of the input.
So the first thing we need are sets, so sets are declared by this expression,
set of and then type.
And the type can be integers or enumerator types or floats or Booleans.
And then set expressions, well then we have set literals,
which are open brace and
then the elements separated by commas, and then close brace, that was a fixed set.
We've already seen how to build integer or
float ranges as sets using this dot dot notation.
And then the standard set operator is provided, so
in says whether this element is in the set or not.
Writes the elements to the set and union and
intersection of two sets are well understood.
We can test whether one subset is a subset or a superset of another.
We can also do set subtraction is different, so
A diff B gives you all the elements of A, which aren't in B.
And symmetric difference is rather like X also A,
symdiff B gives you all the elements in A and B, which aren't in both.
And another important set operation is this cardinality operator which
gives you back the size of the set.
And sets can be used as types, so we can declare a variable given a set.
Here's some examples of some fixed sets, so
this numbers 1 to 6 is a few of the small prime numbers.
Here's a float range, here's a fixed set of float numbers, and
here's a fixed set of Boolean values.
Obviously, there aren't many sets of bools which are very interesting, so
we don't use sets of bools very often.
So let's look at some examples of set expressions.
So we can take ROW union PRIME, that's a union of two sets.
We can intersect two sets here, two sets of floats.
Here we're taking the symmetric difference of two sets.
Here we're checking if one set is a subset of another and
recording that result in Boolean.
And here we're building up a Boolean set,
which is going to have an element which is equal to is PRIME a subset of ROW.
And it's going to have the false element as well in that set.
So how do we evaluate those values?
So we think of x ROW union PRIME.
Obviously, we're going to have the numbers 1 to 6 which is ROW,
plus the numbers 2, 3, 5, 7, 11, 13, which is PRIME.
So that's the union of those.
We look at RAN intersection NUM, so there are two numbers in NUM,
our 2.57, 2.87, and 3.14.
And the range is from 3.0 to 5.0, so only 3.14 exists
in that range, so that's the end of the intersection.
If we take ROW symdiff PRIME, and we need numbers that occur in 1 to 6,
and in 2, 3, 5, 7, 11, 13 exactly once.
And we get 1 which it goes in the first one.
2, it goes in both so we don't get that.
3, it occurs in both, we don't get that.
4 only goes until 6, so that we get that one.
5, it goes in both 1 to 6, and 2, 3, 5, 7, 11, 13 so we don't get that.
And then 6, 7, 11, 13.
Is ROW a subset of PRIME?
Well, obviously not, because ROW takes the value of 1 which isn't in PRIME, so
that's just the value false.
We look at this set of Booleans, bs, is PRIME a subset of ROW?
No it's not, that's false, so we get this set of false and false.
But of course it's a set, so that's the same, same, the set containing false.
Arrays are another critical data structure in and they could be multidimensional.
They're declared by this array and index_set1 and set 2,
..., as many index sets as I want.
Although typically, we don't go very far beyond three or
four normally, of some type.
Now the index set of your array needs to be either an integer range or
a fixed set expression whose value is an integer range.
Or a enumerated type range expression,
because enumerated types act very much like integers.
So the elements of the array, so
what this type here can be basically anything except another array.
And here an array, 2-D array, known by PRODUCE and RESOURCE of integers,
you would have 1-D array variables, maybe the production.
Taking values from 0 to mproducts.
An important array function which we use is length,
which returns the number of elements in a 1-D array.
So 1-D arrays are initialized using a list, so
here is a 1-D array of profits with the values 400 and 450.
Here is a capacity which, obviously with a 1-D array with five elements.
A 2-D array initialization can also be done,
it uses a special 2-D array notation.
So here we start the 2-D array with this open brace vertical bar and this
is the first row, separated by commas and we use a vertical bar to separate the row.
Here's the second row, separated by commas and
here's vertical bar end braces to end the two-dimensional array.
And arrays of any dimension less than or
equal to six can be initialized from a list.
So basically from 1-D array we can build up to a six-dimensional array using
the family of arraynd functions.
So another way of moving exactly the same consumption matrix would be to
take the 1-D array, which is all the values given in the same order and
say, well, we want this to be an array which has two rows and five columns.
And we're going to have these index sets from one to two and one to five.
We'll get exactly the same result with these.
We can use concatenation on one of the arrays.
And that's sometimes very useful to concatenate some arrays and
then use an array indeed to built the array for example.
So a key thing that we're going to do with array and
set objects is build comprehensions.
So a set comprehension, as this expression, this is the expression
that's going to give the value of the current set and set of generators.
And we could have an optional where expression, which is
going to require that the generated variables take a particular value.
And array comprehension is exactly the same,
just we're using it with the braces rather than its closed
brackets rather than the braces to say that this is an array, not a set.
The generators of this form, var in set-expression.
So this variable is going to take values from this specific expression.
And normally, we'd expect this set-expression to be fixed, right?
We can't have unfixed set-expressions here.
But if we do, then it's actually going to end up doing something behind the scenes,
which can cause you some difficulties if you don't know what's going on.
We'll talk about that more in the relations
mandates in the option types section.
So an alternate syntax.
When you have two or more generators that use the same set is, we can have this v1,
v2 in set-expression, which is just shorthand for having v1 in set-expr,
followed by v2 in set-expr.
So how do we comprehend how comprehension works?
Basically, you give a value to variable generator1.
With that, you can give a value to the variable of the generator2.
You keep doing that until you hit the end of all the generators.
And then you evaluate this Boolean expression with all those
generator values.
And if it evaluates to true you'd generate this expression here,
given the values that the generator builds.
Then you try the next value for the last generator.
And you evaluate, again, this bool expression,
just check where they're called.
And generate a name and an expression in your array.
When that generator is exhausted, right, then you try the next or
last value for the previous generator.
And keep doing this until all the generators are exhausted.
But let's think about this on the simple example.
Here's a set comprehension.
But basically, we're going to do the array comprehension and
then convert it into a set because that's exactly how that goes.
Now i takes its first value, which is 1 and
j takes its first value, which is 1 and then we test, is i less than j?
That doesn't hold, so we go back to j, which is the last generator.
We take its second value, which is 2.
Is i less than j, yes it does hold, so we're going to generate 1 + 2.
Then, we're going to try the next value for j, which is 3.
Does this test hold?
Yes, it does.
We get 1 + 3 and I get the next value for j which is 4.
Does this hold? Yes, it does, we're going to get 1 + 4.
Now we exhausted all possible values for j.
We're going to have to go back to the next value for i which is 2.
So we try i is 2, j is 1, fails its test.
j is 2, also fails its test, j is 3, passes this test.
So we generate 2 + 3 and then we try j is 4, passes this test, we get 2 + 4.
We've exhausted all the values for j, so we go back to the value for i.
Now we have the value for i is 3.
And we try j as 1, fails the test, j as 2, fails the test, j as 3, fails the test,
j as 4, passes the test.
So we can write 3 + 4, we've run out of ways for j,
we go back to i, and take it to 4.
Try all the ways for j and none of them pass this test, so we can write nothing.
We've run out of values for j.
We'll also run out of values for i, so we finish.
So all together these were the elements we generated.
These are basically pairs of i and j which passed this test.
But of course because it's a set comprehension, even though we have
two ways of getting 5 here, the set only has one copy of the value 5.
Let's have a look at an array comprehension, a more complicated one.
So we're building up this array of integers where we have taken i from
the set primes, and we've taken j in the valuation i minus 1 to 6.
And we're going to keep all the i, j pairs if you sum them up, you get an odd number.
So you think about how this works.
i takes its first value, 2, and j will take its first value,
which would be 1 and 1 to 6, so it would make 1.
Now 2 + 1 is odd, so we're going to generate this absolute value of 2- 1,
this expression here.
Now we'll try j is 2 but
this will fail this test because we sum them up we get an even number.
So then we'll take j is 3, we'll pass this test so we get this expression.
Then we'll take 4, we'll fail, 5 we'll succeed, getting this.
6, we'll again fail the test and we'll finish all the values in j.
We'll go back to i and we'll take it to the next which is 3,
j will take variation 2 to 6.
We get 3- 2, 3- 4, and
the value of 3- 6 as the three cases where we pass this test.
And with these all j we go back to i, take them back from 5.
j's going to take values from 4 to 6 and we take the ones where that
adds up to an odd number which is 5 and 4, and 5 and 6.
Generate one copy of this expression for each of those and
we go back i takes the value 7 or you can take those j in rank 6 which is only 1.
It passes this test, so we get this one, then we go back and i takes a value of 11.
And then we're going to try j in the values 10 to 6, which is an empty range.
There are no numbers in between 10 and 6, so
we're going to generate nothing, i is 13.
We're going to generate nothing.
Overall, these are all the expressions we're going to generate, and of course,
we're going to evaluate them all.
We get this array, right, and of course, this is not a set, so
the order of the array elements matters.
We can't move.
All right, let's look at another example of using arrays.
And here I've got a two-dimensional array which has five columns and two rows.
What is the result of this expression?
All right, I'm taking c of j, i,
there I'm iterating over the columns first, and then the rows.
And then I'm going to coerce it into a two-dimensional array with five rows and
two columns.
So the first thing to think of is what does this expression here do?
Well, it says let's say i is 1 and j is 1 so we're going to get the first,
the top left most element in the array, 250.
Then it takes j is 2 which will be the first element in
the second row, which is 200.
Then it's finished j so it'll go back and
take i is 2 and j is 1, so we get 2 which is this bit,
which is this element, the second element in the first row.
And we'll get 0, 75, 150, 100, 150, 0, 75.
So the first thing is that this expression will generate this one-dimensional array,
which is basically a different order of the elements in c.
Then we're going to coerce that into an array with five rows and
two columns, so this is the array we generate.
And if you look at this array, with what we started off,
what we've actually generated is the transpose of c.
So let's look at some more set and array comprehension examples.
So 3 * i + j, i takes the values from 2 to 3 and j is in prime.
So again, at each of these values here and add 4 to them and
add 6 to them, so, this is going to be the result, so
adding 4, adding 6, and adding 9.
If we add 6 to each of these numbers,
we're going to get 8, 9, 11, 13, 17 and 19.
And then we'll also add 9 to each of them.
So we get 11, 12, 14, 16, 20,
and 22, so the set will have all of those numbers in it.
We're looking at i times j, we're looking at i taking values in the small set of
prime numbers and j taking values from 2 to i.
And then getting the i times j values where this j directly
completely divides i, the i mod j is 0.
We think about that, the only way, if I take the number 2,
the only number from 2 to 2 which divides it is 2 itself, so we get 4.
Take the number 3, the only number between 2 and
3 which divide 3 exactly is the number 3, so we get 9.
Then because basically these numbers are prime, the only number that
divides them exactly is themselves or 1, but we're not working at.
So we're basically going to get all these.
All right, let's look at z.
So here we've got a set comprehension, inside an array comprehension.
So i is going to take the values in prime except where i is the value of 11, so
we're not going to use that.
And for each of those sets, we're going to say, we're going to configurate
j with 1 to i, and take all the odd numbers from that value.
So in the first test, i is 2, all of the numbers in 2 is just 1.
And i is 3 we get 1 and 3, i is 5 we get 1, 3, and 5.
i is 7, we get 1, 3, 5, 7, i is 11 we don't do because we don't pass this test.
And for i is 13 we generate these set of odd numbers, so that's what.
So MiniZinc provides a lot of built-in functions which operate over 1D arrays
because that's what we generate with these array comprehensions.
So we can have operations on lists of numbers like sum, product, min, and max,
and operations or lists of constraints like forall and exists.
And MiniZinc provides this special syntax.
If we write function in a generator, generator where bexpr,
you've got this where, that one.
And then the expression's just a shorthand for
saying do an array comprehension, and then apply this function on that array.
So running this is exactly the same with.
Like for example, if I write down for all i, j 1 to 10 where i is less than j,
a of i is not equivalent to a of j, it's the same as this.
I'm building an a of i not equal to a of j in my array for all here's i,
j in 1 to 10 where i is less than j.
And then I'm applying it for all in that array Boolean expressions.
So let's look at some examples of generated call examples.
[COUGH] Let's take the sum i is in 2 to 3, j is in 3 to 4 of i + j.
Well, we're basically going to build this list of numbers, right?
2 + 3 and 2 + 4 and 3 + 3 and 3 + 4 is 5, 6, and 7.
And sum them up, we're going to get x 24.
Now here's almost exactly the same thing, except now I'm
basically summing up a set comprehension of exactly the same thing.
What happens now?
Well, I actually build up the set, right?
I take 5, 6, 6, and 7 into my set, but the set is 5, 6, and 7.
I take their sum, and get the value 18.
Now with this sum taking numbers i and PRIME and j in 2 to 3, and
looking at i times j mod 30.
Well, it's going to generate all the multiples of 2 of these things and
all the multiples of 3 of these things and take mod 30 of each of them.
And then find the minimum one, and in fact, it would turn out to be when y is 3,
which is [INAUDIBLE] happens when i is 11 and j is 3.
So again, with a value of 3.
We look at this one, we take all the values i in PRIME and j in 2...i-1,
and we want to find cases does there exist a case where j divides i exactly.
So i mod j equals zero, and
of course there is a prime number that only divides it is i and itself.
So all of these things are very likely false.
Exists over all things which are false, will give us this number.
So MiniZinc uses sets to name sets of objects.
So this allows us to talk about the collection of objects and do
things on the whole collection, and arrays capture information about those objects.
And then, with that, we can build comprehensions to build constraints and
expressions over these sets of objects of differently-sized data.
You're going to need to learn how to use comprehensions to build the data and
constraints and model complex problems.
And you can see more of that comprehensions in, for example,
in this Wikipedia file.
That brings us to the end of this section.
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.
