3.1.3 Bounds Propagation

Loading...

From the course by The University of Melbourne

Solving Algorithms for Discrete Optimization

6 ratings

The University of Melbourne

Solving Algorithms for Discrete Optimization

6 ratings

Discrete Optimization aims to make good decisions when we have many possibilities to choose from. Its applications are ubiquitous throughout 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 on the use of scarce or expensive resources such as staffing and material resources also allow corporations to improve their 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, these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students who have completed Advanced Modelling for Discrete Optimization. In this course, you will extend your understanding of how to solve challenging discrete optimization problems by learning more about the solving technologies that are used to solve them, and how a high-level model (written in MiniZinc) is transformed into a form that is executable by these underlying solvers. By better understanding the actual solving technology, you will both improve your modeling capabilities, and be able to choose the most appropriate solving technology to use. Watch the course promotional video here: https://www.youtube.com/watch?v=-EiRsK-Rm08

From the lesson

Basic Constraint Programming

This module starts by using an example to illustrate the basic machinery of Constraint Programming solvers, namely constraint propagation and search. While domains represent possibilities for variables, constraints are actively used to reason about domains and can be encoded as domain propagators and bounds propagators. You will learn how a propagation engine handles a set of propagators and coordinates the propagation of constraint information via variable domains. You will also learn basic search, variable and value choices, and how propagation and search can be combined in a seamless and efficient manner. Last but not least, this module describes how to program search in MiniZinc.

3.1.1 Constraint Programming Solvers13:13

3.1.2 Domains + Propagators18:59

3.1.3 Bounds Propagation21:58

3.1.4 Propagation Engine21:52

3.1.5 Search25:32

3.1.6 Module 1 Summary4:38

Meet the Instructors

Prof. Jimmy Ho Man Lee
Professor
Department of Computer Science and Engineering
Prof. Peter James Stuckey
Professor
Computing and Information Systems

Dragon veins are precious,

so Nuwa wanted to avoid removing them.

To appease the giant turtle,

she offered him a position as Prime Minister of the sea.

In return, the turtle agreed that it would only move its foot

to the outermost dragon veins in four different directions.

Zhuge Liang observed that in the west,

there was a colossal mountain that was tall enough to support the sky.

This meant the western foot could be moved to the north for extra stability.

The stability of the sky in the north could now become less challenging,

as it was sufficient to let the stability line pass between the two feet.

Nuwa had to reconsider the impact of this to make sure the sky would be stable.

Zhuge Yang summoned the dragon of dimensions for assistance from the professor's.

So Dragon Veins are precious

and Nuwa looking at the result of trying to overcome the Great Turtle's challenge,

it's a bit unhappy that so many Dragon Veins have to be removed.

So, she's going to appeal to the Great Turtle and offer him

premiership of the oceans to make the challenge a bit simpler.

So, the new challenge that he comes up with is that he's going to

restrict himself to only pick one of the extreme Dragon Veins,

one of the furthest runs away from the North Pole,

other than northernmost, the southernmost, easternmost or westernmost.

And he's going to have two dragon legs on

the extreme intersections with the other extreme Dragon Veins.

So, you can pick the northern, the southernmost Dragon Vein,

the westernmost or the easternmost,

and two turtle legs will be put down.

And now the old stability requirement was the Dragon Vein that he picked had to

have an intersection with another Dragon Vein such as

the turtle leg was actually on the stability diamond.

He's going to make that much simpler now.

And the only requirement is that when he picks Dragon Vein,

these two turtle legs will be put on the most extreme Dragon Veins available,

and the stability diamond has to cross in between those two turtle legs.

So, hopefully this means that Nuwa will be

able to get away with it discarding much fewer Dragon Veins.

So, here's the problem that she's trying to solve.

We have the possible vertical Dragon Veins,

that's domain D of X,

the possible horizontal Dragon Veins,

that's the domain of the variable Y,

and note that the Dragon Veins are only integer positions.

