Zhuge Liang had fixed all of the troubles that he caused by breaking the tablet. However, the celestial old man told Zhuge Liang that his mission was not yet complete since his actions caused changes in history. Zhuge Liang was encouraged to travel to different times to rectify these changes. Zhuge Liang arrived at the dynasty Shang. He joined the war between the Immortals where he needed to help Tai Shang Lao Jun and Ne Zha defeat the Grandmaster of Heaven. During the fight, the Grandmaster of Heaven called upon his team of Taoist priests to establish a gridlock,10,000 Immortals formation for defense. Moreover, he summoned several magical swords used to create Qi shields. The overlap between these shields provided strong protection for the Grandmaster. Tai Shang Lao Jun pointed out, that attacking the weakest taoist priest within the shields was sufficient enough to destroy the whole formation. Ne Zha asked Zhuge Liang to help find the weakest Taoist priest. Zhuge Liang summoned the dragon of dimensions for assistance from the professors. With a disruption in the heavens, it's come to the point that Ne Zha has to battle the Grandmaster of Heaven. Now, he set up this 10,000 Immortals formation of priests all sitting on this one meter by one meter grid. And to improve his defenses, he is also set up this Qi Shields. So he set up Qi Shields on all of the three different cardinal planes and some extra Qi Shields, three different Qi Shields like this all to protect his little area. And in this intersection space, which is within all of the Qi Shields then he is very, very strongly protected and then he has his 10,000 Immortals formation of the priests also protecting him. Now, Tai Shang Lao Jun has decoded the definition of the Qi Shields and, in fact, the Qi Shields are defined by these six different constraints, so basically three different planes and these the planes that are orthogonal with the axes. And he knows that, in fact, the weakest member of these 10,000 Immortals will be found at a position given by this expression. So the weakest member will have the largest value of that expression. And so he knows that there will be a priest at a Vertex and that is the weakest priest. And if Ne Zha were to attack that priest at that position, then he would be able to break down the whole formation all the Qi Shields will be broken and he can then get through to the Grandmaster of Heaven. So let's look at the Qi Shield problem. So we are given these six Qi Shield planes in 3D space. And we've got an objective because the priests under the protection of the six shields have a strength and we want to find the weakest point. And so we can think of this as this MiniZinc model. So we have our three complex Qi Shields and then the three planes just X, Y, and Z that are positive and we want to maximise this objective here which is basically the higher that is the weaker the priest at that position is. And what we've got here is an example of a linear program. So a linear program, in general, has N variables and M constraints. We are going to maximise a linear term. So this sum of coefficients times the variables, that we are talking about, subject to these M constraints which are also linear constraints. So we can write it out using this A of IJ is the coefficient for XI in the Jth constraint, and all of these XI variables have to be non-negative. So we've got linear objectives, linear real constraints, and non-negative real decisions in our linear programs. And so in order to solve this linear program, we are basically going to look at these linear inequalities which are hyperplanes in the n dimensional space. N is the number of variables. So now example, there are three variables so we are talking about planes in three dimensional space. And so here is the first plane, here is the second plane, and here is the third plane, and then we put them all together and we get these intersections so around here is the actual space of solutions of this problem. And so we can work out where all those planes intersect on all these intersection points and then we can just get to a bounded, in this case, polytope, which defines all the possible solutions to those constraints. And here, if we expand it out, we can see where all of the intersection points are those constraints are and, interestingly, you can see there are only five faces to this polytope even though we had six constraints and that's because one of the constraints was actually redundant it actually didn't improve the Qi Shield at all. And the most important thing about solving this linear program is we know because it's a linear objective that the optimal solution must be on one vertex of the polytope. So one of these vertexes must be the solution that we are looking for. So it could be that one or that one or indeed the other vertexes. So how are we going to find this vertex? So we are going to do it this way. We are going to jump onto a vertex at the polytope and then look for an adjacent vertex which is better in terms of objective A and then jumped to that new vertex. And we are going to stop when we get to a place where you can get no better vertex and then we know that the current vertex is an optimal solution. So there's a few questions with this. How do we find these initial vertex and then where we have one of the vertex, how do we find and jump to an adjacent vertex which is better? Alright. So we are going to step back for a moment and talk about Gauss-Jordan Elimination. This is something you should have seen in high school or a long time ago. So how do we solve the simultaneous equations like this in terms of X, Y, and Z? Well, in Gauss-Jordan Elimination, remember what we do is we'll pick one of them and we'll use it to substitute out that variable. So let's pick three and we say well this is the same as saying Z is minus Y. So we just replace Z everywhere by minus Y. We get these new form of the equations because now we know what Z value is going to be. Once I give Y value, then you can tell these and work out Z's value. So once we've done this, we'll pick another one of these. Let's say pick the first one here and we'll write it in terms of Y. So this can be rewritten as five over two minus half X and then we'll substitute out of Y from this. And then, we'll get this 17 on two X is equal 17 on two. Now this is easy to solve. This is just tells us that X is one and then we can back substitute into here. If we put one in here, we are going to get that Y is five on two minus a half which is two, and then we substitute the value of Y and here, we get Z is minus two. And so we found a solution to our simultaneous equations. So simultaneous equations is about the intersection of planes and lines. That's exactly what it's solving. And the nice thing about what we are doing here in this Gauss-Jordan Elimination is we are just doing the substitutions and there's equivalents preserving. We are not changing the solutions to the overall problem by just rewriting this equation and substituting for Z elsewhere. And that's why when we get down here and we find this solution to the form of the one we found, then we substitute it back in the original form, it will still be a solution. So how are we going to use Gauss-Jordan Elimination which is about equations to solve our linear program which is about inequalities? So the trick is are we going to convert our inequalities to equations by adding slack variables. So the odd here is like fills the gap between the two sides of the inequality. So if we have this originally inequality which said two X plus two Y plus Z is less and equal to 30, it must be that there is some number s1, which if you added to that would be the gap. So, in fact, that number is 30 minus that value there. And then that's like variable obviously has three Z equals zero. Otherwise, we wouldn't have. So this equation here, because it's like variables non-negative, is enforcing the inequality, and we can do the same for the other two inequalities and just when adding that all of these slack variables and cells and non-negative. And since all of the other variables are non-negative already, it doesn't change. They are the same as all the rest of our variables. And to make things simple, we'll also add an objective variable which we are going to keep track of. So this is not necessarily non-negative but this is allowing us to keep track of the objective in a very similar way that we'll keep track of what's going on in the constraint solving. Now, we can get to this, what is called Basic Feasible Solved Form. We're going to split our variables into two classes, the basic variables appear here on the left-hand side, and the objective is a kind of fake basic variable. And the non-basic variables appear on the right-hand side. So here, x, y, and z are all of our non-basic variables. And in order to make sure that we have a solution, the constants that we find here, all have to be non-negative, not the constants for the objective which could be negative. We don't care. And if we have this form of our equations, in fact, we can see that we're talking about a solution. Because we can say that s1 is 30, s2 is 25, s3 is 20. All of these variables take the value zero and that would actually solve all of these equations. So, a basic feasible solution is actually a solution that satisfies all the constraints and ensures all the slack variables are positive. And we get it, exactly as I said before, by setting our non-basic variables to zero. We set all of x, y, and z to zero, and then we can set all of these basic variables just to the constant value, alright? So, non-basic variables, x, y and z are 0, and our objective ends up being zero, if you work out there. And all of the slack variables are just set to that constant value. So 30, 25, and 20. And you can see that that is a solution, clearly a solution, always equations. An important observation is that every basic feasible solution corresponds to a vertex on this polytope that we're trying to solve. And so, if we have Ne Zha starting at one vertex, then he will try to find the best possible vertex. So, here is the Simplex algorithm we're going to use to solve this problem. We're going to start with the basic feasible solved form that defines the problem. We're going to find a non-basic variable that could increase the objective, and that's the one should have a positive coefficient in the objective row. We're going to call this the entry variable. And then we're going to see how much we could increase the value of this non-basic variable by, by looking through every equation where that variable occurs, and finding the one which is the most constraining, or allows it to increase the least. And that'll give us an exit row for this entry variable. And then, we're going to use this exit row, we're basically going to do a Gauss-Jordan step of pivoting, it's called pivoting, where we use this exit row as a substitution for this entry variable. And then we'll get a new basic feasible solved form and will continue until no such variable exists. So, let's have a look at that in action. So we look along the objective row, we can choose any non-basic variable which has a positive coefficient. Let's just use x, for example here, that has a positive coefficient. And then, we'll look through all of the other rows and find how big could x go without breaking this constraint? So if we think about, if we increased x up to 15, and s1 would still take a value which was positive, or non-negative, it could take the value zero. If we increased x up to 20, then this would be minus 10. We'd be subtracting 40 from this and we get a negative value, so we don't want to do that. We can increase here, x up to 25, without s2 going negative. And here, we can increase x only up to 10, without s3 going negative. So, this is the most constraining row, that's telling us the most constraining row in x. And now, we're going to pivot using this row. So, how do we pivot? We rewrite that last row in terms of x. Here it is rewritten as an equation in terms of x, and then we substitute throughout the remaining equations using this equation to replace x with this expression. And we're going to get something like this. You'll notice that x has now become a basic variable, and s3 which was the basic variable for this row has now become non-basic. Now, we have a basic feasible solution again. Again, we can set all of these non-basic variables to zero and then we can work out the variable of the other one. The objective is now 30, s1 is 10, s2 is 15, and x takes a value 18. And we found a better solution, you can see the objective has increased. So if we think about what happens on our graph of the polytope, if we move to this new basic feasible solution, then Ne Zha has actually found this vertex which is a better vertex. We can keep going. If we again have a look across here, then picking s3 wouldn't improve the objective, nor Y, but picking z would. So our entry variable is z. Now, we'll go through the exit rows. So here, we look at z and z doesn't appear in this row, so that's not constraining it at all, that's an infinite amount. We can increase z without making this violated. Here, we can increase z up to six without s2 going negative. And here, we could increase z up to 20 without x going negative. So clearly, the second row is the most constraining. So, we will rewrite that row in terms of z. There it is, rewritten in terms of z. And then, we'll substitute throughout for z. And here, we'll get this new tableau. And we got an even better basic feasible solution. Again, we set s3 and Y and s2 to zero, and then we get this new solution here with s1 is 10, z is six, and x is seven, and the objective is 39. Now, what happens if we look for an entry variable? So we look across here. So increasing s3 would just make it worse. Increasing Y would make it worse. Increasing s2 would make it worse. So there's no way we can get a better solution than this. This is, in fact, the optimal solution. If we move Ne Zha to that point, we've in fact found the optimal solution, which is an optimal vertex. So what we're seeing here is the Simplex algorithm, and in a more pseudo-code kind of version. This is what it looks like. We start with a basic feasible solved form. We choose a variable with a positive coefficient in the objective row. We find the equation of the form x equals b plus cy, so where Y occurs. With c has to be negative and minus b on c is minimal. Notice if c is positive, we didn't see an example of it, then increasing Y will just increase x and so that is never going to be constraining on how big we can make Y. So, we rewrite this equation and this terms, Y equals minus b on c plus one over c. That's just dividing three by c, moving Y around. And then we substitute for Y in the tableau. And we keep doing this until there's no such Y, so we can't pick an entry variable. And if no such Y exists, then an optimum is found. So the other possibility is we go through all of the equations here and we find no cases where Y occurs with a negative coefficient, which means that Y can actually increase forever, and there's actually no optimum. So this is an unbounded polytope, which won't be very interesting for discrete optimisation cases because we'll very typically be working in bounded problems. Alright. So some questions we should think about, why do we select a variable with a positive coefficient in the objective? Well, that's basically because if we can increase that variables taking the value zero, if we can increase it, that's going to improve our objective. And we choose this equation, where the c is less than zero. Again, that's because if c was greater or equal to zero, then increasing Y would just increase x and so it won't cause any problems if there's not negativity. This Y minus b on c is minimal. That's because if we increase, if we pick another one then we are going to increase Y too much and then another variable will go negative. So we have to be careful that we follow these rules. So is the algorithm guaranteed to terminate? Well, as we've explained, not because what can happen is this minus b on c value is zero and so we can basically change the basis. We can do the substitution, we'll get a new form of tableau, but we won't actually move points because Y which is already zero, will change to still be zero and we won't have actually moved. So in order to guarantee termination, we have to do some kind of anti cycling method. There's a number of methods of those in the literature and I invite you to look up how anti cycling methods are used in the simplex algorithm. So at termination, Y is the optimum found when we don't have one with the positive coefficient. Well, that should be fairly clear because if we look at that objective, then there's no way we can get a better rate from the objective. And if why is there no optimum we know such equation exists. Well, this is unbounded case and you can look at some examples to see why that's the case. Alright, but we have fudged to be here because what we didn't do is say how did you get this initial basic feasible solution. So if we start off with this different problem here, where we've got some negative coefficients on this side, if we just add in the slack variables we write down like this, and we can see that this isn't a basic feasible solution because some of these slack variables in this equation form are going to take negative values. Of course they're meant to be non-negative variables. So this is not giving you a basic feasible solution. We got one in that previous case because all of the coefficients over here were positive, and so it was easy in that case. So what can we do about this? Well, what we're going to do is actually use the same algorithm to get us to a basic feasible solution. And we'll do that by adding an artificial variable A. Alright? So the way you can think about this is we're going to add an extra variable A on this side and of course this A here, if we make it big enough there will always be a solution to these constraints. Right, we can just take any values of x, y, and z. Then we can increase A to be big enough so that this inequality holds. And once we've added that A we're going to just minimise the value of A. So the idea is to get A back down to zero and if we do that then we're actually going to find we've built a basic feasible solution to the original problems, because of course if A is zero here then these constraints are the original constraints. So if I write down our problem here with this A variable in it and now I have my slack variables here, then I can always pivot. So I just pick the A which is the most negative in cost so this one here, and then I can use that to substitute for A and since it occurs in all of these cases then all of these constants will be non-negative. Right. So if I pick it with the largest, most negative value, pick that row and use that to substitute for A, I'll certainly get a basic feasible solution, still with an A variable in it. So here is our resulting tableau and here you can see we now have a basic feasible solved form. Right, so s2, x, y, and z are all non-basic taking the value zero. The objective is negative it doesn't matter we don't care about the objective being negative, and these slack variables and the artificial variables take these possible values. And now we can just apply our simplex algorithm as before and we'll end up with say a final tableau like this. And you can see in this final tableau, A is taking the value zero. Right. So clearly the problem is feasible. We've actually found a solution to the original problem which is that y is 2.2, z is 1.6, and x is 0. First of all we've actually found there is a solution to the problem, but we've also basically created a basic feasible solved form because we can now just throw away this column and then the resulting thing is a basic feasible solved form for the original problem. Alright, there are some cases we have to be careful of, it could be that A is still basic but takes of a value zero. Then we have to pivot it first and then throw away the column. So we eliminate the artificial variable A, we get down to this. We get back the original objective. Right. We have to remember and we actually have to use this basis to pivot out so the had y and z in it so we have to use these things to replace y and z. So here's our new objective in basic feasible solved form. But that's fine, that's not hard to do. And now we really have got ourselves a basic feasible solved form for the original problem. So infact this gives us this two phase approach to the simplex. So, if we're given the linear programming in equational form. We'll add an artificial variable A and a fake objective minus A which is just saying minimise the value of A. We'll basically obtain a trivial basic feasible solved form by this pivoting so I might take the row which has the most negative coefficient and use that as a row to make A basic and then we'll certainly get a basic feasible solved form. Then we'll apply our simplex algorithm to maximise this minus A. So if we reach the optimal and the objective is greater than zero then the original problem is UNSAT. That tells us that there's no way of solving the original constraints without having some artificial value left over. And so if the problem is UNSAT we can just stop at that point. Otherwise, we will get to a point where the artificial variable takes a value zero. We'll remove it from the tableau. As I said possibly that might require a pivoting. If it's non-basic then it's easy we just remove the column. We revise the original objective with the current basis. So now we have a basic feasible solved form for the original problem, with the original objective and then we just apply our simplex algorithm to maximise this objective. So there are lots of other interior point algorithms. So the very first polynomial time version was from Khachiyan and the very first practical interior point algorithms for linear programmers Karmarkar and now all the commercial solvers include some interior point. And these are very very effective for very large linear programs. Then less useful for discrete optimisation because it turns out that we're going to use linear programming mainly for problems which have integer variables, at least some of the values are integer, and it turns out that the simplex algorithm has some useful characteristics for doing that, when we solve mixed integer programs which we'll look at next. Linear programming is arguably the first general purpose optimisation framework. It is a very very important algorithm, the simplex algorithm. It was developed after World War II, and it's a very well used algorithm. And basically it's one of the only real number constraint solving methods that we use about say network flow and shortest path which are special cases. It's also importantly for us the basis of mixed integer programming which is a discrete optimisation technique that we'll look at next. So in summary, we've looked at linear programs and important class of optimisation problem, and the simplex algorithm. Basically, one of the most important algorithms in practice. So it actually has exponential time worst case but we don't tend to see that in practice. And it's the basis of MIP solving, which is why we're very interested in it. There are plenty of other linear programming algorithms and there's much more to learn about solving linear programs. Lots of interesting concepts like duality, complementary slackness and lots more about the simplex algorithm, just the dual simplex and primal dual simplex. There are a lot more sophisticated versions than the simple version we've talked about here.
