3.1.5 Search

Loading...

From the course by The University of Melbourne

Solving Algorithms for Discrete Optimization

4 ratings

The University of Melbourne

Solving Algorithms for Discrete Optimization

4 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

Shennong Shi said that people were extremely vulnerable to disease.

He therefore wanted to make medicine to heal

any kind of disease using herbs from a heavenly garden.

Nuwa led Shennong Shi to this garden and showed him a herb cabinet

with 100 drawers divided into 10 rows and 10 columns.

In each drawer, there were five types of seeds associated with five different elements.

Pouring the seeds out of the drawer made the five seeds grow

into five separate paths with corresponding herbs.

Shennong Shi poured these drawers one by one and walked amongst

the herbs whilst tasting and collecting them in order to compose the medicine.

There were three requirements for composing this medicine.

One, the elements of the seeds in adjacent drawers in

the same row needed to have generative or destructive relationships.

Two, the seeds in the first drawer could not be associated with metal,

and three, at least one and at most two seeds

in a column had to be associated with metal.

The same requirement applied to the earth element.

After trying different seed combinations,

walking along several paths,

and tasting a variety of herbs,

Shennong Shi found it difficult to arrive at a suitable composition.

So he asked Zhuge Liang to help him speed up the process.

Zhuge Liang summoned the dragon of dimensions for assistance from the professors.

Nuwa has a 100-herb cabinet made out of 10 rows and 10 columns of drawers.

Each of these drawers has five different seeds for five different herbs,

and the five different herbs have different properties: metal,

wood, water, fire and earth,

and she's instructed Shennong to build a herb garden.

So how he does this, he's takes out each draw one after the other in

turn and sprinkles out to get five seed patches, five herb patches.

And then he'll move to the next herb patch and take out the next drawer,

he'd pick a herb patch to go to,

take out the next drawer, and sprinkle the seeds out of it.

He will get five more herb patches,

he'll move to the next one, sprinkle out the next drawer, etc.

And the aim of this is that he has to build a prescription which requires

100 herbs or one herb from

every drawer but there are certain constraints on that prescription.

So he's going to build this magic prescription.

So, the constraints on this are,

when he picks a herb from this drawer and the herb from this drawer,

there has to be relationships between their properties.

So, there has to be either a generative relationship,

so metal goes to water.

The outside circle is the generative relationship,

or destructive relationship which is this red lines inside the circle.

So for example, if he has a herb with water followed by herb with fire,

then that's correct, that follows the generative relationship.

And it goes, water followed by metal,

then that's neither generative or destructive, and so that's not allowed.

And this magic condition occurs for every pair of drawers across the row.

So, there's also a special condition for the first drawer.

So the first drawer he picks out,

he can't use the herb with the metal property.

And there's a condition for every column.

So the herbs that he picks from every column of the cabinet,

have to have at least one and at most two metal and earth in the whole set of choices.

So this set of column choices is correct.

You can see that it has two earth and it has one metal, so that fits.

This one is incorrect because it has no metal.

So, this is our magic herb maze problem.

There's a hundred herb drawers,

each with herbs of five different properties.

And he's going to open the drawers in turn to lay out this magical herb maze.

And his aim is to grow and find the magical prescriptions such that in every row,

all the adjacent drawers,

chosen herbs, have to respect this generative or destructive relationship.

In the very first drawer he pulls out,

he can't choose metal.

And for each column of drawers that he uses in the prescription,

it has to be at least one and at most two metal and earth property herbs.

Okay, so a naive approach to this would just to be,

pick from each of the 100 drawers one of the herbs,

and check all the constraints are satisfied.

And if they're all satisfied,

then he's found his magical prescription,

and otherwise, he just has to try another recipe.

And of course, the problem with this is there are

five to the hundred different recipes to try.

So this is called Generate and Test.

You just generate a solution and then check all the constraints,

and is obviously highly impractical.

So, can we do a better approach?

So let's try Chronological Backtracking Search.

So what this is, is we're going to enumerate the decisions one at a time,

and once we've made a decision,