And we need to find the largest set,

subset of D of X and the largest subset of D of

Y such that we have this stability condition,

the new stability condition holds.

And that is if we look at the minimum value for X,

then it has to exist an integer value of Y in between

its minimum and maximum values, note that Y may

not actually be in this set domain of Y,

just has to be in between the minimum and the maximum of the set D prime of Y,

such that our stability diamond constraint holds.

And then we have to do the same for the max value that X can take,

and we to do the same for the min and the max value that Y can take,

we have to find corresponding values for X.

So, the idea of how we actually support

this is we're going to scan the horizontal Dragon Veins from north to south,

and stop when we find the new stability requirement can hold,

and we eliminate the Dragon Veins along the way,

but once we stop, we've actually found the Dragon Vein,

which satisfies the condition that the Great Turtle demanded.

So, if we look here,

if we look at the top-most Dragon Vein and we look at

the area between the extreme Dragon Veins available,

we'll see that it does intersect the stability diamond,

so we can stop immediately.

If we look at the southernmost Dragon Vein and we look at the area

between the most extreme Dragon Veins from east to west,

then it doesn't intersect the stability diamond,

so that one has to be removed.

So we go down to the next southernmost one.

We again look at this area here and we find it doesn't

intersect the stability diamond, and so we're going to keep it.

Then we're going to look at the westernmost Dragon Vein.

We're going to sit,

look at the area in between the new,

as it turns out, southernmost and northernmost Dragon Veins that we have left over.

And we find that there's no intersection with stability diamond.

We're going to move into this one.

Again, there is no intersection discussion, but when we get to this one,

there clearly is an intersection with the stability diamond,

so we can keep that Dragon Vein.

And then we'll do the same from the east.

We look at this one here, and there's no stability diamond intersection.

When we get to this one there is, and now we're finished.

And we can basically see that we've enforced this Great Turtle challenge,

because whichever of these extreme Dragon Veins that he picks,

there will be an intersection with stability diamond available.

So, now, Nuwa was able to find

two intersections on the chosen Dragon Veins so that

the new stability required is satisfied,

whatever choice the Great Turtle makes.

So, what we've seen here is an example of bounds propagator.

So, bounds propagator is propagator that

only examines the upper and lower bounds of the variable domains.

And this is advantageous because it only deals with 2n pieces of information,

where n is the number of variables in the constraint.

So, remember, an arbitrary of domain can still be very very complicated.

Even a single variable can have a large domain with lots of holes in it.

But here since we're only dealing with the upper and lower bounds,

we are only ever talking about two pieces of information.

And just as we can have a strongest domain propagator for a constraint,

we can have a strongest bounds propagator for constraint,

and the strongest bounds propagator is meant to remove all the possible

lower and upper bounds of the current variable domains that don't find a support

between the bounds of the other domains in C. And that notion of support

is just what we saw for the specific stability constraint,

we can write it more generally here.

We look at every variable in this constraint,

and we look at it taking its minimum value that's possible for it's current domain.

Then there has to at least exist a value for every other variable Vj,

for every other variable Xj in between the bounds that Xj can take.

Now notice, this value may not actually be in the domain of Xj,

but it's in between the upper and lower bounds.

And we have to be able to pick all those values such

that the resulting valuation is in the constraint.

So it satisfies the constraint.

And we have to do that simply for each of the maxs,

and if we can do that for each variable and for each of the min and maxs,

then we've got a domain which is Bounds(Z) consistent with this constraint.

So, notice it's called bound(Z) because we're talking about integer values here.

We're going to come and look at a different notion of

bounds consistency slightly later on.

So, let's write down the bounds propagator for

the constraint X is equal to the absolute value of Y.

It's a slightly simpler version than the stability constraint we talked about.

So here is an example of one possibility.

So, we are going to take the current domain of X and we are going to intersect it

with this range from zero to m. So,

basically, we look at the maximum possible value that Y can

