3.2.3 Inside Alldifferent

Loading...

From the course by The University of Melbourne

Solving Algorithms for Discrete Optimization

2 ratings

The University of Melbourne

Solving Algorithms for Discrete Optimization

2 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

Advanced Constraint Programming

In this module, you will see how Branch and Bound search can solve optimization problems and how search strategies become even more important in such situations. You will be exposed to advanced search strategies, including restart search and impact-based search. The module also uncovers the inner workings of such global constraints as alldifferent and cumulative.

3.2.1 Optimization in CP17:36

3.2.2 Restart and Advanced Search20:11

3.2.3 Inside Alldifferent14:03

3.2.4 Inside Cumulative14:30

3.2.5 Flattening39:53

3.2.6 Module 2 Summary6:30

Meet the Instructors

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

With his improved skill, Hou Yi shot down nine of the ten Suns and

the drought problem was solved.

[MUSIC]

But at the same time, there were monsters now unexpectedly attacking the villagers.

Hou Yi decided to build several guarding spots with armies near the villages in

order to protect them.

[MUSIC]

Every guarding spot was adjacent to one or more villages.

When a village was under attack,

an adjacent guarding spot would deploy an army to fight against the monsters.

Normally, any one adjacent guarding spot could send out an army to help

a village under attack.

This situation could be more challenging, however,

when multiple villages were under attack at the same time.

An unsophisticated defense arrangement might result in no existence for

some of the villages.

Hou Yi want to establish in arrangement to ensure all villages can be protected,

even when attacked simultaneously.

[MUSIC]

Zhuge Liang summoned the dragon of dimensions to help determine this

arrangement.

[MUSIC]

>> So with the heavens in disarray, there are monsters running wild everywhere and

Hou Yi is responsible for protecting the towns.

And he has military units stationed near the towns and

they can protect all the towns that they're adjacent to.

So if a monster attacks the town,

then we can take any of the military units which are adjacent to that town.

And they could be sent to protect it, so any of those five military units.

But imagine if we took this military unit to protect the town,

then that's all very well.

But what happens if monsters attack the other towns?

Then we need to be able to defend those other towns, as well.

So for example, we could try this way where this unit protects this town and

this unit protects this town.

But then we have no way of protecting these two towns.

So that's not acceptable.

We could try a different arrangement where this unit protects this town,

this unit protects this town and this unit protects this town.

But still, there's no way we can protect this last town.

So in some sense, we should never use unit two to protect town T.

So this responsibility should be removed.

And if that's the case, because we know if we do that,

we might get to a situation where we can't protect all the rest of the towns.

And so that should be removed from the responsibilities of this unit,

because we know it could cause problems later on.

So Hou Yi has this problem of trying to work out how to adjust

the responsibilities of the different military units in order to make

sure the towns can be protected.

And for this, he goes and asks help from Zhuge Liang.

But here's our problem.

We've got N villages and K armies.

Of course, we have to have at least as many armies as villages.

Otherwise, there's no way we can have one army protect each of the villages.

And each army is connected to and can protect specific villages of its and

an army can only protect one village at a time.

So here's our scenario.

A random village is being attacked and a random connected army is chosen to protect

the village, and we want to adjust the responsibilities to ensure that all

the other villages can be protected if they're attacked at the same time.

So now, let's draw the parallel to what we're really doing here.

We can think of these villages as variables and we can think of the armies

as domain values, and what we're trying to do is assign to each village a army unit.

So for each variable, we're assigning a domain value.

And you should see that that is of course the alldifferent constraint,

because each village, each variable will be assigned a different value.

So that's exactly an alldifferent constraint.

And so here's a solution of the alldifferent constraint where every

village is protected by a different army.

And when we looked and we saw that this was not a good way of protecting town T,

what we're doing is removing edges which are not domain consistent for

the old difference.

So this possibility of sending T to 2,

if you want is not domain consistent and it should be removed.

So we've seen throughout this course that global constraints are very,

very important.

They capture this combinatorial structure.

And ideally inside our solver, we can use efficient algorithms to do inference for

them and there are a number of different efficient ways of doing it.

We can just use the decomposition.

Because of course,

alldifferent is just a whole lot of not equals constraints put together.

We can do a bounds propagator which only reasons about the bounds of the variables

or we can do the domain propagator and

that's what we're going to talk about in this lecture.

In the next lecture, we'll look at cumulative and

the timetable propagator for it.

So global constraints are one of the principal advantages of these propagation

base of view of solving.

constraint program reviewer solving.

So every global constraint, we know captures an important and

common same problem.

alldifferent captures this assignment problem and cumulative captures resource allocation problem.

And so it's important to understand how these things work.

So they are implemented by one of possibly several propagators and indeed in a system

you might have more than one propagator for the same global constraint.

Because in different circumstances, you want to use different propagators.

But a good implementation of a global constraint has strong propagation.

So ideally, we get domain propagation which remember is the strongest

propagation we can do.

That infers the most possible information from the constraint and fast propagation.

Usually global constraints aren't idempotent,

because that ends up being too complicated to implement.

But not often can we have this combination of both strong propagation and

fast propagation, but alldifferent is a case where we can.

So our alldifferent constraint, we should be well aware of by now.

Each of the variables has to take a different value and

we know that alldifferent X, Y, Z is just equivalent to these three inequalities.

All of them have to take a different value, but

this decomposition into not equals is not very strong.

So if we look at these constraints here, this constraint here.

And we look at the domains where X, Y and Z are all 1 to 2,

then no propagation will happen for any of these inequalities.

But of course, there is no way of giving these X, Y and Z values all different values.

This is infact,

what's called a pigeonhole problem where we have three variables, X, Y, and Z.