we're going to check that the constraints about

that decision are compatible with all the previous decisions.

And basically, we'll keep going considering

alternative choices if the current choice violates some constraints.

So if you get all of these decisions,

all the 100-herb drawer decisions made with no incompatibility,

then a solution has been found.

But if at any stage,

it runs out of decisions, there's no decision made.

So you have to revise the last decision and backtrack and make a different choice.

So let's have a go at Chronological Backtracking Search.

So, in the first drawer,

we pull it out and we have our five seed patches.

If he chooses to go to metal,

he'll find that the second constraint,

that the first drawer can't be metal is violated.

So we can try going to the second patch which is wood.

And then if it goes to the second drawer,

it pulls it out, if he tries to go to metal,

he'll find that neither the generative or the destructive relationship holds,

so that can't be allowed.

If he sees wood again,

the same problem, that row constraint is not satisfied.

Water is not satisfied either.

So fire is the first place where this is satisfied.

So we can go down to the first drawer in the second row and pick metal and that's fine.

We're trying to pick metal again in the next row.

Of course then, there's no other row constraint is violated.

But if we get to wood, then the row constraint succeeds, so that's okay.

Now, we come down to the last row in the column.

The last row and we can start to look at column constraints.

If you tried to pick metal here,

that would violate this column constraint.

We'd have no earth in this column,

so that's no good. Same with wood.

And in fact, all of those except for earth is the only choice we can make here.

And then we get to the last drawer and we see, okay,

we can definitely pick metal in terms of the row constraint,

but that violates the column constraint,

and so we can't do that.

We can't pick this for the row constraint.

We can pick this for the row constraint but it violates the column constraint.

We can't pick this because of the row constraint.

And earth, we can't pick because it also violates the column constraint.

So we have to backtrack and make a different decision.

Now, we come back up here,

there's no other decisions to be made,

so we have to backtrack even further.

So here, we can make a different choice.

We could use water,

that would succeed with the row constraint,

and we can come down here and pick metal,

at least most one, and that violates the column constraint, so that's no good.

We could try wood, that would also violate,

in fact, all of these would violate except for earth.

And now, we try to make our last choice.

Well, we can try and pick metal

but that violates the column constraint here, you can see this.

There's no earth in that column, and so that's not good.

This one violates the row constraint.

In fact, all of them violate the rest of constraints and we have to backtrack.

So, we've seen this part of the Chronological Backtracking Search.

And if we keep going and do that,

we'll eventually find a solution down here.

You can see we've looked at lots of different possibilities,

but we eventually do find a solution down here on this tiny example of

the herb garden problem with just three rows and two columns.

So, what we've actually been doing is solving a MiniZinc model that looks like this.

We have, here's our choices.

Here's our rows and columns,

and we're picking for each draw a element,

a different element as the property of the herb that we want.

And we're enforcing this compatibility constraint

across the rows so that if you are in i,

j, and position i,

j plus one, so that's next to it in the row,

then, we have to satisfy

this compatibility constraint of destructive or generative relationship.

And of course, we need that the first herb can't be picked to have the metal property,

and then, we have a column constraint which basically says,

if we add up the number of times that metal and earth appear in the column,

each column, it has to be between one and two,

and then, we can have some output to show the result.

So, this is basically a search tree.

So, this is what's actually happening inside

is searching for a solution by going through this possibility.

So, what we've actually done here is a kind of checking partial satisfiability.

So, we assume that a variable,

once it takes a fixed value,

once it has only one value left in it's domain, it's called fixed.

And whenever we find a constraint,

has all of its variables fixed then,

we can check it because it's easy,

once I have a constraint with all of its variables fixed,

then it's easy to check whether satisfied or not.

And so, this check C, D is basically a partial satisfiability check

sensitive constraints and a domain D, just looks through every constraint and says,

if all the variables in this constraint are fixed by this domain, then we can check.

If it's satisfied then that's fine.

If it's not satisfied, we know that there's no solution.

So, we can immediately return false, a false domain.

So, we otherwise return a domain here which is normally will just return the same domain.