take and then minus the minimum possible value that Y can take.

Those are the things that are going to contribute to

the largest possible value of the absolute value of Y.

We'll take the maximum of those,

and then that will give us this range zero to m because, of course,

we know that X can only be positive because it's the absolute value of something.

So this is going to reduce the values of X so that we only lie within

this range of the maximum possible value that absolute value of Y could take is zero.

And what are we going to do with Y?

We're going take the current domain of Y,

and we're going to intersect it with the maximum value of X,

which gives us the maximum possible range of

absolute values, minus the maximum value up to the maximum value of X.

So, that seems like a fairly reasonable propagator for this constraint.

So, is it the strongest bounds propagator possible?

So, let's look at some problematic examples.

So, imagine that X takes the values from minus 7 to

4 and Y takes the values from minus 5 to minus 3.

Then if we do our calculations here,

we get minus 7 to 4 intersected with 0 to 5

and we get 0 to 4 as the new domain.

But, really, we only want 3 to 4 because if you

think about the absolute values that you can get out of Y,

they can only be from 3 to 5 because that's the only possible values we can get out of

the absolute value of Y.

Y will intersect minus 5 to 3 with this range of minus 4 to minus 4,

and we'll get exactly the perfect answer,

minus 4 to minus 3.

So, if we look at that graphically, here's the domain of X,

and here's the domain of Y,

always in the negative part.

And, really, that's the only part of the constraint which is feasible,

that little chunk there,

and so what we want to get for bounds consistency

is to remove the domain of Y up to there,

which is what actually happens.

But we want to move the domain of X to this value, which doesn't happen.

Alright, let's look at one more problematic example.

So, here, we have domain of X is 3 to 5,

and domain of Y is minus 4 to 1.

And if we do our calculations and the domain of X gets updated,

we intersect it with 0 to 4.

We get 3 to 4, which looks pretty good.

But we look at Y, we get this minus 4 to 1 is intersected with minus 5 to 5 because,

of course, the maximum value that X can take is 5.

So, that's really that range of possible values and nothing changes.

But, clearly, we know now that since X is taking a value of at least 3,

then the absolute value of Y has to be at least 3.

We want to get this domain.

So, if we look at this graphically, here's the domain of X,

and you can see intersects two different parts

of our absolute value constraint. And here's our domain of Y,

and really, we want to make sure that we get

this is the only thing in the intersection, this part here.

And so we'll update the domain of X correctly,

but we weren't updating domain of Y.

We want to get this value here, minus 4 to minus 3.

So, let's try and write down the strongest bounds propagator

for this constraint X is equal to the absolute value of Y.

So, we're going to have to consider two cases for the domain of X.

So, is zero in the domain of Y?

Does zero's upper and lower bounds extend on both sides of the zero boundary?

If that isn't the case, then, basically,

we can just take the minimum and maximum possible absolute values of Y,

and we can just use that to intersect with the current domain of X,

that's going to be correct because we're only on one side of the boundary.

Otherwise, we can't really do any better than we had in our original propagator.

So, since we know that Y crosses the zero boundary, zero will be in,

and we can just take the largest possible absolute value of Y,

that's M, and intersect X with that.

Let's look at the case for Y. Well, if the maximum possible value of D of X is negative,

then obviously, we should give back

an empty possible values for Y because the constraint has no solution.

The absolute value of a number is definitely not a negative number.

What if the minimum is greater than or equal to zero?

Then what we're going to do is basically take the X domain and also negate it,

sort of flip it across the axis,

sort of give us the reflection of the X values onto the Y argument.

And we're going to take the convex whole of that.

So, just take the bounds of that and intersect them with the current value of Y.

So, otherwise, we can just do what we did in the original case.

We just take from the minus the maximum possible of D of X to the maximum possible value.

That's just a big range,

and we just keep all the values of Y, which were in that range.

So, let's have a look at our bounds propagator in action now.

So, here, if we take this minus 7 to 4,

