Video 6-2: LP Basics & Terminology
CS 627 – Advanced Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-16, 19:54
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:02 We looked at hesy chame problem of deciding how many apple trees of each variety to grow and we had formalized this as a linear program. Um let me go back briefly just to show um the setup again. So there's two variables that we really decide the number of trees of these two varieties that we want to grow. Um there's lots of extra constraints and extra information. First of all, they yield some benefits and some revenue. We want to maximize that. But then we also have constraints in ter terms of space we have and how much space the tree takes. We have constraints on fertilizer and on time for the harvest. So all of these are expressed as as linear or proportional relationships. As you may notice, for each additional tree you plant, you get a certain extra amount of money. For each tree you plant, you need a certain extra amount of space from your total available space. For each extra tree, you have a certain amount of fertilizer and a fertile amount of effort in harvest. Okay, so all of this is um expressed as linear functions. And you see this very clearly here.
1:14 The objective function that's what we in the end get. That's our payout or revenue. This is a linear function in the variables and all the constraints are linear inequalities. That's the defining feature of of linear programs that everything can be expressed as such um a linear function.
1:36 Um the terminology is is not super important but I want to use this uh because we refer to it repeatedly and it's it's somewhat standard so maybe it's it's helpful um that you get famili familiarize yourself with this a bit. Um the decision variables these are the main variables that we control. Um at this stage we don't distinguish. So variable is just some of these formal objects here that can take on values. Uh here they're always real numbers. Then um taking all the variables together form a vector. Uh the values form a vector in in r to the n if there's n variables. And we call that a feasible solution if it satisfies all of those constraints. Now you'll immediately see um remember the picture from last time. This has a geometric meaning because we're we're taking some n-dimensional space for simplicity. Now, here is the plane in this example. And then we cut out half spaces. All of these constraints are such that they they define a line and a side on which you have to live. So a half space just means in this total space of options there's a line and you decide everything on this side is okay.
3:01 Whereas this is forbidden. Right? If you keep doing this, if you just add more and more constraints, you're always going to cut out half spaces where you take the union of uh the the intersection of of a certain of a finite number of of such half spaces. It'll always look a bit like this. Maybe these are all directed inwards so that the intersection of all those half spaces is precisely this this part here in the middle.
3:32 And um because it's defined by half spaces, it will always have straight sides if you like hybrid planes that define this blue region. Um and so that's always a polytope or a poly polygon. Um yeah, polytope I think is the general term. Polya in German for the one that may be unbounded. In principle there could be one side open and extend into infinity.
4:05 Okay. So the set of feasible solutions will always form a polytope. And really all that means is it's an intersection of half spaces. and a half space is defined by a linear inequality in in the variables. Okay. Um the objective function is is this term that we maximize and it will have some optimal value in well uh we we'll come back to the different options but in in our case when this this polytope is is bounded there's always going to be some maximal value. the function is is monotonic in some sense. It's even linear. So, um it will attain a maximum on this bounded region for sure. And it uh well, as we we've seen in the example last time already, it will be at a at a corner point. Uh we'll come back to that. Um and this this maximal value in this case when we maximize the best possible value is the optimal objective value. We'll always call that Z star.
5:22 and an optimal solution that yields us this objective value also denote by the stars. So star always means optimal we also use that notation for other optimization problems.
5:37 Um yeah this is then called the optimal solution because usually this is what we care in care about in the application not just the total value you want to earn but al also how to get there. Um that's that should be all that we need for now. Uh this we've seen last time. Uh let me show this So here's the same same kind of setup. um in an animated way. It's the same problem. Um now here you can slide this along a bit more uh continuously than in my animation. But of course there will be some point here and it will always be this case a corner point where this is optimal.
6:43 Now uh here it's set up so that I can uh play with the direction in which this thing is optimal. Um this is of course changing the problem. Now what I'm specifically changing are the uh the objective is the objective function which is not shown uh either way. So suppose some different revenues for the two trees essentially here almost the same now for both uh then it can happen that the optimum is simultaneously attained along a whole line. But note that even if that happens of course also the end points of the line will be optimal points. Right? So really that's that's all that can happen and um we can without loss of generality assume that we'll look at these corner points as optimal solutions. We'll never miss an optimal solution that way.
7:51 Now something I hinted at last time as well briefly I think is that uh these solutions are real numbers and so they may or may not always correspond to something that you can really uh uh enact in practice. So here this optimal point has a fractional coordinate and it's a bit hard to plant this a third of a tree and we'll we'll come back to that. Um, of course in in general that is a problem. Maybe here it's enough to just say I'll round down and forgive that little bit of money. Uh, note that we so a bit more uh terminology but I hope it's it's intuitive enough that these two constraints for the harvest and fertilizer are really tight in the sense that these are precisely matched or the the orange point lies on these lines. So I have no wrigle room with respect to the fertilizer and harvest time at all. I cannot increase even by a tiny epsilon my um harvest uh time demands or fertilizer demands. Whereas the orchard constraint is far from tight. I would have had space for more trees.
9:10 let's also see how relatively easy it is to solve these in practice. I think this is insightful to have a look at because it first of all is a bit less uh magical than if I just show you some some random animation that uh for fixed examples you could always fake. Uh so here you can look a bit under the hood. So what I've made is uh a Google collab for this. Um it uses some libraries of course to make things convenient. There's a lot of libraries to solve LPS and no particular reason to pick any over the others. I think this one is very friendly in how you specify the constraints. Looks almost like they are on the slide. And so I'm I'm not going to go through um this much. Uh let's run this already because it takes a bit. I need to install this. Um the way you specify in this in this math opt uh linear program is you give you give this a name. This gives you they call it a model everything. Then you have variables. These are the uh decision variables we want to use and you give them some name. Now here this LB stands for lower bound um which is essentially part of our problem in this case. You could of course also model that as a constraint.
10:33 This is a linear constraint s greater equal zero. Uh the reason why they offer you to do this here at the declaration of the variable is that they can more efficiently handle it if it's specifically target labeled as a lower bound for the variable. Um, and then you add these four constraints. And what I what I prefer about this this new library compared to what I've also used last last time I did the module, you can directly name the constraints so the program knows what they're called and can tell you can tell you things about it. Otherwise, I've literally typed up these exams in Python syntax and you can even pass them as this unevaluated expression. You know, Python allows these things. Um, so it looks very much like what you had on the slide. And then you tell it what to do. In this case, we want to maximize. And again, you give this linear function as an expression.
11:26 And then it'll just do this in a split second or so. And it'll tell you the optimal objective value. And it tell you it it'll tell you for the two variables how much of each uh you want to plant. And you see here that uh you use these symbolic these objects that represent the variables to access the values. It's rather nice to um to look at. Um yeah, you can also draw the P. Let me let me stop with this. The whole point here is it's very quick to type in an LP and get an optimal solution. Now you have to trust this solver to do the right thing. But you know uh I have some confidence in these because they are heavily used. We'll come back to this question of how can you be sure that this solution is indeed optimal. There are more principled reasons or more principled ways to tell in the context of of LPS.
12:28 Um very useful but we'll we'll delay that a bit. Um for now let's just say we trust the piece of software that millions of people use. as I can be a great shortcut to getting some some solution to a problem.
12:54 Okay. Uh a bit of the math for the background. I'll maybe not stress this all that much. Uh but in case you want to know what the solver does, I think you should have an intuition. There's many corner cases in details and we really don't care about the numeric here. Okay, this is what really makes this in practice a bit more tricky than what I describe. You're working with floatingoint numbers, you still want to be correct. So, you have to be careful with numeric. I'm going to sweep that under the rug entirely. Uh the general form of an LP, if you think about the most general way you could write this is you say in this case always minimize um some linear function of n variables. uh the coefficients of the cost function here minimizer cost that's the pneummonic is the C's and then you have side conditions in principle you could have uh different kinds of linear constraints they could be equality constraints or lesser equal or greater equal uh let's have a bunch of each of the flavors and then you could have some variables the first are that are non- negative and the others uh we don't care about their sign and um I'll wrote this I wrote this in this kind of silly way of course this is just not a constraint at all but I want to explicitly write that there is no constraint so there you go okay this is the general case um that's pretty much all you can express with these after sorting the constraints that's all you can do with what I allowed you um if you specify any such thing. If you just plug in any numbers without care for these C's and A's and B's, you'll always end up in one of three cases, uh the usual one that we have when we come from an an application that we model, there will be some finite optimal solution and this uh polytope described by the by the constraints will be bounded. There's in some direction always a constraint that limits you from continuing. But if you just carelessly select numbers, it could be that the constraints are completely contradictory. So there's no no point X in satisfying all these constraints at all. Easily done, right? Um I guess if you have equality constraints just by you have a lower dimensional feasible region. So with probability one, you'll get this if you just pick random numbers with equality constraints. Okay.
15:24 Anyways, um we're not going to pick random LPS. And the other thing that can happen is that the region is unbounded. So you can continue uh to improve and improve. Let me show this graphically and then I think it's it's rather easy to see.
15:51 Here's an example of again uh the the apple problem, but we've added another constraint somehow. Uh, we need to at least buy 1,300 trees. Stupid contract. But then you see this this this constraint forces us to be um on the wrong side.
16:15 Okay. Here the the hatching points towards the excluded side from different to what I draw what I've drawn manually earlier. Uh so this this constraint stops us from having any feasible point. Okay. The other option is that we have an unbounded region.
16:31 So here uh I can just make this better and better and better and it escapes to infinity. So there's this uh there's no bound on how good I can make my solution. Let me call the LP unbounded.
16:54 That's in general the three cases you can have uh for minimization means negative infinity. Uh the the crucial fact is that all of these we can easily handle. We can give an LP to a solver and it will tell us tell you in polomial time which of the three cases applies and if it's case a an optimal solution with a feasible with an op well an optimal solution and it's feasible its objective value I should stick to my terminology it'll tell you the optimal objective value and the optimal solution u an example for uh a more algorithmic LP that maybe you've seen in disguise case or even explicitly uh is the maximum flow problem in a graph and this can be entirely written as a flow. So we have a graph I'm assuming you know ST flows. So if not then ignore this it's not super relevant for now. Uh we have a variable for each edge giving you how much flow do you send across that edge. We want to maximize the total flow that we sent which if you have some ST flow there's an a source and a sync and everything goes somehow uh from S into this network and then out into T. So if you look how much goes out of S that's the flow value this is what we want to maximize uh here written as an extra variable F and then a constraint that tells you this is the excess at S right what flows out of S from S to V minus what flows back into S in general you could have flows that circulate then we have a constraint for each edge that tells uh tells you on the along the edge VW I can have at most this capital C of VW flow and so the corresponding variable needs to be at most that um we also want non- negative flows or weekly positive flows so we'll have that for every edge and the last thing is this flow conservation condition at every vertex leaving out the start and the sync where I have actual flow entering and leaving the system. Everything has to be balanced.
19:13 So what flows into vertex V summing over the incoming edges has to be the same as what flows out of out of V summing over the outgoing edges. Okay, that's a typical example. If you write it like this, it's directly an LP and is very convenient to just stick into a solver instead of uh rushing up your admin's carb etc. Now, of course, you can usually solve max flows faster than general LPS. So, if you care about performance, there's still um a point to be made for handcrafted algorithms.
← Video 6-1: Linear Programs ExampleVideo 6-3: LP Reformulations →