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 who have completed Basic Modelling for Discrete Optimization. In this course you will learn much more about solving challenging discrete optimization 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 course will focus on debugging and improving models, encapsulating parts of models in predicates, and tackling advanced scheduling and packing problems. As you master this advanced technology, you will be able to tackle problems that were inconceivable to solve previously. Watch the course promotional video here: https://www.youtube.com/watch?v=hc3cBvtrem0&t=8s
2.2.2 The let-in Construct
Loading...
来自 The University of Melbourne 的课程
Advanced Modeling for Discrete Optimization
54 个评分
从本节课中
Predicates
In this module, you will learn how to encapsulate a complex constraint definition in a predicate definition to enable its reuse. This will enable the construction of far more complex models with improved readability in a modular manner. You will also encounter for the first time a problem with multiple objectives and learn how to compress them into one single objective. In addition to this, you will learn how to model the banquet seating problem, which will assist you in many occasions in life.
与讲师见面
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
Cao Cao still considered Liu Bei a potential enemy,
even though Liu Bei had moved away to the Jing Province.
So he financed a team of bandits in the Jing Province
to cause chaos amongst the people.
Liu Bei decided to send a strike force to raid the bandit's nest.
The houses in the bandit's nest were located in a grid,
such that there was a walk way between any two adjacent houses.
The strike force planned to dig underground tunnels from one
corner of the housing grid through which they would sneak in.
They chose to exit the tunnels by digging up through the walk ways above them
as opposed to the bases of the houses which were too difficult to penetrate.
In their raid, the strike force could take control of houses within
three units of distance from the tunnel exit.
Because of this, they needed to exit in a way that all houses were in reach
once they launched a raid.
Digging an exit further away from the starting corner would cost more in terms
of resources.
And Liu Bei wanted to minimize the total cost incurred.
He took out the tablet.
[SOUND] >> Now our heroes are going to raid
a bandit's nest because the bandits are being supported by Cao Cao and
terrorizing the countryside.
And so basically, the nest is fortified and in this gridlike like shape.
And they're going to dig tunnels in to jump out of these tunnels and
surprise the bandits.
So that's the aim.
We've got a set of tunnel diggers and we're going to decide where to dig
tunnels in order to send the army down those tunnels and surprise the bandits.
So, when we're digging tunnels, we can't dig under the huts, okay?
So the huts are actually impervious so
we can't just directly break through the bottom of the hut.
We have to dig to places which are open ground.
So the diggable spots are these ones particularly in the corridors
inside the thing, we can't dig directly to a heart.
Now, once the tunnel is built, then our soldiers are going to jump out of
the tunnel and they're going to run around and attack the bandits.
And basically, what we want to do is get all the bandits quickly.
So we want to be able to get to every hut within a distance of three.
So, that's a Manhattan distance.
The Manhattan distance counts basically the number of steps we take vertically and
horizontally.
So, here the Manhattan distance of three to here because we go one horizontal stop,
then two vertical steps.
So each of these are examples of Manhattan distance 3.
So, if we open the tunnel here then we could reach all of these positions in red
within a Manhattan distance of 3.
And basically, that's how quickly we want to be there.
So we want to make sure that we're going to cover all of the huts within
a certain Manhattan distance, all right?
So we're going to make sure that huts are covered.
So for example, if we dug a tunnel to here,
we're going to cover these four huts in the corner.
If we dug a tunnel here, we're going to cover these four, right?
With these four tunnels,
we could actually cover all of the huts at Manhattan distance 3.
Unfortunately, Liu Bei and the other heroes only have three digging teams,
so this is not going to be a solution to our problem.
Now there's a cost of digging.
So basically, since the digging starts from over here,
the cost is how far away we are from that position.
So every different slot we can dig to has a different cost.
And what we're trying to do is minimize the cost of the digging because
effectively that's going to be how much effort we have to pay for
from our diggers.
So let's look at that model.
So we have the size of the bandit's point, so
it's size times size, it's a square bandit camp.
Then the number of points that we're going to dig to is going to
be this number of points and the maximum distance that we can be, so
we can cover where we're going to escape from a tunnel.
What's the maximum distance that we're going to be able to get to
in Manhattan distance to surprise the bandits?
Okay, so for each position in this size by size bandit array, we've got a cost.
How much it costs to dig there?
And then the main decisions, of course, are for each point,
we have to decide which row does that point occur on.
And which column does that point occur on which variables from one to size.
Now, we need that all the tunnel exits are different.
So we could write that this way so basically we're taking the row
number minus 1 and multiplying by size and adding the column number.
And that will map our two decision variables into a single integer and
making sure they're all different will force that the positions that we exit
are all different.
But that's kind of difficult to understand, so can we do better?
Well, we're going to introduce a new construct from MiniZinc to help us
do that.
So the let-in construct is very powerful in fact.
So it allows us to introduce new variables and parameters "any point" in the model, so
any points inverted commas because it's not exactly true.
And we'll come back and look at some of the restrictions of any point later on.
So the format as we say, let and
then we have basically a declaration of the variable.
We could have an expression which we equate it to,
we're going to have to do that for parameters.
And we've got a list of all these normal variable definitions in MiniZinc.
And then we're going to finish that off with a close brace and in.
And then, we have the expression for
which these local variables are going to be available.
So the parameters, if we introduce a parameter in this we must have a defining
expression because otherwise there's no way to get that parameter value to that
parameter variable.
And basically, we've gotta remember that anything we define in
this let expression is only going to be visible in this expression here,
the one after the in, and not for the remainder of the model.
So let's see how to use let.
So here, we're going to build an explicit array for
each of the points of this particular integer, right?
Which is going to vary from one to psi squared which is the points.
So it's exactly the same expression we did before.
So we take the row number minus 1 times the size plus the column number.
So we're going to build up this array and
then we can just say, alldifferent of this set of values.
Okay, this makes the definition easier to understand,
because we're basically explicitly showing you what's going on.
It's not going to create actually anything different really,
in the underlying solver.
We're just going to make our model easier to understand, and easier to modify.
All right, what other constraints do we need?
We need to define which spot is diggable.
Now a non-diggable spot is a building,
so the buildings are on the even rows and even columns.
So that's where the buildings fit, so we can explicitly say this.
You can say it's not the case that we're digging to a building spot
which has an even row and an even column or we could do this instead.
And basically,
a very useful rule to remember is don't use negation if you can at all help it.
We can just basically push that negation through this conjunction and
get this disjunctive constraint instead which says either the row is odd, or
the column is odd.
And that'll also make sure that we don't hit one of the buildings.
Now, we need to make sure that all the building are covered.
So here's an example of where we can use a predicate, and
we're using some local variables to define that predicate.
So, do we cover a building on the position x, y?
This is what this predicate is meant to ensure.
So if we do cover a building on x, y,
there must be a point within a Manhattan distance of mDist from that building.
So we're introducing a local variable, i,
which is going to guess basically which exit point we're using.
And then we're going to calculate the distance from x, y to this exit point.
So the distance from x, y is just the position x minus the row of i,
the absolute value,.
Plus the absolute value of the y-th coordinate,
the column coordinate for the position we're looking at covering,
minus the column where we find the particular point we've picked.
So we're going to calculate that distance and then, say,
well that distance must be less than the maximum distance that we're
allowed in that model, in our example, which is 3.
So this is a predicate, which is going to test where this position x, y is covered.
And notice we're doing something quite clever here.
We're actually allowing it to pick which point is covering it.
So basically,
there's a pseudo decision here about which point is going to cover it.
Now, how do we apply the constraint?
So let's build basically the even numbers, right,
the huts occur on the even numbers, which is from i is 1 to size div 2 i times 2.
Let's build that array and then we'll say, forall i, j in huts.
So basically, picking all row columns in these even numbers,
we're going to check that it's covered.
All right, so we can see that by building this cover constraint,
we've made it clear what we're trying to do.
And then we're using this cover constraint on each of the hut positions,
improving readability and modularity.
Now finally, the objective we're trying to minimize the total cost of building, so
that's basically looking up the row and column.
Looking at the cost value for digging to that point and minimizing the total cost.
And if we can run their model, we'll find that we can actually cover the bandits
with only three points, if we pick these three points, and our cost is 18.
So, just to show you another use of let-in,
if we go back to the patrol problem we saw a number of lectures ago.
Then we needed that in every day,
the number of soldiers on evening shift was greater than equal some lower bound.
And every day the number of soldiers on the evening shift was less than equals to
some upper bound.
Well, another way we could do this rather than introducing direct common
subexpression based for this, we could just do it the same by using a local
variable to build up that expression that we're going to use twice.
So here, for each day, we're going to build a new local variable,
which is how many are on evening shift which is just this value, right?
The sum of the soldiers are on evening shift on that particular day.
And then we're going to add these constraints
that l is less or equal to u and on is less or equal to u.
Which is going to enforce these two constraints, so we're building a common
sub-expression but we're just using a local variable to do that.
It's often easier than building an array of intermediates,
which is what we did last time.
We were basically adding some global decisions into our model and
then use them in multiple places.
If we're only going to use them in one local place, we just add a local name for
this particular common subexpression and then reuse that local name.
So, let's look at another use of let-in.
Suppose our solver does not support division,
then we can actually define division using multiplication.
because really from a relation perspective,
they're really the same thing, like plus and minus are really the same relation.
I only do it for non-negative numbers because it makes it simpler.
But if that's the case, then if I were to write that x div y = z,
it's really the same as saying this.
That there is a number, if I multiply z times y and
add in some extra remainder, then I would get x.
And I need that this remainder is between 0 and
less than y, so these are two equivalent statements.
We can define division in terms of multiplication by these constraints.
But we need a new variable for this remainder and so
this is a perfect example of where to use a let to introduce that new variable, so
here's a predicate defining division.
So here's the actual arguments we're interested in, x and y and z, and
we're going to introduce this local variable r,
which is going to take a value from 0 to the upper bound of (y)- 1.
So we can't use y here, because y is not a decision, so far.
We have to give it a fixed range, so
we're taking the largest possible value that y could take, -1.
And then, we just write down our constraints, so x = z * y + r,
and r is less than y.
Okay, of course the actual value of y will constrain r as well.
But any time we introduce a local variable,
we should try to introduce very tight bounds on its possible values.
That's going to make our model much more efficient.
So what happens, we should think how does this work with division by 0.
Well, if y is set to 0, then this constraint will fail, right?
Because r has to be 0 or bigger, so this will have no solution and
that's what we want.
Remember the relational semantics says, if we divide by 0,
the constraint should be false and so this division constraint will return false.
What happens with division by negative where you can see that if we
add in a negative number then this will also fail?
And so, it's not really correct because there are,
you can do division with negatives, this version of the predicate is only
meant to work when we're doing non-negative numbers.
So, if we ever make an assumption in our model,
we should really check it using assert.
So we can do that by using a new form of an assertion that is specifically
useful because of things like predicates.
So our division predicate was only really meant to work if the lower bound of y was
greater than or equal to 0.
That is that y was definitely not going to be a negative number.
And so, this is our version of assert which says,
okay, if this test holds then we just give you the regular definition.
Otherwise, we're going to print out an error message and abort, right?
So this is good, it documents the assumption we made about this predicate.
It's only meant to work when y takes a positive value and
it prevents the misuse of this predicate.
So something we've seen in the previous slide is that sometimes we need to know
properties of the variables in the model in order to
build predicates that are reusable.
So, we can look up the possible values of a variable
in the model using these reflection functions.
So lower bound of x is going to return a lower bound
on all possible values of x and upper bound, similarly an upper bound.
Dom(x) is actually going to return a superset of all possible values that x
could take and we've also got versions which can work on arrays.
So lower bound array, just looks across the whole array and
finds a lower bound for all of the elements in the array.
Now we gotta be careful because these bounds are not
guaranteed to be the declared bounds.
They're guaranteed to be correct bounds on the variable we were talking about.
So for example with this little snippet of code here, if we ask for
the lower bound of x, then MiniZinc could return 0.
Because well, x is the result of an absolute value call, so
it's definitely going to be a positive value.
It could return -4, that was the declared lower bound of x, so
that definitely is a lower bound to any possible value that x could take.
Or it could return 2,
because if we propagate this constraint just looking at the possible values
of y between -4 and -2, it means in fact that x has to take values between 2 and 4.
So all of these are correct lower bounds on x.
And you can't rely
on which one of these you get when you're using the lower bound code.
You can probably rely on the fact that we'll always get no worse than
the declared lower bound, if there is one, because it'll be impossible for
MiniZinc to lose that information.
And we'll see that this assertion that we've used here,
this new form of the assertion takes three arguments.
The previous version only took the first two arguments.
And this assert returns the value of the expressions, so we can have
an arbitrary expression here if our test holds, then otherwise it prints out this
string expression and it works just like the other version of assert we've seen.
And so for example,
if we took this model here where y can clearly take negative values and
we tried to run it, then MiniZinc will give us back an evaluation error basically
saying the assertion failed because in this call, this y value could be negative.
And so, that wasn't the way we designed our division predicate to work.
So in summary, let-in expressions are actually a very powerful way of
introducing parameters and variables for use locally.
So we introduce a parameter basically if we want to build
some complicated expression and use it in multiple places.
That's very handy.
Similarly we use variables if we want to build some local decision or
common subexpression, we can use it locally or
we want to make a new local guess, basically a local decision.
As we saw in the covered constraint where we added a point variable which was going
to basically check which point it was covered the hut we were interested in.
Whenever we define local parameters, they must be defined by this expression,
because that's the only way they're going to get a fixed value.
But local decisions don't have to be covered.
And what let-in does is help us modulize expressions and improve the readability of
our model, and basically remove common subexpressions in another way.