we intersected with 3 to 5, we get 3 to 4.

And we were hoping for and minus 5 to 3.

This still uses the old,

the simpler version but already gave us the right answers.

So, that has fixed the first problematic example.

If we look at this example, we take X,

we intersect it with 0 to 4 because Y is on both sides of the boundary, so we get 3 to 4.

But, now, we take the hull.

So that's the original values of Y we intersect with.

This is the original values of X negated.

And then negated part,

and we can see that that only intersects in this area from minus 3 to minus 4.

And so that's the bounds that we get out.

Similarly, if we do 3 to 5 and minus 4 to 4 and are very similar calculations,

so nothing different happening here.

But, now, if we intersect these minus 4 to 4 with this,

then we're going to hit from minus 4 to 4

and we're going to get back no change.

So, this is an example where the hull hasn't been able to help us because,

basically, 3 intersects on both sides.

So, our new stable pillars problem was we can build a very simple for-loop to do that,

but could we do it better in terms of complexity? That's a good question.

In other words, what's the strongest bounds propagator for the stable pillars problem?

Absolute value of X plus the absolute value of Y equals 10.

So, one thing is,

and this will happen by default in MiniZinc.

This constraint, we don't want to build a propagator

for every new constraints we come up with.

This constraint will be broken down into three, into XA is

the absolute value of X, Y is the absolute value of Y

and then making sure that their sum is equal to 10.

And so our challenge is,

can we write a better tailored propagator for this constraint directly?

Or just if we take the bounds propagators,

the strongest bounds propagators for each of those,

will we get just as good a result?

So, that's a question we leave to you.

Alright, so we've just introduced bounds propagation,

so hopefully, that was made everything easier.

So, what do we think the complexity of

this linear equation strongest bounds propagation is?

We know for domain propagation, it's NP-hard.

What about for bounds propagation?

Well, it's still NP-hard unfortunately. Alright,

but the complexity of linear inequality bounds propagation is linear.

Right. So, that was even for domain propagation.

In fact, bounds propagation and domain propagation are

the same for the inequality version.

So, we're going to relax our notion of bounds propagators to have a simpler version,

or a more relaxed version.

So, this is the real bounds, real propagator,

and it's allowed to move values,

the upper and lower bounds of a current variable.

If there's no real number supports between the bounds of the other domains in

the constraint c. Now we can get our notion of bounds R consistency,

which is basically exactly the same as the bound Z consistency,

except that now the values that we're picking here these Vjs are in between the range,

but they're real values.

And of course our constraint, we have to relax,

so these assignments that we get here have to be

the solutions of sort of real relaxation of this constraint.

And well for constraints that we're going to look at,

that will be fairly straightforward for other constraints,

it might be hard to work out what the real number relaxation of them is.

But we look at arithmetic constraints where it's

very easy to just think all the variables are real,

and the real relaxation is just mainly that interpretation.

So, we can look at the linear inequality propagator.

So, this is the sum ai Xi is less or equal to b.

And actually the bounds propagation rules whether it's bound Z or bounds R the same,

are all just the same thing.

We just take the current minimum,

it doesn't change obviously,

we're doing the case where the ais are all positive.

So, really this can only put a new upper bound on an Xi.

And to work out the new upper bound,

we just take this bound value,

we subtract out all the lowest possible values that the other variables can take,

which is this aj by the min of the D of Xj and divide it by ai,

the coefficient for the variable we're changing.

And that's a new possible upper bound,

or we can also do this floor,

because we know we have to get an integer value.

So, if we use our linear inequality propagation on this constraint here,

with original domains from zero to nine,

we can calculate the new upper bound.

So we know that W is less than well,

we know that these, each take no values.

Right. So the lowest.

So we take the nine,

we do three quarters times a minimum of D(P) which is

zero minus two quarters of the minimum of D(C) which is also zero.

We're basically just going to get W is less than nine on four.

Right? So, it's just going to round it to zero to two.

