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.