If we want three pigeons to put in two holes, 1 and 2,

it's going to make sure that there will be at least two pigeons in one hole.

So whereas this alldifferent constraint does not hold,

if we just use the inequality version, the solver won't be able to recognise this and

it'll keep going.

Eventually, it'll do search and find that it doesn't hold.

We can be much better off if we have a specialised propagator for alldifferent,

which can notice this right away.

So what we're going to build is domain propagator for alldifferent and

this is one of the very first important global propagators, it

has this complexity of n to the 2.5, and it's based on maximal matching, and

it wakes on domain change events.

Obviously, when we're doing alldifferent, every individual value matters.

And so we're going to wake basically when any of the variables changes this time.

So we're going to match these towns with the armies.

Matching the variables with the values.

So how is this work?

So in our scenario, we can think of it as these five variables and

these initial domains given here.

This gives us this matching graph which says, and so

we have a line from X to one, because one is in the domain of X.

We have also a line from X to two and three, and

what we're going to do is find a maximal matching of this graph.

This bipartite graph.

So here, you can see an example of a maximal matching.

The heavy arcs are in the matching and the dashed arcs are not in the matching.

And in fact, it turns out these dotted arcs can't be in any maximal matching.

Whereas this arc here could be in a maximal matching and

it isn't in the one that we choose, these non-dotted arcs.

And so the alldifferent will actually get rid of all of these arcs here,

which can't be in a maximal matching.

Because if they can't be in a maximal matching,

then they can't be in a solution of the alldifferent constraint.

And so we're actually going to domain propagation and

move from these in digital domains to these much smaller domains down below.

So let's go through how we're going to do that.

So the first thing we have to do is construct a greedy matching,

a partial matching as much matching as possible.

So we can do that just greedily.

We can just say, lets set X to 1, Z to 3.

T to 2 and U to 4.

Now we can see now, there's no place I can match Y.

Because all of it's possible partners are matched.

So we stop.

Now we have to build a maximal matching and this is a well-understood graph theory

problem, and the way we do this is we're going to search for

what's called an alternating path.

So we're going to start from unmatched variable Y and

we're going to search for an alternating path using unmatched edges,

and matched edges until we reach an unmatched value, and

that's going to give us a way of extending our matching by one more unit.

So we're going to start from Y.

You're going to take this edge to three here.

Now there's only one way we can go with a matched edge here, which is back to Z.

Now, we'll take another edge here to two.

There's only one way you can go back to T and

then we'll take this edge here to five, and we found an unmatched value.

So overall,

we've built an alternating path from an unmatched variable to an unmatched value.

And now, what we need to do is flip all of the ages in that path and

we'll have a new matching which has one more unmatched variable.

So it may not be the case that's possible.

It's not always the case that the matching could be made.

In which case, the alldifferent constraint has no solution.

So if we look at this example about alldifferent constraint with slightly

different domains, here's our matching graph with our current matching and

we start from Y.

If we try any alternating path we go down here, we go up to Z.

We go back down to here up to X and then we go back down here.

We can't find an unmatched value.

Any path that starts from Y can't end up finding one of these unmatched values

3 and 6.

And so this is no solution, which is not surprising.

If we look at X, Y and Z, they take values 1 and 2.

There's three variables needing to take two values and be alldifferent.

So now, we've got a check to see whether the alldifferent constraint has a solution.

So if we have a maximal matching which matches all of the edge,

it clearly has a solution.

Because that is a solution.

If it doesn't have a maximal matching which matches all variables in this,

definitely no solution.

But we already domain consistency,

we want to remove basically the edges here which don't correspond to any solution.

So how are we going to do that?

The first step we're going to do is orient the edges.

So we're basically going to orient the edges in one direction.

The matched edges go down.

The unmatched edges go up.

Now, we can do some pruning once we've done that.

We look at the unmatched values and we look at all the nodes that they can reach.

So if you start from 6, you can reach all of these nodes follow the arrows.

So all of these edges can be kept.

Because basically, we can build a different augmenting path which used 6 and

didn't use 4 and 5 to give values to these variables T and U.

So all of those edges can be kept.

We can also keep all the edges within a strongly connected component.

If we see here, Y and Z and 2 and 3 can all reach other.

Basically, this big cycle around here.

And we can basically, this is also or this is not a strongly connected component.

This is a single connected component.

We were all going to keep always all about matching edges and

then we delete all the rest of the edges.

So basically, none of the rest of the edges can ever be involved in a solution

to the alldifferent constraint.

You can see why.

Because if T or U took the value 3, for example, there wouldn't be enough values

left for Y and Z and X which need to only take values one two and three.

So basically, this is exactly doing this thing of removing any edge which would

lead us to a possibility of not having a solution to our alldifferent constraint.

So once we've done our pruning, that's how we get our new domains.

If we look after we have done that pruning, X becomes fixed to 1, Y

and Z can only take the values 2 or 3, and T and U can take the values 4 and 5.

Well, T couldn't take the value 6

U can still take the value 6, as well.

So if we go back to our original graph, this is what our new responsibilities for

our armies and our villages is.

And now we are sure that whatever happens if these monsters attack,

we'll be able to split our armies around

the villages in order to protect each one of the villages.

So we've looked at a domain consistent propagator for alldifferent.

There are bounds consistent propagator for alldifferent, which is faster.

And it's also based on maximal matching, but it only wakes on the lower and

upper bound events.

And it's actually faster, see n log n much faster than n to the 2.5 and

often sufficient for most applications.

So indeed, typically, we're going to use the bounds propagator for

alldifferent for most applications.

But some applications such as permutation problems really

do require domain propagation.

So domain propagation is a critical part of many CP solutions to problems,

which have an assignment subproblem component.

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