And similarly for these other constraints here,

because the lower bounds here are all zero these expressions are all zero.

We're basically just saying that P is less or equal to nine divided by three,

which just gives an upper bound of three.

And similarly C gets an upper bound of four.

Al right what about a linear equality.

So, because we know if we're doing bound Z propagation,

we get into trouble, it's going to be hard.

We're going to do it much simpler than that.

We're just going to use basically the same formula we have here for the upper bound.

Right. So, this is less or equal to,

we did exactly this formula,

and we're going to do basically the opposite formula for the lower bound.

And really this is the same as treating this constraint as two inequalities.

Really we're just implementing this linear equation as two inequality propagators.

And if we do that, when we get rid of all things,

and also it actually maintains bounds R consistency.

So, if we look at our original constraint we looked at for

domain propagation with these range domains to begin with,

then we try and find what's the smallest possible value that 3Y+5Z equals minus five.

Right. So, if we're looking at what's

the smallest possible value of this expression using the domains,

we'll get minus five is the smallest possible value, its largest, is 16.

We're going to intersect that with D of X and it's going to make no difference.

Then we think about, what's the smallest possible value that X-5Z.

Right? Which is this expression which is equal to 3Y can

take and the smallest possible value is minus eight and the largest is 12.

And then we can think about,

what's the smallest possible value that X-3Y which is what's going to be equated to 5Z,

is and it's largest possible value.

And here we're actually going to get some propagation.

Right. Because we know that 5Z is greater than or equal to minus four.

We know it's actually Z is greater or equal to zero.

And that's the only propagation that we get out of our bounds propagator.

Which is very different in the case for the domain propagator for this linear equation.

But of course, it's much, much cheaper to do.

So, an exercise is to think about the domain or the bounds propagator,

and the domain propagator for this multiplication constraint.

So, we have a multiplication constraint X equals Y times Z. X is taking

values from zero to five and Y is taking values

minus two to three and Z is taking from one to six.

So, for domain propagator it's easy enough.

We basically just have to look through every possible solution of this constraint,

with these propagator values,

and we'll find this is the domains we'll get out.

All right. Basically since we are

multiplying by a positive number here to get a non-negative number here,

we only have non-negative numbers of possible multipliers.

Okay. What about if we apply on this domain now?

Again, it's almost the same.

Right. What would the domain propagator return us?

Well, here we can do a bit better basically,

because if we think about the minimum possible,

the maximum possible value that Z that can take

six and the minimum possible value that X can take three,

it means that Y has to be at least one,

because it has to be bigger or equal to half.

So, we get some strong propagation.

So, when we're building propagators,

they just have to remove as many values as possible, and execute quickly.

They don't have to be domain propagators,

they don't have to be bounds propagators,

the strongest bounds propagator,

or the strongest bounds R propagator.

In the end, they just have to be efficient,

and they have to eliminate things as much as they can,

because it's more important that they're fast.

So, it turns out that almost no propagators will

be the strongest possible propagators, domain propagators.

And even the strongest possible bounds propagators are not that common.

So, once we get to complex constraints,

we typically are just doing as much propagation as we can do fast,

and not worrying about finding all possible propagation that can be done.

So, in summary, we've looked at domains and propagators.

Domains are representing remaining choices.

And basically they are the communication channel for constraints.

So, propagators implement the constraints and they

talk to each other by changing the domains of the variables they have in common.

So, propagators incur the constraints and they map domains to smaller domains.

And there's a number of different types of propagators.

So, domain propagators are the strongest possible.

They're just keeping all the solutions which are leftover.

Bounds propagators are any propagator,

which only considers bounds.

And we can have the strongest possible bounds propagators,

or just some other bounds propagator.

And there's always this tradeoff when we're building propagators, or using propagators,

indeed, we can choose which propagator to use sometimes.

Is the speed of the propagator versus the inference strength.

And because propagators are run many millions of times in a complex problem,

then often speed is the key requirement.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play