So now, we defined the check function where we can define a basic backtracking search,

which takes a set of constraints and a current domain.

So, if all the variables in the constraints are

already fixed then we know that check will actually return that right answer,

either return unsatisfiability if one of the constraints doesn't

have a solution, otherwise D will basically represent a solution,

and we can just return that domain.

Otherwise, we're going to pick a variable which is not fixed in the current domain,

and for each possible value in its domain.

We're going to build a new domain where basically we fix that variable to that value,

every other variable stays the same.

And we're going to call check on this new domain.

So, if this check doesn't fail so we don't

get a failure, then we're basically going to continue our search.

So, we're going to keep going now with this new domain with the X set to

D. And if this returns not a false domain, if it returns,

this is either going to return a false domain,

which means that this whole battering search fails or it's going to return

a solution basically because all returns come from this line here.

If we try every possibility for X and none of them,

they all return a false domain,

we basically return a false domain.

So, we found no solution for this part of the search.

And that's exactly the algorithm we actually run, previously.

So, when we're doing this search, the variable orders,

so this choose which variable we choose,

makes immense difference into the size of the different search trees that we could get.

So, there's lots of different possibilities that we could make in this choice.

So, the simplest way is just to choose the variables

according to the input order and that's what we did in our example here.

We basically, we take the first draws in order,

basically across the cabinet.

But there are many other possibilities.

We can base it on the variable domain size,

or how many possibilities are left for this particular variable,

or we could take the variable which has

the smallest possible value or the largest possible value, for example.

So, this value choices so,

when we have to pick for each,

we look at the domain of X.

So, we picked the variable X, we look at the value in the domain

the order of those choices also makes a difference.

So, we could pick just the simplest orders from min to

max and that's what we saw in our example,

we would always try metal then wood, et cetera.

We go across the value using the order.

This affects the left-right order in the search tree and it's useful because

good choices can move our solution branch to

the left of the tree which is going to help us find a solution quicker.

So, it's very important for just looking for a single solution,

but it's not very important for all solution search,

and I'll let you contemplate that for a while.

We'll come back to it in optimisation.

It's even more important, this value choice, for optimisation.

So, we know that we built this propagation engine,

we want to use that inside our search.

So, if we use constraint propagation,

it's basically effective reasoning about removing

values that are guaranteed not to be part of any solution.

What this will give us is smaller domains and that'll give us a smaller branching factor,

the search nodes will have less choices to make and we'll get a small search tree.

So, what a constraint programming solver actually does,

is more than backtracking search,

it basically performs Constraint Propagation at

every search node before it tries to choose the next variable.

So, let's do our same example using Propagation and Search.

So, here are our six different draws and there are variables and their initial domains,

which of course, all the five different properties.

And let's start by doing propagation before we make any choices.

Before we make any choices,

we know that we can't choose

metal in the first case so that would just disappear from the domain.

All right, there's nothing else that will happen for propagation.

So, we'll make another choice.

So, let's say we put wood there.

Now, amazingly, once we put wood there,

lots of other choices are reduced.

In fact, so we find that because we have to have a metal and an earth in this column,

then the only two choices for

these columns are metal and earth and that's going to mean that,

because of the generative and restrictive relationships,

the only possibilities in these two places are metal and wood,

and that's going to actually force an earth to be in that position there.

Because otherwise, there's no other position to put Earth.

So amazingly, once we make just this first choice,

the domains shrink drastically to this level here. Alright,

so, when we get to the next decision,

in fact there's only one left and that is,

just to fix it to its fixed value. So, that will be fixed.

Then, when we get down here, we only had these two choices,

metal and earth, and so we can take our first choice there.

Once we do that, propagation will in fact fix the entire rest of the variables.

And so now, when we get down here,

basically there's only one choice left, which is wood,

and we get to here, there's only one choice left which is earth,

and when we get to here, there's only one choice left which is metal.

But we've actually found a solution.

So, you can see a very drastic difference between the basic backtracking search,

which we saw a large search tree to find the first solution,

and Propagation and Search which basically has driven us straight to

