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.
