3.1.1 Constraint Programming Solvers

Loading...

En provenance du cours de The University of Melbourne

Solving Algorithms for Discrete Optimization

2 notes

The University of Melbourne

Solving Algorithms for Discrete Optimization

2 notes

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

À partir de la leçon

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

Rencontrer les enseignants

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

One night, the curious Zhuge Liang decided to

study the magical tablet to figure out what made it so powerful.

In doing so, he accidentally broke the tablet and this triggered

the emergence of a powerful time and space tunnel, causing chaos.

In the tunnel, Zhuge Liang met

this celestial old man that originally gave him the tablet.

The celestial old man encouraged Zhuge Liang to fix the chaos he had created and

gifted him a magical dragon that he could call on when confronting difficult problems.

At another point in the space and time tunnel,

Zhuge Liang found himself back in ancient times,

only to discover that the sky hard partially

broken, causing chaos such as a curse causing illness,

extreme heat wave and invasion of monsters.

An ancient goddess, the merciful Nuwa,

decided to save people from this disaster by

using magic stones to patch and stabilize the sky.

The original sky was composed of a grid like structure

of 81 magic stones of nine different types.

There were nine distinct strands in every road,

and nine in every column.

This rule also applied to smaller three by three grids.

Nuwa wanted to know where to put the stones in order to satisfy these rules.

But she found it too difficult to work out and thus sought help from Zhuge Liang.

Zhuge Liang, summoned the dragon of dimensions to seek assistance from the professors.

So the Nine Heavens are broken and Nuwa

needs to fix them and she's gone to Zhuge Liang for help.

So she can use her magical powers to patch

the heavens by moving stones that are fallen and back up to their place.

And there are nine different kinds of magical stone,

and we'll use the numbers one to nine to represent those.

Now, there's a partially broken sky.

Some of the stones are still in place,

but she's going to need to put stones in

all the places which are blank where the stones have fallen out.

But there are some rules about balancing the heavens,

so we need to make sure that the heavens are balanced horizontally -

that is, in each horizontal line there is one of each stone one to nine.

Similarly, they need to be balanced vertically so in each column there needs to be

one of each stone one to nine and

each of the nine individual heavens needs to be balanced.

And each of the three by three subsquares,

we need the numbers one to nine.

So in the end, we have this problem, there's 81 variables,

that's each of the cells and each cell

can take the values one to nine representing which stone we're talking about,

and we had these constraints.

Each row, column and each three by three subsquare contains

exactly the numbers one to nine, no repeats, each number is used.

And that's an assignment subproblem.

So we can build a MiniZinc model to do that,

of course, here's our decision variables in each cell,

which stone goes in there.

Then there'll be some fixed stones, which is the constraints here,

and then we've got our constraint saying well for each row,

they're all different values so they'll take the values one to nine for each column,

and for each three by three subsquare.

So let's step back from that for

a moment, because now we trying to see how we could solve this problem,

how a solver will actually tackle it.

And first of all, we need to understand why is constraint solving hard?

So we'll look at some simple problems here,

and I want you, before I give you the

answer, to think about what is a solution to this problem.

So this constraint X equals 5, Y equals six,

you should have understood is satisfiable,

well, because it's really just a solution written there.

X takes a value of five and Y takes a value of six.

What about this constraint, system of constraints here X equals three,

Y equals four, X is equal to five.

Well, it should be clear that this has no solution because

we can't have X being equal to three and five at the same time.

So that's an unsatisfiable problem.

And here's another set of equations.

This one turns out to be a very simple form.

Basically, we can define Y in terms X and then

Z in terms of Y and X and U in terms of Y and Z.

So if we just guess the value for X like zero,

then we can compute a value for Y which is two,

which will solve the first equation.

Then we can compute a value of Z which is four, which will solve

the second equation, and compute a value for U which is eight,

that will solve the last equation.

So this no longer has that nice behaviour,

because we can define Y in terms of X, Z in terms of Y and X,

but then X is also constrained in terms of Z.

So now, we need to do simultaneous equations solving,

if you remember that from distant high school days,

and in fact, there is a solution here,

you can see basically if we substitute for Y

in here, we get that Z is equal to four, so Z must be equal four.

Once we have that, we can compute that X has to be five from here,

and then we compute that Y is seven from here.

Alright, we can get a bit harder, so here now we don't have just simultaneous equations,

we've got inequalities as well,

and this is getting to be trickier to find a solution.

And in fact, there's none.

If we go through the same sort of stages as before,

if we substitute for Y in this equation here with one,

Z is four, and then we look at this,

and this tells us that X must be greater than or equal to five, obviously,

and this tells us that Y has to be less than or equal to three, but then because X,

Y is X plus two,

we know that Y is greater than or equal to seven, so in fact, there's no solution.

Okay, so why is constraint solving hard,

the problem is conjunction.

The problem is that I need to solve all of these constraints at the same time.

So solving any individual one of them is easy,

but when I put them all together as a conjunction, it becomes hard.

So constraint programming, is an approach to solving discrete optimization problems,

and it's made up of two components: propagation and search.

And basically, we're going to overcome the difficulty of

conjunction using propagation. So what is propagation?

