Guan Ping arrived back with a news that Yu Bei is currently in Guan Chiao's care. After becoming aware of this, Guan Yu decided to run away from Cao Cao to find his brother. But he had to pass through a number of cities on the way. Some of these cities are guarded by troops that Guan Yu had to fight against in order to pass through. Some cities had larger groups of troops than others. Guan Yu had to come up with an escape plan, and in order to conserve energy he decided that after he had passed through two consecutive cities with troops, he would choose the next city without troops in order to take a rest. Guan Yu also needed to minimize the number of troops he would encounter when passing through these guarded cities so as to increase his chance to escape. To figure out the best escape plan, Guan Yu pulled out a tablet. >> So Guan Ping has returned to his father, Guan Yu, with news that Yu Bei is in the camp of Yun Chao. And so, Guan Yu has decided to escape. Now his escape is going to be much more difficult than his son's because he's too well known. He's going to have to fight his way out. So here's a map of the routes that he can go from where he is now in Cao Cao's camp to where Lui Bei is. And at each of these nodes,some of them have guards, which are shown in red. And the number of guards that are there. And some of them have no guards, which are shown in green. So he needs to plan a route to get from where he is to where Lui Bei is. Now, he's going to have to fight the guards at each of the red nodes and he's going to need a rest. After he has two fights at two different places, then he is going to need a rest. So he can't have a path which visits three red nodes in a row. He has to have a rest every three steps. And the objective is to minimise a number of guards he meets on his way to Liu Bei. And so obviously the more guards he meets, the more chance that he gets killed in the combat. So that's a safety result. So we're going to represent this data using a graph like this. And we're going to add an extra edge here from the destination back to itself. And we'll see why we do that later on. It's going to allow us to make a much more simple model and a much more efficient model to solve. So, we should actually check there's some assumptions about this status. So we should actually have assertions to check that they happen. So basically we're going to assume that there is no guards that's in the starting position and no guards in the ending position which is fairly safe assumption for this example problem. And here is our edge map where we've assumed that we have this edge from the destination back to itself.. All right, and the rest of the data is just where he starts, where he ends, and how many nodes he can go before he needs a rest. Basically he needs a rest every three nodes. And we're going to also anticipate the maximum number of steps that he can take as ten. So let's look at the data. So we have this set of nodes and for every node, we have the number of guards at that node, which might be zero. And then the edges are basically this two-dimensional array, just pairs of nodes. Right, so it's a list of pairs of nodes, and we saw that 2-dimensional array on the previous slide. We have a start and end destination. And this resting amount. How it's gotta rest every rest number of junctions. And then the decision. So there's a maximum number of steps in this path that it can take. We are going to be interested in the actual number of steps he takes because the shorter the trip the better obviously. And then we basically deciding at each step which node is he at. So that's going to generate the path. He goes from this node, then the next node, then this node next, then this node next, eventually getting to the destination. Now we're going to make use of, to represent or this path constraint, we're going to make use of the table global constraint. Now this is a very important global constraint because it's very very flexible basically allows us to write down arbitrary relations amongst variables. So it takes 2 arguments, an array of n variables which are the ones we're constraining and then a 2 dimensional table Giving us the tuples of values that they can take. So there's n values in every row of the table and there's T rows. And basically, this constraint enforces that the x's all take a value from one row of the table in T. So if we look at this example here, x, y, z is our array of variables. And then we have this two-dimensional array with Three rows in it and three possible values. So this constraint forces that either x is 0 and y is 0 and zed is 0 so they all take values from the first row. Or x is 1 and y is 2 and zed is 3, Or x = 4, y = 2, and z = 0. And I said this is very important global constraint because it's totally flexible. Basically, we can write down an arbitrary constraint by just listing every possible solution to that constraint. And then enforcing that opponent variables. So we're going to use that to represent the path in the graph. So the first thing of course is we're going to start at the start node. But here is the use of the table global. We're going to say if we're at position path of i, at step i, and we're at position path of i+1, at step i+1, then there has to be an edge between those two. So basically this is going to force us to follow a path in the graph. So that's very, very important. But now let's see why we added our self edge at the destination. So if we think about it, we don't know how many steps Guan Yu is going to take to reach Lui Bei. And so what we're going to do is we give this maxstep, which is a educated guess on the maximal possible length of the path. The smaller the better because the smaller is the less decisions we're going to make, right. We're going to have to make a decision of where we are at each of these steps regardless of how many we really use. So, that's good. But if we make it too small, of course, we might remove the best solution, or remove all solutions. But, we have to do something with the extra steps. And what we're doing is going to make use of that self edge. So, basically, when the path goes like this: 1, 2, 3, 11, 14, 15, 9, once we've reached 9, which is our destination, we're just going to keep staying at 9. And so by doing that width we're going to use this constraint from the previous slide. Then, if we're in position 9 at, say, step 7, and position 9 at step 8, we need an edge which is from 9 to 9 to make sure that this is allowed. So that's why that extra self edge is there. To allow us to do extra steps and still use the same table constraint, to just keep us there. We're going to add some extra information to force us to stay at the destination. Once we do and this is basically once we go over the actual number of steps, then we force that the path of i is equal to the destination. So basically here it took us let's say 1, 2, 3, 4, 5, 6, 7 steps to get to our destination. So the steps is 7 and then our destination is 9. And forever were onwards still have to be 9. So you have to stay at the destination from that point. So as you can see how our self edge is helping us, we can just use the single constraint here, this table constraint. It's not going to exclude the possibility of staying where we are once we reach the destination. So we're to use another global constraint in our model. This is the sliding sum model. So, this takes four arguments, the first is a lower bound. The second is the upper bound. The third is the amount, the size of the sequence, sub-sequence we're going to look at. And then this is the array of values that we're going to constrain. So basically it says, for every sub-sequence of this array of length s sequence, that the sum of that sequence, that sub-sequence of S E Q values is between low and up, inclusive. So if we look at our example here, we're saying the sum of every four numbers in this array x has to be between 4 and 8. So if we check here, on this array, the first four add up to 7, next four add up to 6, next four add up to 5, next four add up to 7. So all of those constraints. They're all between four and eight. If we look at the second example of x here, it's not a solution, why. The first four add up to 7. The second four add up to 7. The third four add up to 4, but the last four add up to 3, so they don't make the lower bound. So how are we going to use that to encode or use that in our model? We are going to use that to encode this resting constraints, because we know that in every three steps, we has to make a position whether there's no guards. And so that's sliding sum says, so for every three steps, that's what rest is, we have to make between 1. And rest positions where the guards on that position is equal to 0 right. So we're counting how many nodes we met where the guards of the position are 0. Of course, if we, we're lucky we can reach all having no guards, and that's perfect. But we have to have at least 1 where there's no guards. And finally, our objective was to sum up the number of guards that we met on the path. And he where I using this assumption that the destination is no guard because we keep adding up the number of guards at the destination. For all those extra steps at the end. So we run the model and we get unsatisfiable. So this is really not good. This is very depressing when we run a model and just gives no solutions. Cause we think there must be a solution. So what is happening? What can we do? So this is one of the worst things you can do with a model. And even worse is when you run the model and it just sits there for a long time and never gives back an answer. So the first thing we should do for optimization problems is run with all solutions printed. Okay, so typically if you run an optimization problem without asking for all solutions then it will just run until it proves optimality. And proving optimality might be very very hard. Now if you're using the IDE this will be always a default behavior. If you have an optimization problem it will always run with all solutions printed so you'll see any simple solution, before we reach the optimum, will still be printed out. But if there's still no solutions found, as in our example here. So we were running with all solutions printed. It didn't find any solution for Guan Yu. Then we have to do something more. So, more general techniques to doing this. We can add a solution, a solution we expect to see to our problem and see where that breaks and we can relax constraints. We're going to make the problem easy until we find the solution. Maybe that will give us a hint about what's going on. So, when we add a solution what we want to do is construct a small instance of the problem that we're trying to solve. And something that should be a solution, something that will be expect to be a solution. It doesn't have to be a good solution, if we're doing optimization. It can just be any solution. If we add it to our model and re-run we might, with luck, get a message saying something like modeling inconsistency detected. And if we're lucky a line number that tells us where that problem was. So basically it will tell us which constraint is causing this solution not to be a solution and we go directly there. Otherwise we might get warning model like this, model inconsistency detected before search, which just means somewhere, the model doesn't have a solution, but we don't know why. Worst still, it might still run and still give us no solution. That'll not help us at all. So more generally, we can look at relaxing constraints. Right? We're going to try removing constraints one by one until a solution is found and this is going to help us narrow down the set of constraints which were responsible of the problem and once we know which constraints are causing the problem then we're going to be able to fix the problem. So let's look at doing that two our example problem. So we add an expected solution here to the model. So we expect if we took step 7 This would be actually a solution to our model. And if we run this, we just got unsatisfiable with no extra error message, so it didn't help us at all, unfortunately. So let's start removing constraints. If we remove the sliding sum constraint, we still get unsatisfiable. So that wasn't really part of the problem. If we remove the table constraint then we get a solution, basically here, since there's no variables, we just print out that there is a solution and in fact is optimal because once we've added this constraint there's no other possibility of a solution. So obviously something's going wrong with table. So what is it. So let's add a trace to see what we're actually asking this table constraint to do, all right. So we then add a trace here printing out the tuples that occur in this path, every time we write down a table constraint and now this will make sense, because these path variables of course are fixed, because we fixed them in our example solution that we've added to our model. So if we do that, we're going to print out something like this. And now something should pop out at you. If you think back of the edge array, all the entries, the pairs in the edge array were written with a lower number to a higher number so all the edges were written from a lower number to a higher number. So there was no entries. Of the form 10, 6 or 15, 9. The only one which went to an equal number was 9, 9. So, is it clear what's going on now? This constraint fails because these table constrains don't succeed. There is no edge 10, 6 in the edge array, okay? The problem is we have got edge data which is, unidirectional edges but we want so, we're using it in a way which is directed, right. We only have one direction of the edges in the edge array and what we're expecting was to have both directions. So we need to create an undirected form of the edges and the easiest way to do this is just add the reverse of each edge. So let's build a new table, so this twice as big as the original table, with his undirected edges. And basically, here's all the original edges, all right, that we're creating. We have to flatten them all out into a one-dimensional array, and then we're going to use array2d to reconstruct the two-dimensional array. And here's all the edges in the reverse order. Right, where I have basically put the second element of the age and then first element by putting 3 minus j where j is 1 to 2. So that is ordered the mean edge i2, i1. So we reversed the order the edges. Now, all we have to do to our model is replace the use of edge with this undirected edge. So now, we found our error, we've replaced that by this undirected edge here. We're going to get the correct behavior. Okay, no solutions is the worst possible thing that can happen all right. It might be that the model is too slow to solve. Or the solver just goes into a huge search and never returns. But this is the worst thing where it basically never returns. What can we do? Well, we should try to simplify the model first. Okay, take into account, less to the problem and see if you can get some answers to that. Look at the solutions to the simplified problem. Maybe you can use them to understand what's going on and then prove your model that way. Another way is just to decompose the problem. If we break the problem into two parts, we won't get as good an answer, but we can maybe solve the first part of the problem, fix that solution and then use it for the second part of the problem. And that will make our problem much easier to solve, and hopefully, that allows us to actually get some solutions, even if there's no error in our model. But we have to be aware that in discrete optimization problems, some of these problems are just going to be too slow to solve. Hopefully, we expect to get at least some solutions quickly, but not always. So debugging models is very hard and basically it's a key skill that you need to develop to become an effective user of a discrete optimization technology. But our key methods are things like this. Find a small example which shows the problem. Make sure the constrains generated by your model are the constraints that you think they are. And you can use things like trace and assert to make sure that that's happening. Generate a solution that you expect to find and switch on and off constraints in the model to see when, what is causing that solution not to be actually exist. In other words, solve a simple version of the problem by basically ignoring parts of the problem. And that'll allow you to get past this problem of missing solutions, which is very hard to deal with.