an answer for this small example of the herb draw.

So, how do we describe that in algorithms?

So we have this search with propagation.

And we have old propagators which, remember,

we know are at fixed point,

and new propagators which may not be at fixed point,

and here's our current domain.

So of course, the first thing we do is we run

our propagation solver on these propagators.

Now, if that detects unsatisfiability,

then we basically know that we've got no solution.

We have to return that domain.

Or if it detects that all of the variables are fixed,

then we also know that isolv will have checked all those constraints, and so,

we have a solution, and we can return the domain representing that solution.

Otherwise, we get to our search choice.

So, we pick a variable which is unfixed,

and again, we'll just go through every possible domain for that variable.

And we'll think about it this way,

all of the propagators now are old because we know we've just put them at fixed point,

so they're all at fixed points,

so they go into the old category,

and let a new propagator for X equals D,

which will have the effect of changing the domain D,

to fix X to that single value,

but that'll also work well with our isolv which will

then wake up all the other constraints that need to be propagated,

that need to be looked at, to get us the final fix point result.

So, we're going to do, we're going to go around that loop,

if we get back a result which is not a false domain,

it actually must be a solution,

and so, we can just return it.

Otherwise, we get our false domain,

we'll keep going around this loop.

If all of these domain values give us a false domain,

then the whole thing should just return a false domain.

So, that's propagation with search.

So we have a variation.

In fact, this is more commonly what's actually implemented

in constraint solvers of binary branching.

So here, exactly the same thing,

we start off by running our propagation engine.

If we get a false domain, we return it.

If we get a single domain,

where every variable is fixed,

we return it because it must be a solution.

Otherwise, we're just going to look at our current domain and find a pair of

constraints which are implied by the current domain, alright?

So, we know that this pair,

this disjunction is implied by the current domain.

This is our binary search,

and we'll try either adding a propagator for the first constraint,

and looking for a solution.

If that succeeds, then we're fine, we return it.

Otherwise, if it fails returns a false domain,

then we'll try adding a propagator for the second constraint in this binary choice.

And if both of those fail,

then we return the false domain

otherwise, if one of them succeeds,

we'll return the solution it found.

So, binary branching, we don't try every possible value in the domain,

we just basically split,

we have two constraints which split the domain into two bits.

So, this choice of the split for the search is crucial.

So usually, we choose a variable with a domain of X greater than or equal to

one just like we did for the normal backtracking search,

and then we'll choose a value, d,

in the domain of X and add this binary split.

So, we say X equals d or X is not equal to d, and that's called labeling.

And you can see, that's very analogous to what we did in the backtracking search where we

just basically tried every possible value for X and fixed it to that value.

But here, interesting thing is,

once we set it not equal to this value,

we might actually get more propagation than we did in the basic backtracking search.

Another possibility is just to pick a value in the domain of X and

add X is less than or equal to d or X is greater than or equal to d plus one,

and that's domain splitting.

So we're basically splitting the domain of X into two,

and you can see that that can give you very different results,

but it ends up being almost the same if we pick

the minimum value of the domain X because basically,

this is saying the same as X equals d and this is

saying X is greater than d which is the same thing,

X is not equal to d if it's the minimum value.

So, programmed search is one of the great advantages

of Constraint Programming solvers because the user

can specify a search strategy that

allows them to add knowledge of where the solutions were right

and this right search strategy can make an exponential difference.

And one thing we also have to be aware of is that

not all the variables in our model have to be labeled.

So, if we label enough of the variables,

so that the rest are fixed by the constraints,

then we've solved our problem.

So, MiniZinc allows the modeller to suggest a CP search to the solver,

and notice that these annotations that we're

using for this can always be ignored by the solver.

For example, if the solver is a MIP solver,

it does not support program search,

so it's just going to ignore these annotations.

So, these annotations are written on the solver item,

we'll see examples later on,

and the basic ones are an integer search,

so here's the variables,

this is how we're going to pick the variable to branch on,

and which value we're going to branch on or which way we're going to split,

and the complete is a fourth argument left over