It's a very weak inference method, but the idea is we're going to

reason about each constraint on its own, separately.

And then we're going to communicate the inferences via the variables between the two constraints.

And the nice thing about this is each constraint

sort of lives by itself, it's an inference engine.

We only have to understand that constraint by itself nothing else

and then each constraint can talk to the other via the variables.

We're going to have to add to that search,

which is we're going to have to guess bits of the solution, and that's true of

basically, any discrete optimization

solving approach, we're going to have to guess at some point.

And in order to make this into a viable technology,

we're going to add a lot of engineering, to make the inference very fast.

And then we might add other things like learning to

remember what we already did and not do it again.

So let's have a think about finite domain propagation and see how it works.

And in fact, our problem of fixing the heavens,

which some of you may have recognised as Sudoku as well,

exactly exposes what happens in a finite domain propagation engine.

So if we look at this partially filled in sky,

we can reason what goes in the green cell here?

So we can look at that column and we know the rule about the column

says that every number has to appear at least once,

and so the only possibility missing is three.

So we can do other kinds of reasoning.

So if we look at this nine by nine heaven over here, three by three heaven over here,

we can reason another way around we can say okay we

know that three has to occur in that heaven at some point.

And let's look at which places it can occur and we can see that this three here,

wipes out all the top row,

and this three here wipes out

the third row which means that the only place that three can occur is there.

So that three has to be there.

So we are basically making reasonings about

each of the different possible values that could happen.

So we can do more complicated reasoning,

so let's look at this row here and intersect it with a column.

So if we think about that green cell,

what could possibly go there?

Well, if we look at the row down the bottom,

the only possible values left over are one, two, and three.

And if we look at the column well there's a three in there.

So that leaves only one and two leftover as the only possible values there.

We can do similar reasoning here, again the only possible values here are one, two,

and three because of the row,

and because of the column, that only leaves one and two.

And this allows us to do a more complicated kind of reasoning,

so we look at this row here and everything is

almost filled in we've got what values could go here.

Well, we know that there can only be one two and three but in fact if we look at

these two entries over here we see that one and two must occur in these two positions.

So we know that one and two are taking up those two positions,

so the only thing that can occur in that green cell is three.

So you can think about if there is any further reasonings we can do from this thing.

And there's actually quite a few,

and we can think about representing all the possible values left over in every cell.

In fact that's exactly what the constraints are always going to do.

It's going to keep track of, for every one of the decisions,

what are the possible values that we can do.

But we haven't solved our problem.

So we now need to make a choice.

Now, one way to do this is to

choose one of the cells with the least possible number of values.

So that would be that cell there,

right, it only has two possible values,

that's one of the two cells which only has two possible values.

So this means that we're making the least amount of choice.

So now we're going to guess one of those values,

let's say we guess one.

Once we do that, we're going to get propagation, which is

going to change these other cells.

So fixing one of course fixes this to be two,

and then you can see we can remove one from these entries up here,

we can move two from these entries here, etc., etc.

So you can see that fixing one removes some values here, it also

fixes this two which causes more removal of values.

So we have this propagation of information.

So that leads us to more, now we have to search again so we

pick now another variable which has the least possible values, let's say this one here,

and we'll set it just to its least possible value for a moment

and we can see we get more propagation here just the direct propagation,

removes some values four from these cells which were affected by that.

And we can keep going,

it can pick the next value here,

pick a value we get propagation here,

and we get other kinds of propagation, further propagation.

So here once we know it's one and four here we know they can't be here for example.

And so we can see that this reasoning keeps on going.

Okay, so we can also reason up here once we pick that five, we know that two,

six, and nine must be in these three cells so they

can be in any of these cells around here for example.

And if we continue that after

23 guesses and reasoning steps we actually reach a solution.

Actually, we never make a mistake in this example.

So that's not bad really,

for 81 possible cells to fill in,

although some of them are filled in the beginning,

we make 23 guesses,

none of them are ever wrong, and we get to a solution. That's very very quick.

So in summary, what's happening in

a constraint programming solver when it solves this kind of problem?

We examine each constraint in turn and

the constraints remember we were looking at were these all different in a row,

in a column or in a three by three subsquare.

We reason about the possible values of

the variables in that constraint, we try to reduce those possible values.

And we just keep doing this until no further reduction is possible.

So this is this propagation loop.

This was why its propagating values from one to the other.

Then we'll get to this point, there's no further reduction we can do,

we have to search, what we do is we make a decision which is just

really a guess then we propagate again.

Now, three things can happen really.

It can fail so we can find that there is no solution after we make that guess,

in which case we have to backtrack undo that last guess and try a different value.

It can just propagate until nothing and that means you have to keep going for

the search or it could propagate so that

no variables will lift all the variables were fixed.

In this case, we've actually solved the problem and we can print out the result.

So we're going to look into constraint programming in detail in this module,

and we're going to start by looking about domains and valuations,

then constraints and propagators, propagation engines,

then how we do optimisation using this technology, advanced search strategies,

and they will look inside how we build some of the complex global constraints.

And one of the powers of constraint programming is that we

can have very expressive global constraints,

which we've already seen their power and modeling and this is how they work internally.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play