Although Guan Yu was of great assistance to Cao Cao, he was kept under house arrest and unable to receive any news about his brother, Liu Bei. He therefore planned to send his son, Guan Ping, to secretly collect information. There were ten exits for Guan Ping to escape the city and collect information. It took different amounts of time to walk along the paths leading to these exits. Four of these exits were guarded by soldiers, and it therefore took even more time to use these exits and avoid the soldiers. The time needed to escape was the sum of the walking time and the time for evading the soldiers if needed. On rainy days, there was no impact on the walking time and time for evading the soldiers, because the dark sky obscured their view [MUSIC] On sunny days, however, the walking time halved, while the time for evasion doubled because of the clear view of the soldiers. [MUSIC] It was impossible to escape on stormy days, as the heavy rain resulted in muddy roads. With all this in mind, Guan Yu wanted to work out in what weather condition it was best for Guan Ping to exit and which path he should use to leave the city in the quickest way possible. Again, Guan Yu, turned to the magical device, but a solution was not provided, and thus, Guan Yu called for help. [NOISE] >> So, Guan Yu is stuck in the camp of Cao Cao and wondering what's going on outside. So he decides to send his son, Guan Ping, to find out more information. So, there are ten possible escape routes from the camp. And each of them takes a different time to go along that route, so to route 9, it takes 12 hours. But there's also guard posts on some of the routes and it's going to take a number of hours to evade those guards. So, if we look at the total time it takes to escape on this path, then if it's rainy, basically the times on each of the edges were given in hours. It takes 12 hours on route 9 and it's going to take 8 hours to avoid the guards on route 2. If it's sunny, what happens is that he can make twice as fast of time on the escape route. So, it halves the time required to go along the route, but it takes much more effort to avoid the guards. Because now, they can see much further. So, it doubles the amount of time to avoid the guards. And if it is stormy then basically it becomes impossible, the road becomes impassable, and Guan Ping can't escape at all. So, what we're trying to do is optimize Guan Ping's escape time, because that's going to give him the best chance of getting out without being detected. So, let's have a look at that model. So we have a set of paths from 1 to 10 and a set of guard posts on 1 to 4. And basically, for each path, we have a time it requires to go along that path. And then for each guard post, we have the time it takes to avoid those guards. And then we have possibilities of the weather. So, we can wait til the weather is the kind that we want. Or we gotta chose, we could go in storm or rain or sun, and we're encoding those using 0 to encode storm, 1 for rain, and 2 for sun. And so, the other decision that Guan Ping has to make is which path to take. And now we've gotta work out how much time does it take to do that? And so, here is our calculation of the time. So it's going to take the time required for that path, divided by the weather. So, if it's sunny, it's going to be divided by 2. If it's rainy, it's going to be divided by 1, so it's going to give you the original value. And if it's stormy, it's divided by 0, and we'll talk about that on the next slide. Plus, if we take the guard time, the time to avoid the guards on that path and we multiply it times the weather. So if it's sunny, that doubles the amount of time to avoid the guards. And we're trying to minimize this time. And there's our data that we've seen on the previous slides. But what about this division by 0 that can clearly happen there? If the weather is 0, we're going to evaluate this expression, time of path divided by 0. So what should happen when weather is 0? Now the way to think about this is that what we're building here is constraints. And division is really a different way of writing down multiplications. So, when we write down an expression like x equals y div z, it's really the same as saying this, that y is x times z, plus some remainder. And that remainder, of course, has to be less than z. And what should happen then? Well, if we set z to 0, so if we just set the divisor to 0 here, then there's no possible way for this remainder. So, this remainder's gotta be between 0 and less than the value of x, there is no possible way, because z is 0. That means this whole constraint would fail. And this is telling us what should happen with this whole constraint. If we reset z to 0, there is no value of x, which is going to make b equal to y div 0. And so, the whole constraint should fail. So, our model is correct when weather is 0, that constraint working at that time will just fail. And Guan Ping can't sneak out. So, that's going to make sure that if we try to set weather to 0, it won't be part of any solution. So, if we run our model, we'll get this answer. The weather equals 1, and the path is 3. And if we look that up, we'll see that it takes 6 time units, I think it's 2 for the path, and 4 for the guards. Is that all we expected though? There is a path, a path we call 7, which in sunny weather, looks to be shorter. Now, what we've got to do is look at this expression here and understand what's going on here. So, if I said path is 7 and look up this guard array, well this guard array only goes from 1 to 4. So, there's no possible value for guard of 7. So what happens is guard of 7 is undefined. It just has no meaning, just like division by 0, it returns undefined. And that is going to make the whole constraint false. So, the way we've written the model, because we got this expression guard of path in our expression for evaluating t, there's no way that path can take a value outside of post. Because if it does, what we try to do is look up, we'll get a value undefined, and then the whole expression will be undefined, which will make the entire constraint false. So, as we've written our model now, we can only look at paths one to four, because of this expression, which is going to force if it's going to succeed that path is between 1 to 4. So, what we're talking about here is the use of partial functions. So, our model is make use of partial functions, division and array access. And these are commonly the most common partial functions you'll see in a model, particularly array access. And we've got to ask this question when we're using these, how should our model act when we do division by 0? Or we do array access out of bounds? And the relational semantics, and that's what I was trying to explain by saying this x equals y div z, is equivalent to running some multiplication constraint. Is that these statements, they just have no solution. So, because we're really talking about relations, eventually, there's just no solution to the relation, which means it makes them false. So, how can we fix our problem? We want to get rid of this out of array axis, we want to get rid of this partial function behavior. So, let's take our expression for t and replace our guard of path times weather by building up this extra cost. So, this is the extra cost for guards if they're there, unless adds some constraints to define what happens. So, if the path is in post, then the extra cost is we lookup the guard on that path, right? And if it is not the case the path is in post, then the extra cost is no guards is 0. So, we are basically adding this definition to make sure that we get the right value. Now, what happens? So, we still have the possibility of putting a path 7 here, right? There's nothing stopping path equals 7 being put there, so what happens? Then this whole constraint becomes false, because there is no path of 7. So, this constraint is false, but also this constraint is false. So path in post is going to be false, since post is only 1 to 4. And so, the whole implication is true. So, this allows us to now set path equal 7 without causing failure for the entire model. And this will mean that we'll get the right kind of behavior. Another way we could do this is using if, then, else. So, we can just write an if, then, else expression for the way we calculated extra here, which would also be more efficient. So, if the path is in post, we get guarded path, otherwise we get 0. And then we're going to multiply that times the weather amount. All right, so now when we run our corrected model, we get that if the weather is sunny, we can take path 7, and that will only require time 4. And now, our model correctly uses the relational semantics because when we try to do something, which is an unbounded array axis, we've sort guarded it. We've guarded it by this expression here, or this implication here, which means that that it won't cause the whole model to fail. So, the relational semantics is how MiniZinc handles partial functions. And the way you can think about this is if you get an undefined result, that's when you do a division by 0, or an out of bounds array lookup, then that floats up the expression that are seen until it finds a Boolean context, something which has to be true or false, and it makes that whole thing false. And so, that's how undefined behaves. So this is a relational view point, because if we've converted these things, this division to multiplication, it's just another relation. We get the same behavior. Now, we have to be careful because it makes some obvious transformations of the model invalid. So, if I write not x div y equals 1, it's not the same as x div y not equal to 1, if y can take the value 0. So, if y can't take the value of 0, these are exactly the same statement. But if it can take the value 0, we can see that this expression here, right? 0 div 0 equals 1, this will be false, and then the not will make it true. Whereas over here, we'll go 0 div 0 not equal to 1. And the first born expression that we'll find is this one, so it will make the whole thing false. Right, so you can see how that undefined value floats up until it finds a Boolean expression, the first one, that it's inside its context and it makes it false. Ideally, we want to write models where undefined can't occur. But that's sometimes not possible and in our example before, we added a guard. There was still an undefined that could happen, which became false. But it would happen in a controlled way that would make our model correct. So, in summary, the relational semantics is very important to understand how models act when you're dealing with a possibility of getting undefined results. But most models will have no partial functions. Normally, you should make sure that whenever you're building a model which can access an array, that all the possible ways that that expression, that accesses the array, fit within the index set of that array. So you always get the right result. We don't use division that much in models. But also, every time we do a division, make sure that y is not equal to 0. So, once we do that, we're going to avoid partial function applications and our model will be easier to understand. But we have to be aware that if we are going outside these rules, then the relational semantics is the way to understand what's going to happen to our model.