Auto news on Youtube Nov 26 2018

[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.

For more infomation >> Basic Modeling for Discrete Optimization - First Steps by The University of Melbourne - Duration: 14:05.

-------------------------------------------

Basic Modeling for Discrete Optimization - Modeling Objects by The University of Melbourne - Duration: 8:32.

To motivate their soldiers, Liu Bei, Guan Yu, and

Zhang Fei decided to treat themselves and their army to a nice feast.

For their own meal, the brothers wanted to have three of their favorite dishes.

Each dish with its own satisfaction rating and plate size.

They needed to determine the number of these three dishes to maximize their

culinary satisfaction without exceeding the table space available.

For the soldiers, five different types of dishes would be served with wider tables.

So, the brothers needed to solve a similar problem.

They pulled out their magical tablet.

[MUSIC]

In order to increase the moral of the army,

our heroes want to organize a banquet for both themselves and the rest of the army.

So in order to do that,

they're going to try to make the most pleasing banquet possible.

So on their own table, they want to fill the table with their three favorite

dishes, which is snake soup, kung pao frogs, and mapo tofu.

But each of these has a satisfaction rating,

how much it's going to make them enjoy the meal.

But each of them has a size as well.

And the table that they're going to put them on has limited capacity.

So basically, they want to put as many of these dishes on the table as they can to

maximize their satisfaction in the meal.

So for this example, if the capacity of the table is 18, then we can see that

what we're really trying to do is solve this simple linear program.

I'm trying to maximize this satisfaction,

which is 29 times the number of snake soup dishes plus

19 times the number of kung pao frogs plus 8 times the number of mapo tofus.

So that's the satisfaction that we're trying to maximize subject to these

capacity constraints.

So basically we have to have those dishes fit onto the table.

But they also have to make a banquet for the rest of army with different dishes,

much cheaper dishes of course since they're going to feed many more people but

a much larger table.

So here we have five different dishes with different satisfaction ratings and sizes.

And so what we want to do is, since this is really the same problem,

is we want to model to be reused with different sized data.

So here we have five dishes.

For the heroes table we have three dishes.

We want to use the same model.

So let's build an minizinc model, which allows us to use differently sized data.

So, here's that model.

We've got an enumerator type telling us which sort of dish we're talking about and

then the capacity of the table.

And we have two arrays here.

So, this is the first time we've seen array declarations.

Basically, associating with each dish a satisfaction rating and

with each dish, a size.

So, there's an array declaration how to clear an array, so

we have one of these satisfaction values for each dish.

Now the important decisions we have to make is how many of each dish,

what amount of each dish, we're going to put on the table?

And so here is an array declaration of variable integers.

So this is an array for decisions.

So those are the decisions we're going to make.

And we can look at the rest of the model, we're saying that

the amount of each thing is going to have to be greater than or equal to zero.

And we're going to sum up for each dish the size times the amount of that dish,

and say it's less than the capacity.

And our objective is, of course, to maximize the total satisfaction.

And you can see here that we're introducing some new concepts.

So first of all, we've got an array look up.

So if I have an array amount, how do I get the ith amount, so the amount for

the ith DISH.

Then I just write it like that, like you do in most languages.

Next we have a forall expression.

So here we're saying forall (i in DISH) ( amt [i] >= 0).

So this is going to add a constraint to every dish's amount.

So basically we're forcing this constraint amount of i is greater than or

equal to 0 for each of the amount decision variables in this array

and we also have a sum expression here.

So we're summing up over a variable sized array.

So we're summing up over all the dishes, the satisfaction for

that dish, times the amount of that dish, and

that's going to give us the total satisfaction for the meal.

So this sum expression generates information over all of the dishes.

That's what we're doing over there.

So we've seen some new amazing features here, so

we have seen ranges before when we declared the initial ranges of a variable.

We also, we can use ranges from l to u which we did in here, or enumerated types,

which is what we did here, when we were summing over all the dishes.

We have arrays of parameters and variables, so we had examples of

parameters for the size of a dish and variables for the amount that we'd pick.

And we wrote this as array, then the range of and

then the variable declaration that we wanted.

So we basically got a copy of the variable for each element in this range.

And we've had array lookup here, where we have the array name and

index expression, just like we do array lookup in most languages.

And then, we've also seen, for the first time, some generator expressions.

So this allows us to build something which is dependent on the size of the data.

So here we've got a forall expressions, so forall (i in range)(bool-expression) is

going to force this Boolean expression to be true for every value i in that range.

And usually i would be somewhere int his bool-expression doing some array lookup or

something like that.

And then we have the sum expression, so sum(i in range)(expression) and

this will return the sum of all the expressions for all the i's in that range.

It'll add them all up and return that value.

And that's what we've used here in this simple model.

So now we can run our model with the two different data files for

the two different problems we want to solve.

So here's the data file for the heroes table.

Here's the three dishes that they have, the capacity of the table,

the satisfaction of each of those dishes and the size.

And we can run this by asking with the minizinc model and

the particular data file we have, banquet1.dzn here.

And we'll get this solution.

That's how much they should put on the table.

Then we can run it with the different data files.

So here's the data file for the rest of the army.

So we have our five different dishes, our capacities, our satisfaction amounts and

our size.

Again, we can run that by now just saying that

a different data file on the command line to minizinc, and

we'll get back a different solution for this particular problem.

And of course you can do the same in the IDE, we can just load up the banquet.mzn.

And then we can select one of the two data files that we have loaded into the IDE and

run it simply by hitting the run button.

So what have we seen here?

We've see basically how we model objects in minizinc.

So typically we want to do this.

We want to create a enumerated type that names the object.

In this case, it's the DISH, that is the enumerated type.

Then we're going to create a parameter array for

each attribute of the object that we're going to need to reason about.

So here we had two different parameters of our dishes.

We have their size and their satisfaction amount.

Then we're going to create a variable array for

each decision we need to make about that object.

So in this case, we had to decide how many of each dish to get.

So we built a variable array amount,

which decided how much of each of those dishes we're going to get.

And then we're going to build constraints over the objects using comprehensions.

And we saw two kinds of comprehensions, foralls and sums in this example.

So, we should note that a model has very many sets of objects typically,

not just one complicated model.

We'll have many sets of objects and we'll be building up different enumerated types

and building up different parameter arrays, etc, over these things.

And we'll see more examples of complicated arrays soon.

So in summary, we've seen enumerated types to represent sets of objects and what they

gave us is the ability to build a data file which was independent of the size.

The size could change with the data file.

And then we had arrays of the object to represent the attributes of that object

and the decisions about that object.

And in order to work with these arrays, we needed some way of building

expressions which involve an unknown number of objects.

And so we had forall and some as examples of generator expressions.

So they allow us to build expressions over multiple objects, in fact,

a number of objects which we don't know until we see the data file.

And of course, the Peach Garden Banquet problem is a version of the well-known

knapsack problem, that we've seen before.

For more infomation >> Basic Modeling for Discrete Optimization - Modeling Objects by The University of Melbourne - Duration: 8:32.

-------------------------------------------

WELCOME TO SYRACUSE UNIVERSITY FLORENCE - Duration: 4:08.

For more infomation >> WELCOME TO SYRACUSE UNIVERSITY FLORENCE - Duration: 4:08.

-------------------------------------------

Basic Modeling for Discrete Optimization - Welcome to Basic Modeling by The University of Melbourne - Duration: 2:50.

Welcome to Basic Modeling for Discrete Optimization.

I'm Professor Peter Stuckey.

>> I'm Professor Jimmy Lee.

This course is about solving problems using discrete optimization technology.

>> Optimization is a common form of decision making and

is ubiquitous in our society.

Its application range from solving Sudoku puzzles to arranging seating for banquets.

The same technology can schedule planes and their crews.

Coordinate the production of steel and

organize the transportation of iron ore from mines to ports.

>> In this course, you'll learn an entirely new way

to think about solving challenging discrete optimization problems.

By stating the problem in a high level modeling language and

letting 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.

[SOUND] My phone rings.

Please, excuse me.

[FOREIGN]

>> [FOREIGN] >> [FOREIGN]

>> [FOREIGN].

Okay, I'm sorry for the interruption, that was a call from Liu Bei again.

He is looking for help from us.

I almost forgot to mention that this course uses an entirely new teaching

approach, fable based learning.

You'll learn complex concepts by immersing yourself in the stories from the novel,

the Romance of the Three Kingdoms.

This novel is one of the four classics of ancient Chinese literature, and

it's still widely popular today.

>> In counter variance and well studied optimization problems, such as

the knapsack problem, graph coloring and the traveling salesman problem.

As well as important applications such as rostering, clustering, and

production planning.

We'll see how these seemingly insurmountable problems underlie

the challenges faced by the heroes in the Romance of the Three Kingdoms.

>> This immersive, animated experience will really help you understand and

appreciate the challenges being presented to you.

And will motivate you to follow us in picking up

new techniques to solve complex problems.

It will also demonstrate how frequently discrete optimization arises

in everyday life, even in ancient China.

>> With an understanding of advanced modeling technology,

you'll be able to solve many practical and

complex real-world problems that you couldn't conceive of solving before.

And most importantly, without even knowing how.

Since, all you need to do is describe the problem as a model.

Solving the problem is done entirely and

automagically by a sophisticated solver you need know nothing about.

Thus, solving these challenging problems will suddenly become easy.

>> [CROSSTALK] On to the story.

For more infomation >> Basic Modeling for Discrete Optimization - Welcome to Basic Modeling by The University of Melbourne - Duration: 2:50.

-------------------------------------------

Basic Modeling for Discrete Optimization - Global Constraints by The University of Melbourne - Duration: 9:13.

In order to establish the army, Liu Bei had encountered several expenses.

So he asked Zhang Fei to determine how much money had been spent so far.

Zhang Fei set to work using counting rods for his calculations.

However, just as he was close to finishing up and

to his great surprise, a cat jumped through the window and messed up his rods.

This left part of his calculation unknown.

Zhang Fei knew how many once were involved in the calculation, yet

he had no idea how to recover his work.

This calculation was important for future reference,

so this confused Zhang Fei told Liu Bei about the accident.

Liu Bei then took out his magical tablet to see if

it could help them to recover the calculation.

>> [SOUND] So, Zhang Fei is in charge of accounting for

the army, and he's sitting there doing his accounting

when a cat jumps in and messes up the figures.

Now the point is, he's doing accounting using a system of counting rods.

And after he sees the cat and bounces around,

he can see that 12 rods have been knocked off the table and not in their position.

And he remembers that all of the digits in these positions were different.

So basically he has to solve a problem of working out what

were the digits that have gone missing that the cat has mixed up?

So, just a briefly word about counting rod representation.

So this is a way of representing digits using up to 5 counting rods.

And there's two different ways, vertical and horizontal.

And in fact that's a very neat trick where you can keep vertical and

horizontal alternating so you can leave out digits while doing that.

Although we won't use that in this example here.

So he's got,

here is the representation of what those counting rod digits actually meant.

So he was in Arabic numerals, basically, the arithmetic that's going on here.

And of course this arithmetic should hold, so that's another part of the problem.

So let's look at building a model for that problem.

So what do we have?

We have a set of digits from 1 to 9,

and then we've got this array of how many rods it takes to represent each digit.

So the digit 1 is only 1, and 2 and 3 and 4 and

5 for representing the digits 1 to 5.

But then you need 2 digits to represent 6 and 3 for 7, 4 for 8, and 5 for 9.

You can look back, if you look here and number representations for

6 is 2, and 3 and 4 and 5.

Okay, so

that's basically telling us how many rods we require to represent each digit.

And then we have five different things we need to know,

basically each of the five messed up digits.

So if you look back at the example here we have one, two, three, four, five,

messed up digit positions.

And then we got our constraint.

Well we know the number rods in the digits that are messed up sum up to 12.

Okay, and then we're trying to make sure that the constraint holds.

So if we take the first number, it would be 2,303 * M1 * 10, because M1,

that's the missing digit here, if it's in the ten digits position.

So that's going to give us the value of the first expression.

And we take the second expression,

which is 980 + M2 * 1000 + M3 because here's M2.

That's in the thousands position and M3 is in the ones position.

So that'll give us the sum of the top two numbers and

then we have to add up to get the right value underneath.

Which are 301, which are the digits are given,

times M4 * 1,000 because the M4 is in the thousands position.

And M5 * 10 because it's in the tens position.

But one thing we should note here is we are looking up

using a decision variable into an array, all right?

So this is a very powerful modeling ability of things like MiniZinc.

We can use a variable here, we're going to look up using the digits here which is

the decision, how many rods it takes for that decision.

Now, we got to continue,

we know that each of the five missing digits are all different.

We could write down all of these not equal constraints to make sure that all

five of those digits are different.

So that tedious, it's long.

It's also prone to error.

You can leave off one.

So let's do it a different way.

The way we're going to do this is by introducing and aldifferent constraint.

So this is an example of a global constraint,

which is what we're going to talk about a lot in this course.

So here's the aldifferent constraint saying, everything in this list of digits,

M1 to M5 has to be different.

So it's just a shorthand way of writing down all of this information in one go.

But its definition is in a different file so we have this include statement here,

which says we gotta include the definition of the constraint, alldifferent.

And that's in this alldifferent.mzn file.

And then here's our global constraint, the use of the alldifferent.

And since the problem is just to find a solution,

we're just running solve satisfy to find what is the solution for these variables?

There's nothing to optimize here.

So we've seen a few new things in this model.

So we had a set of type, so here, rather than use a numerator type,

we used the digits from one to nine.

So here was our, we gave a name to that.

We called digit this name from one to nine, right?

So this can be used in place of any fixed set.

So that's often what we'll do.

Also is build ranges and give them names and

use those just like we used enumerated types.

We also variable lookups.

As I said here, we can use decision variables as part of an index expression.

And this is going to give us a very powerful modeling capability,

which isn't in many other modeling languages.

So here we're using it very, very simply.

Basically for each missing digit, we're using this array lookup to look up

how many rods it took to represent that digit.

We'll see many more examples of this later on.

So we also saw an include statement here.

So include just has include and then a file-name.

That's all you need for the include statement.

And basically, it takes the contents of this file and

just imports them directly into your MiniZinc model.

And it'll look in the current directory.

So you can use it to break a model into parts.

Or it'll look in the MiniZinc library path, whose what we're doing here.

Is looking up, finding the definition of all different, and

including it in our model.

So include statements allow us to break larger models into small pieces.

Although we won't do so much of that during this course.

But when you're building large real world models is very useful.

It allows you to load library definitions of global constraints and

that's what we're doing here.

We're loading a library definition of the order for constraint into our model.

And the nice thing about this is this global constraint definition we

load will be different depending on which solver you choose to use.

This is one of the key things that global constraints allow us to do,

is allows us to give a version of the constraint which is specialized for

the particular solver we're going to use for running the model.

So even though we write the model with one or

different solvers may see a different way of representing that all different.

Okay, and global constraints.

So technically a global constraints is any constraint which is

unbounded number of variables as input, and so we've already seen a linear

constraint like some expressions are kind of global constraints.

But here, global constraints typically will be a name of the special constraint

and then some arguments,

usually with arrays because they they attain unbounded numbers of variables.

So global constraints are used to store constraints that arise in many problems.

And using the global constraints makes the model smaller.

You can see here once were used alldifferent

we've made a much smaller model.

And it does more than that, it makes solving easier.

So typically, here we pass the alldifferent constraint to the solver,

the solver will know especially how to solve that constraint.

So basically we are recognizing some structure of the problem, which occurs

commonly in many problems, and passing that information to the solver, and

then that solver can use that information to solve the problem more effectively.

So if we run our model we're going to get an answer here.

So here you can see you can see each of the digits is different and if we count

the number of rods in these blue missing digits, you'll see they add up to 12.

So we've got our solution to our problem.

So in summary, we've introduced global constraints.

That's one of the most powerful concepts we'll see in this course.

It's a way of recognizing and

naming common tutorial substructure which occurs frequently in many problems and

dealing that information to then to the solver to be able to allow it

to do the best job it can on that particular common tutorial substructure.

Another powerful modeling approach we've seen here is the ability to use a decision

variable as an index into an array expression.

And this will allow us to build very very complex constraints while building up

arrays and using decisions to look into those arrays to find the appropriate

path that we need for the model.

So here we're just using a very simple example, but

we'll see much more complicated uses of this later on.

For more infomation >> Basic Modeling for Discrete Optimization - Global Constraints by The University of Melbourne - Duration: 9:13.

-------------------------------------------

Sir David Attenborough - University of Leicester Centenary Square dedication - Duration: 1:05.

For more infomation >> Sir David Attenborough - University of Leicester Centenary Square dedication - Duration: 1:05.

-------------------------------------------

Alumni University - Duration: 1:23.

this is my first time attending and i definitely would like to come back i mean you come here you get treated like a

Queen and the icing on the cake was the little breakout sessions that you get

To see things you never saw the panels were fantastic and then the entrepreneurial

session was really great and i met a lot of fun people i don't know anyone in

the group i

Didn't know anyone here but i met a lot of wonderful people you know from all the different classes

Everybody want to know what class you are in and where you're from where did you stay and we went on the bus tour yesterday

And it was so funny because

we drop drive by certain areas and i remember events in my time here in those spots

It's just fun to see the old spots and see what they've done like

you, know the south campus and the west campus

1855 buildings awesome there's always changes going on and just doing the bus tour

it's always seen things

it's good to be back.

some of our friends who graduate around when we did

retiring now

they're out of state mostly but we're gonna invite them back next couple years

come back and see this place because it's only getting better

For more infomation >> Alumni University - Duration: 1:23.

-------------------------------------------

Murray State University - Apply Today! - Duration: 0:31.

You have dreams. We'll help you make them happen. At Murray State University, we've

earned our reputation for excellence. We offer the best of both worlds;

state-of-the-art facilities paired with small class sizes and faculty dedicated

to your success. You'll gain hands-on experiences and take your education

beyond textbooks and lecture halls and with one hundred and twenty six academic

program offerings, you'll find endless opportunities here. This is where your

future begins. Apply today!

For more infomation >> Murray State University - Apply Today! - Duration: 0:31.

-------------------------------------------

Racist robocall messages left for Montana State University Billings staff members - Duration: 1:01.

For more infomation >> Racist robocall messages left for Montana State University Billings staff members - Duration: 1:01.

-------------------------------------------

Basic Modeling for Discrete Optimization - Module 1 Summary by The University of Melbourne - Duration: 5:49.

All right, so welcome to the summary of the first module.

Here we're going to go through what we have to do, what we've seen over this

material, and the workshop and assignment for this module.

>> Right.

>> So, Jimmy, what have we seen?

>> Right, I hope you have been enjoying the journey with our three kingdoms.

Heroes, the heroes have met,

they have even sworn their brotherhood in the Peach Garden.

And the rest of the stories mainly focuses on the problems they have encountered

informing the armies, as well as, doing weapon production.

So what have we learned?

>> So that's the story in the technical side of the course,

where we've seen basically how to model in music, basic modeling approaches.

We've learned the basic concepts of modeling, so

we have decision variables, and constraints, and objective,

and an output statement, to see the result of our model.

>> Well the objective is optional, right?

Because actually students, they also learn how to differentiate between

a satisfaction and an optimization problem.

>> Yeah, so those are two classes of problems we'll see throughout the course,

where we just want to find any solution to our problem, or

where we'd want to find a good solution to our problem.

So what else have we learned?

>> I think, of course, after a student has started doing modeling they have to be

able to run the models as well.

So we have taught them how to make use use of the [INAUDIBLE] IDE to run the models,

as well as, running, using the command prompt, but of course,

we never show that but it's very easy.

>> Yeah so we expect that most students will run the IDE throughout the course.

>> Yeah >> Okay among the other things that

student learn in modeling,

I think one thing that is particularly important is the concept of types.

That allow us to give names to data

that would really help to make our models much more understandable.

>> Yeah, and one thing we've seen, another important concept, is this separation

between a model, which is a basically a recipe for solving a class of problems.

And an instance,

which is a model together with the data, which is a problem we can actually solve.

>> And then the students also got to see a very important data structure, arrays.

They allow us to make use of iteration, such as for all and

some, as well as, array comprehension to process such array datas

>> Yeah, and

arrays are going to be essential to us to be able to model a problem

which takes arbitrary different sizes of the actual data, so

we can solve different size problems with the same model.

>> Right because of that, that would allow us to build one model that is

general enough to allow us to use it solve several related problems.

>> Exactly, and we've look at classes of problems, we've look at linear models,

where all the constraints are linear.

This is a particularly important class because there is

a kind of solver that is mixed to your programming solvers,

which are specialized to handle this class of problem.

And we can handle very big problems of this class.

>> Yeah, and of course, allows us to model nonlinear constraints as well,

such as the not equal relationship.

>> Absolutely and we've also seen a generalization of the not equal,

which is our first global constraint, this is the all different constraint which

allow us to say that all of these variables take different values.

And we'll see many, many more global constraints throughout this course.

>> And also in the last chapter we learned a very important modeling concept

in which we are allowed to make use of variables as indices for arrays.

>> Yeah that's true,

that's one of the powerful modeling tricks that we'll use throughout the course.

>> Yeah, and what kind of applications have you seen?

>> So we've seen production planning, that's a very classic

optimization problem, that goes on throughout the world everywhere.

Where we're trying to work out how to best make use of the resources we have to build

some products, or build some internal things at the most efficient way.

>> Yes, we will see the production planning also has many,

many applications as well.

>> So we saw graph coloring, now graph coloring may seem to be a kind of

toy problem that no one's really interested in,

but in every compiler there's graph coloring to do register allocation.

And graph coloring is kind of a simplified version of roistering.

>> Yeah, and of course it has applications in time tabling as well.

>> And time tabling and roistering, yeah.

>> And then we also saw a knapsack problem.

>> Yeah, so the knapsack problem is kind of the smallest discrete optimization

problem which has all of the nasty things.

It's in be hard, so it's going to be hard to solve.

And it's really this exact trade off between the constraints fighting

against the objective,

which we'll see as a large part of what we do in discrete optimization.

>> We all want to be able to solve knapsack problem because we always have

limited capacity, but we always want to maximize our profits.

>> And knapsack problems occur as a sub problem of many, many real world problems.

>> Yeah.

>> So, we've now finished the course material,

now you'll need to go off and do the workshop and the assignment.

So, workshop one is about temperature control in a forge, and

you will use linear constraints and arrays.

And mainly it's there to make you see beyond the procedural view,

the first part you'll think, I can easily write that in a procedural language.

The next part we are actually writing controller,

you need to think declaratively, and so that's the aim of that workshop.

>> Right, remember to read the specification and

try the problems before watching the solution videos.

>> And then assignment one is also it's going to be fairly simple,

they'll get harder, don't worry.

So you're going to solve some cryptarithm problems, and the very first one is just

checking that you can actually submit through the Coursera infrastructure.

And then you'll look at more complicated cryptarithm problems

all based around the seven paces poem story.

>> Right, so, this is the end of the summary.

For more infomation >> Basic Modeling for Discrete Optimization - Module 1 Summary by The University of Melbourne - Duration: 5:49.

-------------------------------------------

Basic Modeling for Discrete Optimization - Third Model by The University of Melbourne - Duration: 6:55.

Liu Bei, Guan Yu, and Zhang Fei wanted to borrow horses from a wealthy man,

Zhang Shiping, to help suppress the Yellow Turban army.

Zhang Shiping wondered if the brothers were talented enough

to make good use of his horses for the suppression.

He decided to give them a problem and

promise to let them borrow the horses if they could solve it.

The problem was to color a map of the Han Dynasty, using at most four colors,

such that the adjacent states didn't share the same color.

Lupe thought for quite a while about the problem but was unable to solve it.

So urgent was the need to borrow the horses that he sought help using

the magical tablet.

[SOUND] >>

So, our three heroes are interested in building a stronger army.

And so they go to visit Zhang Shiping in order to see if he'll sponsor them for

horses.

But Zhang Shiping is a wise man and he sets them a challenge first to show

that if he's going to sponsor them, then they are going to show

the capabilities that's going to be able to defeat the Yellow Turban Rebels.

So he gives them this map of the Han Dynasty and says, four-color this map.

So let's look at MiniZinc model to color this map.

So here we have an enumerated type COLOR, which is made up of four different colors,

green, blue, pink, and yellow.

And each of the different provinces is declared

as a variable of this enumerated type COLOR.

So province Si, we're going to have to decide which color to color that province,

and the same all the rest of the provinces.

Now we have to write down the constraints of the map.

So any two provinces which are next to each other

we have to make sure that they have a different color.

And so we've written down all of those constraints.

You can see that there are so many that we've gone through a very small font size.

Let's just look at a few of them.

So, the province Liang is next to the province Yong and so

we've written this constraint here, the constraint Liang is not equal to Yong.

And similarly, the province Yong is next to province Yi.

So I've written that constraint, Yong is not equal to Yi.

The province Yong is next

to the province Jing so I've written that constraint, Yong is not equal to Jing.

And the province Yong is next to Si and so we've written this constraint,

Yong is not equal to Si.

And we write down all the rest of these neighbor relationships

between the different provinces.

We will solve satisfy,

we're just trying to find one particular solution to the map coloring problem.

And we can this run MiniZinc model and will result in the coloring.

Able to print out all the different colors of the map.

Notice we didn't need an output function and we're just going to get for

each particular province which color it got.

And if we look at the result we'll see a correct coloring of the map

where every province is colored different to every neighbor.

So, what we've seen here is a new feature

of MiniZinc which is enumerated types.

So enumerated types are a way of defining a finite set of named objects, and

then we can make decisions and parameters can be then about these enumerated types.

And array indices which we'll introduce later can also be over these enumerator

types and we can also choose sets over these enumerated types,

which we'll see shortly.

So they're declared by this enum and

then the name of the enumerated type and then they're defined by this equality,

enum-name is then given this set of identifiers.

So we got the example of the set of different colors that we were given.

And then we can declare the variables by this var, and the name of enumerated type.

And then variable name, or if we don't have the var in, it's a parameter,

and we're just picking a particular fixed version of this enumerated type.

So we could modify our program to have a different enumerated type.

Let's call it green, blue, and pink.

So can we color this map with just three colors?

And we could run our MiniZinc model then,

we will result in this, unsatisfiable, right?

So this is a new kind of output we haven't seen before, and

it should be fairly clear what it means.

It means that there is no way of three coloring

the map of the Han Dynasty provinces.

So we know if you know that there's a four color map theorem says there's always

a way of four coloring a plain out map like this one.

But there's no way of coloring this map with three colors.

And so our MiniZinc, our solver is telling us there is

no possible way of solving this problem and getting back the result unsatisfiable.

So in this lecture we've introduced enumerated types which is a way of

introducing a named set of objects.

So their real importance is that they introduce a notion of type safety

of models.

If I have two different sets of objects that I'm making decisions about,

then I don't want to mix them up.

I don't want to make decisions about this one when I meant to be making

decisions about that one.

So enumerated types will in fact map down in the solvers to be integers.

We could have used the numbers one to four to color our map,

instead of these color names.

And in fact the numbers one to four is what the solver will see

when it sees this problem, but by using this name type, we not only get

a model which is easier to understand, but we also get this notion of type safety.

Which will help us later on with more complicated models.

We also saw for the first time an unsatisfiable model.

We have to be clear that not every model has a solution, so

sometimes we'll ask to find a solution, there will be none.

More often, an unsatisfiable model will arise because we typed in a model

incorrectly, there's a bug in our model or a bug in our data, and

unsatisfiable will be a trigger for us to try and find out what's going wrong.

And the problem we solved here was graph coloring,

this is a very classic problem in graph theory.

It has applications in register allocation, in compilers, in timetabling,

a lot of other things.

And, of course, as I'll usually say,

pure graph coloring is better handled by specialized algorithms.

So lots of problems in graph theory are being studied intensely,

like graph coloring.

And if you are featuring a pure graph coloring problem, and

you should use a specialized algorithm.

But if we add some side constraints about how specific parts of the graph should be

colored, then using a general discrete optimization approach like MiniZinc,

is the way to go.

For more infomation >> Basic Modeling for Discrete Optimization - Third Model by The University of Melbourne - Duration: 6:55.

-------------------------------------------

Amazing Cornish Makers: Falmouth University Digital Print Bureau - Duration: 4:25.

My name is Freya Moses and I am the Senior Technician for printed

textiles so I cover screen printing but obviously also cover digital print as

well. We're in the digital print room and so basically this houses our two large

format digital printers and it's sort of central within fashion and textiles,

obviously we share this building with four of their courses. So this is our

shiny new Mamaki printer so we're very lucky to have this it's a year old so it

is, you know, top of the range and it's partly industrial, but also used for

educational printing, but it can print, you know, sort of 10, 12 metre lengths

at a time. It prints with reactive dyes so it's the more high-end way of

printing textiles, which is obviously what we want on textiles you know we

want to print kind of the best we can. So the dyes that we use, they only work on

natural fabrics, so we can print on cottons,

silks, wool, jerseys, you know, all those sorts of things and so we've got a huge

range of fabrics I think we've got about 25 at the moment and but we're also open

for requests as well, if there's a particular fabric somebody wants, you

know, pop-up we can negotiate, talk about it and see if it's something that we can

offer, but yeah so we've got obviously got two printers and but this is our

main one that we use just because it's the newest one and you can kind of print

quicker, the quality's amazing and so yes we're very pleased, very pleased with our

new printer. So we're really, really keen for local businesses, makers to come up

and just look at the process look at the printers, local makers are outsourcing

because most of the companies that offer this a kind of thing are up north, like

Macclesfield, London all of that and it's quite anonymous you send off your file

and then you kind of get what you're given, but you don't see the process and

I'm a designer, so when I design textiles for digital printing I'll design them in

a much different way to if I were screen printing it, because I know the process

so I think it's so important for all of the makers to know how this works

because I think it will inform their designing a lot,

we also kind of educate as well so of course they can come up watch the stuff

print, anything like that, we can obviously accommodate. I think what makes

us a bit different to bigger kind of setups is that we can print very small

samples so rather than having to have you know a minimum of 1 metre, 2 metre

printing I could do a minimum of half a metre 30 centimeters you know so we can

offer. I think printing that's more appropriate

for kind of smaller makers people that are starting out wanting to prototype

new products, our lead time as well is a lot shorter, so we're sort of working on

like a week kind of lead time so I think basically we can kind of offer an

opportunity for small businesses or local makers designers it's almost trial

stuff with us and yeah if they wanted like I mentioned before 10 meters of a

fabric that's absolutely fine but we couldn't print huge you know amounts of

fabric so if someone's wanting 50 metres, we wouldn't be able to do that with the

setup that we have, so I think we can offer and it would be for sort of you

know maybe mid level you know from small to mid level kind of designers makers.

I'm really sorry I can't be there at the amazing Cornish makers event today but

I'm really excited to be able to share with you what we can offer you with our

digital print Bureau here at Falmouth University if you've got any questions

if you would like to come up and have a look at what we do we've got a Facebook

page which is digital print bureau for Cornwall and we've also got an Instagram

page which is fowl digital print. Thank you!

For more infomation >> Amazing Cornish Makers: Falmouth University Digital Print Bureau - Duration: 4:25.

-------------------------------------------

Basic Modeling for Discrete Optimization - Arrays and Comprehensions by The University of Melbourne - Duration: 16:33.

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.

For more infomation >> Basic Modeling for Discrete Optimization - Arrays and Comprehensions by The University of Melbourne - Duration: 16:33.

-------------------------------------------

Racist robocall messages left for Montana State University Billings staff members - Duration: 1:01.

For more infomation >> Racist robocall messages left for Montana State University Billings staff members - Duration: 1:01.

-------------------------------------------

Oxford University | Wikipedia audio article - Duration: 1:05:14.

For more infomation >> Oxford University | Wikipedia audio article - Duration: 1:05:14.

-------------------------------------------

Basic Modeling for Discrete Optimization - Second Model by The University of Melbourne - Duration: 7:53.

After recruiting their army with help from the magical tablet,

the brothers started to train the soldiers.

Some soldiers fled because of how tough the training was.

The brothers observed the loss of the soldiers and

wanted to know how many soldiers remained without counting them one by one.

Zhang Fei proposed to adopt a similar method to one used by the famous

military scientist, Han Xin.

They arranged the soldiers in five lines of equal length and

two soldiers were left out.

They then arranged the soldiers in seven lines of equal length, and

two soldiers were left out.

They further arranged the soldiers in 12 lines of equal length, and

one soldier was left out.

But later, Zhang Fei could not work out the number of soldiers using

these three arrangements.

So, Liu Bei took out the magical tablet to see whether it could help.

Preparing the army to take on the yellow-turbaned

rebels is hard work and not all of their soldiers are up for

it, so some of them are running away.

So, our heroes would like to know how many they have left.

So, they line them up in a column of rows of five, and they have two left over.

And they line them up in rows of seven, and they also have two left over.

And they row them up in lines of 12, and

they have one left over, so how many soldiers do they have?

Well, we can do some maths, and we'll show you how to do it later on.

But why do maths when you can just have it answered for you directly?

Let's build a MiniZinc model to do it.

So we can see that we have an army.

Now, how many people do we have in our army?

Well, in fact, this is very loose, between 100 and 800 vars.

Given we had originally had something like 496, it's not going to be 800, but

it's somewhere in that range.

We don't think we lost too many of our soldiers.

And then the constraint's saying, well, our army mod 5 was 2.

We had 2 left over if we lined them up in lines of 5.

And our army mod 7 was also 2 because we had 2 left over if we lined them up in

lines of 7.

And our army mod 12 was 1,

And, then, this solve satisfy.

So here we're not trying to optimize anything,

we're just trying to find a solution.

So is there a solution to this problem?

So this is a different kind of discrete optimization problem.

It's not really a discrete optimization problem,

it's a discrete satisfaction problem.

Just trying to find a solution to these kind of constraints with

this decision variable.

So there's no output in this model either, and we'll make use of that, as well.

Show what happens when we have no output in our model.

So we can run our MiniZinc model as follows.

We can just type MiniZinc count.mzn, and we get this result.

So, we find the army is 457.

And we have our line of ten dashes indicating that we found the solution, and

then we don't have a line of ten equals indicating there might be other solutions.

Right, so there might be 457 soldiers left, or there might be something else.

So we don't actually know.

So we'd rather run this.

We're going to run MiniZinc with all solutions on.

So we're asking it to print out all the possible solutions there are to this

problem because what if there's another solution which is 453 or 452?

Then we wouldn't be sure how many soldiers we have.

Now if we run, we get that the army is 457,

That is a solution, and there's no other solutions.

Right, so this line here indicates there is no more solutions, so we know

the three heroes know that there must be exactly 457 soldiers left in their army.

So, the all solutions can also be set in the Configurations tab in the integrated

development environment.

So for optimization problems, it's the default.

For satisfaction problems, like the one we're running here, it's not the default

because typically for satisfaction problems you only want one solution.

You don't want to see all solutions.

But, here, we wanted to make sure that there weren't any other solutions.

So, if we look in the IDE, and you go to the Configurations tab, and

you run down, so here's the default behaviour, that's normally how you'd run it.

You can set user to find behaviour, and ask for all solutions, and

then you can get the same behaviour out of the IDE.

So note that we didn't have an output statement and we still got some output.

So what happens is if you don't declare an output statement then MiniZinc will output

all the declared variables in your model which are not assigned to an expression

in your model.

So, here, we only had one variable and so that was output.

And this is a very useful feature for simple models.

If you're building simple models, you don't have to worry about output,

you'll get a very useful output out of MiniZinc just by having no output item.

But for later models, you'll be interested in building specific output functions

to write out the bits of the decisions that you're interested, or

writing out the decisions in a way that's understandable to you.

So we could've done this without using MiniZinc because there's a Chinese

remainder theorem which is about solving simultaneous congruences.

And we could write down here's all the algebra for doing this.

We know that our army = 5t + 2, where t is some integer,

because it was, remember, rows of five plus two left over.

So that's saying it was 2 mod 5.

Similarly, our army is equal to 7u, some integer u

+ 2 because it was equal to 2 mod 7.

And it was equal to 12v + 1, as well, because it was 1 mod 12.

And then we have to do some substitution.

So if we substitute A into B,

we're going to get that 5t + 2 = 2 mod 7.

And then we have to do a bit of multiplication.

We subtract over here, we're going to get that 5t = 0 mod 7,

And then if we multiply both sides by the number, the inverse of 5,

we're going to get that t is 0 mod 7, in other words that t is 7w.

So, now, we can substitute that back into D.

Sorry, we can use D to substitute back into A, and

we know that the army is 2 + 35w, for some number, w.

Now, we can use that to substitute into C.

And we're going to get 2 + 35w is 1 mod 12.

With a bit more simplification, we'll find that w is 1 mod 12.

And then we can substitute that back,

and we'll end up with this thing that army is 37 + 420x.

And you can see, basically, the only solution to this in the range that we're

interested in is that the army is 457.

So, in summary, here we're seeing a satisfaction problem.

So sometimes we're interested in just finding a solution,

not necessarily finding the best solution, for a particular objective.

And we've also seen that constraints don't just need to be linear equalities and

inequalities.

So here we've used modulo, and we've used disequality,

or we could also use multiplication, division.

And we'll see many more complex constraints later on.

One of the powers of modern modeling language is being able to write down very

complex, highly non-linear constraints, and have our solver solve them.

For more infomation >> Basic Modeling for Discrete Optimization - Second Model by The University of Melbourne - Duration: 7:53.

-------------------------------------------

Basic Modeling for Discrete Optimization - Models and Instances by The University of Melbourne - Duration: 10:49.

Our three heroes are interested.

If they had more money, how much better an army could they have?

So here's our army model that we made a few lectures ago,

but we've made one change.

So before we had that the budget was 10,000, but

we've removed that, so we've left the budget unspecified.

So this is a parameter where we haven't given it the value.

This is a parameter without a value.

So, we need to run that.

So when we run that model, we're going to have to give that parameter a value.

So a parameter is not a decision, so it has to be given a value before

the solver can actually know what problem it's solving.

So we're going to have to get that value some way.

So one way is to do it this way, so we're running with a model file and

a data file, army.dzn.

And we'll assume this data file here has this content, budget equals 20000.

So this is an assignment giving the missing value to budget.

So now the parameter, budget, has a value, and now it can be solved.

And we'll get a new description saying, okay, if we have that much army,

that much money, then we could get this army, which will be the better army.

Alternatively, we can do it this way.

Since this data file is so small,

we can actually put the data file on the command line.

And we do this with this -D flag, and

then this string here, budget = 20000, is in fact the data file, itself.

So we can run this alternatively this way by putting the missing

values to the parameters on the command line, itself.

Okay, of course,

we can use the integrated development environment to do this instead.

If we run this model, MiniZinc will realize, hang on,

you haven't given me a value for a parameter.

It will actually pop up a window and ask you to type in the missing parameter.

So we can type in the missing parameter for

budget here, and hit Continue and we'll get a solution.

Another way to do it is if we have army.dzn loaded into the IDE and

we free run, we can select a data file from this drop-down menu when we run.

And that will allow us to select army.dzn which has the parameter value for

budget, and that will also allow us to give the parameter a value.

The brothers observed that there was a shortage of soldiers in their army, so

they planned to recruit some more, but

they needed to loan money from some business man in order to afford this.

Zhang Shiping suggested that they ask his friend, Su Shuang, for the loan.

Zhang Shiping spoke highly of the brothers and encouraged Su Shuang to help them.

The businessman, Su Shuang, agreed to lend money to the brothers, provided they would

pay back the loan, plus interest, over four installments in the following year.

Liu Bei tried to figure out exactly how much they needed to pay back

each installment.

He took out the magical tablet.

So our heroes go with Zhang Shiping to the money lender in order to get

some more money to hire a bigger army.

So, the money lender will lend them some money, but they're going to

have to make a repayment at the end of every season, that is, every quarter.

So let's look at the way the loan is going to work.

The money lender will lend them an amount, which is the principle.

That's how much money they get to lend.

They'll make a regular repayment, R, and there's a quarterly interest rate, I.

And at the end of Ith quarter, the balance that they'll owe, the I, is given by

the previous balance, plus the interest on the previous balance minus the repayment.

So let's look at a MiniZinc model to do that.

So here's our model.

Now we got some some new features.

So here we have here a float variable, so

var float: R; defining the repayment amount which is going to be unknown.

And here we have a float range, from 0.0 to 2.0, so

that's the interest rate between 0% to 200%.

So that is going to be another decision, possibly.

So let's look at our model.

So we've basically got these decisions, the repayment, the principal,

the balances after each of the quarters, and then the constraints that relate them.

So the balance after the first quarter, we take the principal,

we multiply by 1.0 + the interest rate to get the new principal plus the interest,

and we subtract the repayment.

Similarly, the balance after the second quarter is we take the balance after

the first quarter and do the same calculation.

And we can see the same thing for each of the other quarters.

And then we're going to ask to find a solution, and

we'll have a complicated output function which we won't show you for lack of space.

Now, let's ask some questions of this model.

So if Liu Bei wants to borrow $10000 at 4%,

repaying $2600 every quarter, how much does he owe at the end?

So we can have a data file that defines this instance by saying, well,

the interest rate is 4%, the principal is 10000 and the repayment is 2600.

And we can run the model by saying minizinc loan.mzn loan1.dzn.

So this is our data file here for this particular set of data.

And if we run this, we'll get the result saying that at the end we're going to

owe $657.78.

So how would we use the IDE?

Well, it's a bit tricky here because MiniZinc's

expecting when you use the IDE to fill in parameter values,

and here we're actually filling in decision variable values.

So it won't, by default, ask you for a data file.

But we can go to the configuration page, and select a data file in this top,

select a field, that's one way of doing it, and then type run.

Or, if we've got a project file open, we can go down, find the data file we're

interested with, have our model open, here, and say, run with this data file.

And that will also allow us to run our model with the data file.

So we can ask different questions with this model,

that's one of the reasons of our having different data files.

And, here, because we're changing the variables,

the decision variables that we're giving, we're asking different kinds of questions.

So if Liu Bei wants to borrow 10000 at 4% and

owe nothing at the end, how much does he have to repay each quarter?

So here's the data file for this where we're given the interest rate,

the principal, and the balance at the end rather than the repayment amount.

And this time, if we run this using the same thing, we'll find out that he has

to repay, basically, 2,700 every quarter in order to make this loan work.

So this is an example where we're using the same model

with different data to actually answer a different question because

the different data is specifying different decision variable entry values.

So here's a more interesting question.

If Liu Bei wants to borrow $10000, owe nothing at the end, and

he can repay $3000 quarterly, what is the interest rate he could afford to pay?

So here we're given a principal of 10000, a balance of 0.0 and

a repayment amount of 3000.

Again, we can run it just the same as we did before, and

we'll find out that he can repay up to an interest rate of 7.71%.

So, interestingly, this last question is quite a hard question to answer,

it's actually solving non-linear constraints.

And if we ask this to be solved via the G12 MIP solver, for example, which is

a mixed interest programming solver, we're going to get this kind of error,

that built-in operation float times is not supported by the MIP solver backend.

So to explain what's happening here is this problem is, essentially,

non-linear for a loan3.dzn.

Basically, we have to work out the interest rate,

we're going to solve a polynomial equation.

And the MIP solver just cannot express that multiplication of

continuous variables.

So it's just cannot solve this problem.

The default solver that we use, Gecode, uses interval arithmetic, and it can

solve this problem, so that's why it could solve loan3.dzn without any problem.

So not all solvers are equal, and you may see this that some models can run for

some solver and others won't.

Because of features of the solver, you'll certainly see differences in how quickly

various solvers can solve which model,

and which solvers can solve which models in practice.

So usually, though, data files define values for parameters,

that's the main use of parameters.

We also note they could be enumerated types as well.

For example, for

our color file we could have changed the enumerator type to just say color, so

just declaring that there is a color in the enumerator type in our MiniZinc model.

And then we could have had the color in the enumerator type declared in

a data file.

So, we'd get a five color data in the data file, and

we could have five-colored our map, instead.

So MiniZinc data files must end in .dzn.

And usually the data files only contain assignment items and usually only for

parameters.

But it's also possible for decision variables, as we saw in the lone examples.

And any parameters not assigned in the model must be assigned in the data file.

So there must be some way of getting that value into the model,

otherwise we won't be able to run it.

You can add multiple data files where you assign different values and

different parameters.

So on the command line it's straightforward by using

multiple data files, one after the other.

Much more difficult in the IDE, and

we won't go into how to do that because usually we won't have to bother.

So, in summary, a model, remember,

is a formal description of actually a class of optimization problems.

And an instance is one particular optimization problem.

And the way you get an instance from a model is you add the data.

So, typically, we're going to build now models which answer many,

many different optimization problems, and then we'll give them different data in

order to solve different instances of the problem.

So in MiniZinc, we do this by using data files, which is .dzn files.

For more infomation >> Basic Modeling for Discrete Optimization - Models and Instances by The University of Melbourne - Duration: 10:49.

-------------------------------------------

Saint Mary's University Co-Curricular Record - Duration: 1:49.

My name is Josie and I'm a varsity basketball player.

I have recorded over 300 hours on my co-curricular record.

My name is Gail Moxie I'm the current Co-President of Enactus Saint Mary's.

The CCR is a university verified document that allows me to track and report all of my volunteering experiences in and outside the classroom.

Hi my name is Sehmat and I'm a Student Leader.

Stepping outside of my comfort zone and getting involved around campus is what helped me understand myself and my passions.

Anyone can have good grades but having a CCR is what really helped me set myself apart from other University students

Telephone, garbage bags, and standard time.

What do these three things have in common?

Innovations created right here in Canada!

CCR is important because it effectively articulates skills and experiences.

This document allows me to show future grad schools and employers the different

experiences skills and leadership qualities I have gained throughout my undergrad.

We live in a vicious cycle where in order to get a job you need experience.

But in order to get experience, you need a job.

This is where volunteering and the CCR comes into play.

The CCR provides you with the opportunity to show my employers that

I have the transferable skills through volunteering in order to do their job properly.

My name is Isaiah and I'm the current Co-President of Saint Mary's University Indigenous Students Society.

As a Mi'kmaq person I got involved on campus to help my fellow First Nation students feel at home.

Hi I'm Tom Brophy, Senior Director of Student Services.

Research has shown that involved students are more successful.

The co-curricular record provides a transcript like document that reflects what students have done and what they have learned.