Video 6-4: The Simplex Algorithm
CS 627 – Advanced Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-16, 27:17
The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.
0:03 Next, I want to very briefly show you how to solve LPS. And the idea will not be to dive through all the linear algebra on the slides in detail. You can do this if you want. My goal was to have explicit formulas on the slides just for the sake of showing these are just explicit formulas with some linear algebra terms and you can evaluate them in a program easily. There's there's nothing magic going on. it is a bit annoying and confusing. So, um if you see the slides, you may agree, but the intuition is really not that hard. Okay. Um let me introduce a bit of the notation and I'll show you some uh some parts of this in in animation as well. Uh we'll fix this normal form here. So, the lesser equal normal form. Okay.
0:55 Um if I have just two variables then I get some picture like this in the in the plane. And here maybe I have even 12 constraints. The their number can be large. Uh but uh I can still draw these two variables as x and y. Then these these constraints in general they just define some some half some uh or each of them defines hyper plane or a half space. I can have uh the equality is uh uh hyper plane and these are half spaces and my cost function you should think of as a direction of improvement. If you're sitting somewhere suppose in the nicest way uh to visualize this the cost function improves whenever you move downwards in this picture is a I guess a way of saying that the x direction is completely irrelevant for the cost function. You want to minimize the y direction. The thing is that all I've said above is rotation symmetric.
2:02 you could rotate your coordinate system and it wouldn't become false. So in a way you can always rotate your whole world so that this is the direction you optimize. Okay. Um so then intuitively what you do is you just roll down a ball along this feasible region. If you were to somehow start here, then maybe it falls down here and then it just rolls until it can no longer roll roll down. Intuitively, that's what we want to do now without building this out in in physical space. How should we do that?
3:07 again on our uh Apple scenario from earlier. I'll assume for now that the point in the origin is feasible as it happens to be in in Hess's case. Just not planting any apples won't earn you anything, but it's a an allowed solution. Um this is this is already taking um the equality form.
3:39 uh where you introduce for all the lesser equal variables the slack variable that uh makes that constraint uh an equality constraint. And putting the initial variable at the origin means x s and s and k are zero. And um any kind of difference to the lines to the the colored lines are equal out by setting the slack variables respectively to that slack value whatever that that is left between where we are and and the this value of the green line on on the slow for the red one. We don't even see it all up here. Okay. um how can we move in a strategic way to the optimal solution? Well, fact one is it's enough to look at these corner points of the feasible region. Okay. Um we'll eventually find the optimal solution if we do that. If we just enumerate all of them, this will be too slow. But uh let's as a first step stick with that. What are all possible uh solutions that could be uh such an intersection point? Well, take any in this in this two-dimensional space. Any such corner point is the intersection of two constraints.
5:04 This point here is the intersection of the um k greater equal 1 greater equal 0 constraint. So the s greater equal z con. No. Yeah. Ss greater equal z. That's that vertical line and the blue line.
5:23 Okay. So, of course, this is um a linear in a linear equality system with two equations and two variables that's going to have a solution. That's true for any pair of points. Of course, these lines all intersect somewhere. If I zoom out enough, they all have some intersection point. Many of these intersections points are in uninteresting because they're very bad and unfeasible. But in principle they exist. So all I need to do is to move from one intersection point to another one. I could enumerate them all but that's going to u blow up quadratically and in in higher dimensions if you have n variables the power is n. So that's very bad. But we don't want an arbitrary intersection point anyways. We already know we're at a point that's not horrible. It's at least feasible and we want to improve in this orange direction. So what we can always do is among these two lines that intersect at the current point I can follow up down left or right in this case there's always four directions here and um I can follow the one that is has a less than 90° angle with the orange line or um is is if you take the the scala product is not is is non- negative so that the orange line improves if I move in that direction.
6:48 So here there's these two directions that I can take where if I move in that direction, the orange line would move up and that gives me a overall a better uh outcome.
7:02 That's the part while we're not locally optimal and we'll come back to how to check that in in formulas. There is a way to improve in either this or this direction just following one of the defining constraints of our current vertex and you can pick any of them and slide up there. What this does to your solution is that now you're the defined by the intersection of two different constraints. So the original variable here k is no longer zero. um but some other variable will be zero and that's indicating that you're now at a different intersection point and there you can do the same. You again have uh directions to improve. The one where you came from certainly isn't it. Uh but the one along the blue line there is one that improves and so you move in this direction. In this case in this small example that's that's the end of it. So what we need is a way to check whether we're already at the optimum visually there's no way from the current intersection point to improve along any of the feasible uh parts of of the constraints. So I mean I could improve if I move the green line further up but I'm violating the blue constraint. I need we need this locality uh local optimality check and then we need a way to move in this direction.
8:30 Okay. So, um that's what we used algebraically. We have some constraints and um there's a unique intersection point unless it's somehow degenerate. Let's um sweep that under the rug for the moment. So we're we're sitting at some specific vertex at the moment. And this is the intersection of a selection of the constraints. Now I can only use n constraints. I need to match the number of uh equations to the number of variables otherwise I may not have a solution. Right? Um so I might in principle have many more constraints like in the example here I pick n of them or two in our example that defines a vertex. Uh we know from what we've observed the fact that these are linear functions under on a on a convex linear constraint region we'll always find an optimal vertex. So we only have to look for that. There's too many to do this in brute force. But we can find with this uh simplex algorithm.
9:45 That's what I've shown you in the animation. U precisely this the wordy informal description of what we've done. Unless there's no intersection point among the constraints at all, you find some feasible vertex. And while that's not already locally optimal, you move towards one of the uh directions in which you can improve. We'll we'll come on the next slide to what that condition is. It could at this point happen that you can always improve. There's no way to stop. Uh well then then the problem is unbounded. Otherwise, you move to one of your better neighbors.
10:31 uh how do you do this actually in in linear algebra? So um if we do uh equality constraints um we can here so this is potentially after if you start with the inequality constraint we've added variables for them these slack variables so afterwards you'll always have more variables than constraints because I just added another variable for every constraint that's the way I I find it more intuitive we actually Start with the lesser equal normal form for the algorithm. We want the equality form. But that means I'm just adding these slack variables. So this will always be true. I always have more variables than constraints. But the constraints now are equality constraints. Uh let's assume that the constraints are not redundant. So then the rank of our matrix has to be the number of constraints. And uh that means I can always pick m of the constraints to find a basis of my the spent uh space of the of the matrix.
11:40 Um and that's basically what we use also for for finding the solutions. Um, I can now take the indices that correspond to the current basis and say I'm only looking at some of the entries in X. That's my basis variables. It's just a name and the others are the non-basis v variables. Um, what's the benefit of doing that? Well, I can I can rewrite all these quantities um to consist of just the indices in J or the indices not in J. The benefit that I have is this is equality constraints.
12:25 If I look only at the basis rows, this AJ is as it says a square matrix and is is invertible because it has full rank. I also have these other indices where I don't know this. So in principle a right we said we have fewer constraints than variables. So a looks a bit like this and I have my long vector of variables and I say my long list of sorry the short list of right hand sides.
13:04 Now, if I pick out some rows as the basis, these uh same here, right? Not going to do a very good job here. Um then it's not even the same number. Oh god. Uh maybe like this.
13:21 Then here what I'm left with if I just take the red matrix is square and the rest is not. So the result here will be a vector of this shape. I can split that into two parts. It's a linear function. Now, uh because this is invertible, I can multiply from the left with the inverse matrix. That's what happened here. So, I have XJ I bring this to the other side B minus and then I multiply both things on the right hand side with this from the left with this inverse matrix. And so, I can always express the basis variables as a function of the other variables. So I don't actually have n independent variables. I only have these n minus m independent variables and the basis variables are determined from them via this function. Right? There's a tells you what they are. Um and that means I may as well choose these others uh in a convenient way. For example, I could just set them all to zero and then my basis variables get some value. But uh this part then just cancels because it's zero.
14:37 Okay. And this corresponds precisely to the vertices in the picture, the corner points when I pick some intersections in this way. Um not all of these bases, not all of these selections of variables are a feasible solution. That's a different story because maybe these this is just some formula. It may not give us non- negative values.
15:01 But we can easily do this check by just computing it. Okay. Now the next step this is telling us how we move from one corner to the next. The next thing that we need is how do we know whether we're optimal and what is an improving direction and uh okay this is uh just rewriting what we had from the slide before. Um we can't simply modify individual variables because we have an equality constraint. So this is uh rather rather tight. We always have to move variables in accordance. Now for the basis variables these are fixed right these are given in terms of the others and for the non-basis variables they're fixed at zero so I cannot decrease them the only thing I can do is increase some non-basis variable now if I do that then my basis variables will also change and they might go up or down in general I don't know so if I change one of these jar variable ables by a little tiny bit. I'm moving in a certain direction.
16:20 And um the idea is to essentially model what this little movement does to our objective function and see if it improves. The objective function is is ctx by definition. I can also split it into the basis and non-basis part. And um here I'm inserting what I know for XJ. Right? This is the equation from here.
16:57 And then you can split this up and find that you're both multiplying on the right here with this XJ bar. Uh and so there's something that has no dependence on the variables. This is a a constant term plus some other vector some new kind of cost vector multiplied by the non-basis variables. Aha. So, um, each of these tells us if I move with a single of the non-basis variables up by a little bit, what happens to the cost? Is this a positive or negative coefficient? Does the cost go up or down? That's the local test that we need. So, we can just check um if these are all all positive, so increasing this makes the cost higher for everyone, then we're locally optimal. And if not then this also tells us um where we can where we can move if there exists an index that is not a non-basis index. So uh where we can increase the variable where the these um what's the name of the CI reduced cost I think where the reduced cost coefficient is negative. So I I can improve my cost by making that variable a little bit higher. Then I should do that and I should do that in a way that I'm increasing that just by as much so that the basis variables are not negative.
18:33 And so um that's also what the animation was trying to show earlier. Let's look at uh same example again. So I'm uh come on.
19:02 So if you want um let me maybe point out there's the algorithm written out with the formulas as a inserted instead of the the plain plain text before and you can step through and it works out precisely the um uh concrete numbers in each case is a bit overwhelming. It's I found it useful to step through a little bit um to get an intuition the first few times. is a bit overwhelming but uh maybe you find it useful. Uh so let's let's play this example again. And what you want to watch is is this variables panel. Uh the first thing is we find um we find the reduced costs. That's the CJ uh tilda that we had on the slide. And here it turns out for both of the variables they're negative which means improving the non-basis variables by um the non-basis variables here are s and k. Okay, these are zero at the moment.
20:08 The others are determined from them. These I cannot reduce. They're already at zero. But I can make them bigger. And in in this case, both of them are multiplied with of course because these are literally our trees. Planting more trees gives us more money. So, I should pick one of them.
20:31 And there's different rules which one to pick. Um, in this case, I think it it goes greedily for the one that gives you more more gain. And now we decided the direction to go. We haven't changed the variables yet. But now what you do is you increase this K. Okay, the animation was too quick. um you increase this k gradually until the first other variable the non-basis variable hits zero and then you have to stop to not leave the feasible region. Okay, what I'm trying to do here is give you the connection between the linear algebra and the and the and the pictures because I think the pictures stick in mind the algebra never does but the algebra generalizes to n dimensions where the pictures don't.
21:18 So precisely this local test are we optimal or not? If the answer is no tells you what to do and um you know that this should now enter the basis. This is one of the variables that you should now include as the ones that are no longer set to zero. So some other has to go up. And the last step is by how much. And that's um is another simple calculation.
21:49 Uh you can see it in in the animation where it says uh but in principle you just increase it as a continuous process. Imagine you increase that non-basis variable until one of the basis variables hits zero. Okay. The simplex algorithm that's what I've shown you. This is precisely that. There's a few corner cases I left out. Again, if you care, most of them are by now included in here. Uh you need to um find an initial feasible solution if the origin isn't. Thanks.
22:31 You need to find an initial feasible solution in case the origin is not feasible. That can happen. There's a simple trick to do that. and you have to deal with um unbounded um LPS and something you don't even have to explicitly worry about but in in the analysis or in the thinking uh there could be degenerate cases where more in in our picture more than two lines meet at the same point. It turns out that's not really a problem, but you have to pick make sure you're not cycling there because you could have a step that doesn't improve your cost function. If you're not careful, you might repeatedly do the same step in in a circle. Uh but all these things are kind of easy to solve and known and the solvers of course do all that. So um a conceptually simple algorithm I would claim you just walk along these edges of this polygon um and and uh see whether you can improve still and if not you stop in your optimal. It's rather easy to implement subject to doing the numeric right which we ignored. There's very good solvers that do this in practice that are robust and scale to millions of variables. uh the collab that's linked has some larger transport networks benchmark example but even even in collab runs in 10 seconds with millions of variables. These things are really scalable. Um simplex itself as you may know is actually an exponential time algorithm. There's a a nasty example that makes it go uh visit all the vertices in uh in a polygon.
24:22 Let me show this to also showcase the 3D thing. Um Okay. Uh what you see is is a kind of cube. It's a bit of a deformed cube to show better what happens. Uh but it with the usual rule for picking a direction of where to go next. What happens is that um too much for the uh uh oh okay running very slow. Either way, um, it cycles through all the corners to get to the final optimal solution.
25:35 I'll stop rot trying to rotate it. Uh, this was something that was that was rather uh early discovered that in principle the simplex algorithm can be can be made to take exponential time in in the number of variables in the dimensions. Uh, that's not what we want of course.
25:59 Yeah, sorry. This is this is unusable here with the recording running next to it. Um, there's two answers to this. For one, uh, one can prove that this is a corner case that rather happens very rarely. If you change the numerical values a tiny bit, the worst case goes away. It's a rather confined contrived worst case. Um and the other is there's just very different algorithms that are proper polomial time even in the worst case. Uh these are less intuitive because they are working rather with the whole geometry of the space. They they kind of repeatedly cut this the space you still have to look for optimal solutions in in half. But then you have to somehow argue about why this binary search in a continuous space is eventually terminating. Uh for us it's enough to know that we there are these worst case poly time algorithms. uh practical solvers will usually uh the the open source ones combine simplex with a bit of interior point methods and the commercial method comp commercial commercial solvers this is where they where they shine in the cases where simplex is struggling a bit they invested a bit more in the engineering
← Video 6-3: LP ReformulationsVideo 6-5: Integer Linear Programs →