from an original way that these were specified which will always be complete,

so, you can ignore it for the most part.

So, we can do the same thing for a boolean search.

So this is an array of boolean variables,

or float search, this is an array of float variables.

And notice that if you don't put all the variables in there,

the solver will use its default search on that.

And if you didn't put any annotation,

then the solver will always uses its default search.

So, default search will be used for any variables

which are not fixed by a search annotation.

So, we've got labeling search.

So typically, we want to break this up into this variable choice,

and the kinds of things we can do are input order which

just says this is an array of integer variables.

We're just going to fix them in order,

that's what we did in the examples that we showed before.

Or we can do first fail,

which is choosing the variable which has

the smallest possible domain at the current moment.

We can do smallest, which is choose the variable which has the minimum of its domain,

or largest, which is choose the variable which has the largest maximum of its domain.

So there's various different ways we could pick which variables to split on.

And then the splitting is possible,

so we can select indomain_min,

just says we fix it to its least possible value.

Indomain_max says fix it to its greatest possible value.

We can do indomain_medium to fix

a medium value or indomain_random to pick a random value.

And you'll be surprised in how effective random value selections can be.

So then, we can run our model from

the command line by basically saying minizinc with a minus s,

that's for statistics for our herbs program,

and we can change our search that's happening inside

the model by basically adding this int_search annotation on the solve item,

so you see, here's the solve,

here's this annotation item,

and here's the annotation, and then satisfy,

because we're only looking for any solution.

And so, we have this varchoice and valchoice,

and so we might pick our varchoice out of input_order, first_fail, smallest,

or largest as other ones as well,

and the valchoice would be indomain_min, indomain_max,

indomain_medium, or indomain_random, also other ones are possible as well.

So, you should experiment with herbs.mzn to find out

what's the most robust search strategy as

the rows and columns of the herb drawer increase.

And you can draw the search trees yourself,

or in fact, you can use gist and Gecode,

which comes with a IDE package,

to look at the search trees that are generated by Gecode,

and explore what's going on.

So, you can also find all solutions with the minus

all solution flag from the command line or using the configuration tab in the IDE.

And you should notice if you do that and you try

different valchoices for finding solutions for

this small example with the three rows and two columns,

you should notice something that basically, it doesn't matter what happens.

You're going to get the same number of solutions.

So, notice that we can actually construct and use annotation parameters,

so I can declare an annotation parameter.

So, var_select and annotation parameter search,

and those are now parameters which I can give a value to.

So for example, I could set var_select as first_fail,

and then I can build search as this annotation,

this int_search annotation using var_select to be the variable selector.

And here, I'm fixing the random value choice,

and then I can just annotate this with search which,

of course, basically does the substitution,

so search becomes this annotation,

and these var_selects replace by first_fail.

So, annotation parameters are also useful

if you want to control different search strategies from outside,

we can set those annotations on the command line.

So for our large example with 10 rows and 10 columns,

if we run the MiniZinc with this search strategy,

we pop out with a solution like this.

So, there are much more to learn about search.

So, program search is a very important part of CP,

and we'll look at some of these features later on in the course.

So, sequential composition where I'm going to

make decisions over one set of variables and then when I finish that,

look at another set of variables.

More dynamic variable selection strategies like dom_w_degree, impact, or activity.

Restarts, where we actually stop the search and go back and start from the start again.

And other ways, to explore the search tree like

limited discrepancy search or breadth first.

And there's even more complicated search notions like search combinators,

which allow us to join together search strategies

to build bigger and more complicated searches.

So in summary, Constraint Programming solvers alternate

between this guessing a value or restriction for a variable,

so this is the splitting or the fixing of a value to a variable,

and then propagating the result of that guess

and basically, we've seen the algorithm which

is the core of any Constraint Programming solver now.

So, we can control this guessing,

the search, so we can program that search.

So in MiniZinc, this is done via search annotations

and the usual search control is we pick

which variable to explore and how to restrict that variable,

so how to split or search on the values of that variable.

Explore our Catalog

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

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

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play