Video 6-1: Linear programs for modeling problems

0:03 In the next unit, we'll look at some more advanced ideas for still parameterized algorithms um both upper bounds and lower bounds. Uh things that deserve a bit more a bit more context. And so um I took them out of the other two units. Conceptually they belong in in the previous two units which were about uh algorithms with them uh parameterized techniques or lower bounds. Uh but these felt they're distinctively more involved and bu build on some uh extra steps. So um I split them off uh to have the the space to devote a bit more time to the setup. And um hopefully the techniques go well beyond these specific uh examples. Um what we'll start with today is uh a bit of a a detour first on on linear programs and and linear optimization and then we'll apply uh LPS the first first application we'll see will be for a better kernel um for uh the vertex cover problem and there's a short section at the end also on some advanced lower bounding techniques. So far we've really had this dichotomy. Either there is some FPT algorithm with an arbitrarily bad function potentially f of k f could be a really fast growing function or it's w1 hard and we don't expect any kind of ft algorithm. But for problems where we do have an fpt algorithm, we might want to know if we can say something about this this function f of k. a specific algorithm always gives you a specific function and that may or may not be a good one. It'll be super polomial but maybe uh it's not clear how far you can push it down and there we'll see some uh some techniques with stronger assumptions giving you some lower bounds that go beyond saying there's no FPT algorithm whatsoever. That's the plan.

2:02 Uh let's start a bit with the the practical side of linear programs first. And so I pitched this uh really for for people who have never seen it. Uh if you've seen it, maybe the first part is easygoing. What are linear programs? First of all, the name I guess is is just showing the age of the technique. It's from uh just after World War II. And a program at that point didn't mean a computer program really. Uh there were no such no such things in widespread use. Uh instead is is more the planning or a program was a schedule rather. So think of it that way. It was motivated from the application to call it like that. It's a bit like dynamic programming. Same same kind of era. So uh what are what are they? Uh the name is just what it is. uh I guess it's it's here to stay. It's a class of optimization problems and unlike most of the things that we deal with in this module and most of computer science, it is about continuous optimization, not discrete or combinatorial. It does it does have a combinatorial flavor to it, but we'll come back to that. Uh so um is always something you want to minimize or maximize. That's what optimize means. And there's some side conditions that constrain you in doing that. Now the uh interesting bit about linear programs is that they can be solved exactly in polomial time in a completely clean sense.

3:45 uh so I didn't define the formal problem to say in in in P we would have to say what the decision problem is then really the decision problem is a is a bit less exciting maybe uh because it's really just talking about linear inequalities uh but yeah so the um the appeal of linear programs comes from the fact that we know solvers that can solve them worst case polomial time uh and they can also be solved in practice uh for for really large instances. I mean one reason is that it's a polomial time algorithm but also uh because of its widespread use people have tweaked these algorithms and made them really clever. So it goes far beyond saying there's some polomial time solution. um it's a bit uh is a bit like SAT solvers which are often fast in practice but here the difference is also in theory these solvers are clearly polomial okay uh the specific names uh are maybe not so important if if you've seen LPS before you've probably seen the simplex algorithm and maybe know that that one's not polomial in the worst case but there's other methods that Let's uh introduce what this is about with a a little um a little whimsical example. So suppose you're you're an apple farmer and um you're trying to maximize your profit, but of course there are constraints of real life that stop you from just earning infinite money. I guess the way to earn infinite money is is to have as many trees as as you can think of and also sell your apples at infinite prices which uh for for various reasons won't work. So the real thing um is modeled here like this. So you're you're uh you're devoted to promote the uh varieties that have grown in the area for long and have picked. So these are like the the last two years of um Hessa's uh specialized apple varieties that they picked as um historically relevant varieties. Doesn't matter so much. Uh they're just two names sen two types of apples and that's all you you're going to do. you plant trees of of type S or of type K if you if you prefer. Um, now they have different yields and also the apples yield different prices. So here we're just saying per year one tree of each variety gives you a certain amount of of money at the end from selling the apples.

6:38 uh as he has an orchard of a certain size and each tree needs a certain amount of space and also they need fertilizer and time to harvest. Okay, these are the the main constraints. We have space constraint. We need to put fertilizer to get the trees growing and they have different uh requirements there just because this is a bit more uh uh sturdy one and the other is a bit more needy. And then the harvest um I don't know how to justify the three times increase. It made the numbers work out nice. Uh suppose this uh is basically um uh what can you make up? So these you have to uh pick at the exactly right time and for the others it doesn't make such a big difference. You can pick them and they ripen after you've picked them. Um, now the other assumption is that Hessie really has a tight budget and can only afford a certain amount of fertilizer per year and can only hire people to do the harvesting for a certain amount of hours per year and these are hard constraints at that uh at this point. So that's that's the setup.

7:50 Okay. Yep. Question. Everything in this problem must be linear in relation to other Yes. Uh for for linear programs, the question was if if everything has to be linear. Uh for linear programs, everything has to be linear. Um the way it's defined here, it it actually is linear. Um because uh the the amount of space per tree is is a constant. The amount of fertilizer and time per tree is a constant. And the amount of of money you get out is a constant. Um as often this this makes sense to a certain degree. I think it's it's fine that here things are proportional to the number of trees for a while. Now clearly nothing in real life is ever linear forever. Like if you were starting to to plant a trillion trees, you'd certainly not receive the same price per apple than if you have a normal amount that doesn't just flood the entire world with apples.

8:52 and similar I guess for the other things there's there's kind of um limits where it start starts to fall apart uh but within reasonable con and I mean we're we're constrained here anyway so uh we won't grow a trillion trees um locally it often is a reasonably close approximation to reality to have this linearity assumption and so uh is the very critique that um the inventors of linear the inventor of linear program George Dansik got in when he presented to the math audience back in uh at that time uh his algorithm to solve those and uh they also objected yeah the world is not linear right um but it it seems locally it often is sufficiently linear that it gives reasonable results uh and LPS are used in in logistics and and planning and and scheduling a lot where this seems to be good enough uh but it's of first uh legitimate question um here it's it's essentially you can say it's a modeling assumption. So the question is how many trees of each variety should should we plant to maximize our maximize the profit and maybe also interesting if you think of it from a economic perspective we're constrained by various things here which is the tight ones are we uh well maybe you can you can try to make a guess like um the result will be something u maybe you can guess how much money can he make in a year from from this orchard if he picks the best combination of uh of trees. And what's the actual constraint that hurts us where that stops us from earning more? Do we run out of space or fertilizer or harvest hours or some combination?

10:46 Time harvest hours. Okay. And any guesses for the overall profit? You can do some quick like uh so we're going to have from the space I guess less than a thousand trees and so on and so forth. You can do some quick bounds, right? It can't be more than a,000 times this. So 250,000 seems like a a very optimistic upper bound. it's probably going to be lower if you look at some of the other constraints. Now, this is a simple problem just uh there's two variables, right? The number of trees I grow of type S and the number of trees of type K and the the numbers are small is all relatively easy to figure out manually. Um so in in this case you can work it out. In general maybe you see already that this is uh is helpful to have a computer help So this problem is a classic uh operations research question and you can write it down as an LP formally like this. We're trying to maximize the profit which is 195 maybe you have to go back once in a while for the numbers 195 for each type S tree and one 255 for each type K tree. So I'm just picking two variables S and K for the number of trees of type S and the number of trees of type K. And then we have some constraints. Um the easiest are maybe the last ones. We can't build negative trees. Why would that ever make sense? Yeah, you know, optimization problems sometimes do funny things. If you say you run out of harvest hours, the uh result could be that you uh do negative trees of one type to create time for harvesting from the other trees, which mathematically might work, but of course doesn't make any sense. So these are uh constraints that we need for that purpose and the other three are just reading off from the slide. um the total space is bounded by four times the total number of trees and then for the fertilizer and harvest hours you get these two.

13:02 Okay, so far so good, right? Um okay, some some terminology to bring this back to land of of math and linear optimization. We call this thing the objective function. That's the thing we try to max minimize or maximize. The direction of optimization is called the optimization goal. Um well, we we'll come back to all of these. And one of those inequalities is called a constraint. Um and we give the the the whole thing a name just to be able to talk about it more efficiently. Okay. What else? The variables. I forgot about those. I mentioned s and k the number of trees. Um the implicit assumption is that these are always real numbers. Now uh some combination um some some uh values for the variables here in some is effectively a point in R2 is called a feasible solution if it satisfies all the constraints. You can pick arbitrary numbers and that's always a a value for the variables but not all values for variables satisfy the constraints of course.

14:21 Um then the largest possible value or the best possible value in general for the objective function is the optimal value and we'll abbreviate that that with um set star just have a short notation and um an optimal feasible solution. So a a solution that's feasible and achieves the optimal objective value is called an optimal solution. And we'll also denote this by the variables with a star. Now this need not be unique in general, right? It could there could be many ways to pick the parameters the variables to maximize the objective. Um but any of these will be called an optimal So apart from uh manually messing with um the problem and in this case that's good enough to figure out the optimal solution. Uh we can also do a very uh systematic approach that will effectively lead to um the the simplex algorithm because it's in 2D with two variables. It's easy to draw. And so just to go over this quickly, we have um we have a constraint for the space which means I really should have put uh so this is um pointing this way, right? We're below this below this line are all the points that satisfy this constraint. So we've cut off this part of the region. No point up here can ever be useful. But all the points down here so far are fine. Now we can add one constraint after the other. For example, the harvest constraint is this blue line. So everything below the blue line is fine without constraint. And if you take the two together, you get this uh region below the two lines, below the minimum of the two. So so far I guess uh I'm getting new lines each time. So that's the feasibility region so far. Now it's this region. Now we have a third constraint, right? The fertilizer. Aha. And now you see actually the region is shrunk to this and the space constraint is is never really relevant. It's entirely outside of this area. So only points in this in this uh lower part can ever be feasible.

16:45 Um what's missing is the non- negativity constraints. So the actual feasibility region is this purple shape here. In general, you can already see here it's always going to look in 2D like a a convex polygon. So a thing you get as the intersection of half spaces. So you take a line and everything to one side of the line. If you intersect an arbitrary number of those, you'll always get a convex polygon where all the corners um where all the vertices are on um on the convex hull of the thing. I don't know if that helps you. Okay, but that's not all. So, we know all the purple points are feasible. They satisfy all constraints. How do we find the optimal one? And the graphical way to do that is uh to plot the objective function. And the objective function you can say um I'm fixing all values for X and K for S and K that give me a a fixed certain profit say €50,000 and they all lie on this line because the objective function again uh is also just a linear linear number. If you set that equal to 50,000 you get a certain line. That's the one that's drawn here. Now, uh it looks like that's not the best you can do. You can pluck in different values for the re for the um re uh revenue and you get a different line. And you see that with larger numbers, it just moves up and down. It stays in the same slope uh just the intercept at the y-axis is different.

18:31 And you can keep pushing that line up until you start to leave the feasibility region. And so at this value, €155,500 is the point where you exactly cut this corner. And at that point, you have to stop. If you increase it one further, then you're outside of the purple. You don't cut the purple region anymore.

18:58 Okay, good. So that's the optimal point. And you could read off uh you try to read off from the graph what the solution is. But of course you can just solve the equations. So what what else can we learn from this? I mean first of all uh the solution tells us to plant 100 trees of type s fine and uh 533 and a third types uh trees of the other type. That already hints at one problem. The solution uh could tell you things that might not make sense because it's continuous. Uh but let's suppose this is not a problem in our case. We just uh give up one tree. Um and indeed both the harvesting time and the fertilizer are tight at this point because we're lying on the green and blue line. So both of these constraints are are maxed out. We could not have more trees for for two reasons if you want.

19:57 Um whereas the space is never a problem. In this case, it's boring because it lies completely outside. Uh it could also have a line here where uh it would sometimes make a difference. But if you're if you're Hessie, you know what to change now. You need to somehow get more fertilizer and more more hours for harvest. Whereas you don't need to buy new land. Maybe that's a good thing. Okay. Questions up to this point?

20:41 it's given in uh like um depends what your task is. uh in this case it's given right it's is this function is the objective is uh could have used the colors here that was the objective function now all that gives you is the slope of this orange line and what it doesn't tell you up front is where uh to put it in how high to put it that's the task of solving the LP But uh we'll see like this this systematic ways to get there. Um I just wanted to make one one point namely uh that uh this is very easy to do in practice if you need to.

21:39 Um, so here's a a little uh Google collab with code to solve this specific problem. Um, the setup is is essentially taken from Google's O tools. Um, which makes this very very easy to do. And that's all you need. So you define well you need you need to import some solver code and so on. But this is a As I said, I just took this from their documentation. The real problem starts here. You uh tell it the variables s and k and you can give them um a range. So here that's encoding the non- negativity constraints. It's between zero and infinity plus infinity for both variables. Then you put in the constraints and by the magic of Python, you can actually give these as expressions and it'll take them apart. Again, it's a pretty concise notation. These are literally the constraints we had on the slide just typed up in in Python. Um, and you tell it what to maximize or minimize and you say solve.

22:43 and there's some uh boilerplate code to get the result and then it spits out the answer. Okay, so if if you ever need to solve an LP, don't try to invent your new algorithm is is really not needed. And the thing is as as you know 2025 if you know that there's libraries that do it that well uh you can ask any AI assistant to write the code for you. So you don't even have to look up that part. I did it old school and copied it from the documentation. But uh the documentation also has another fun problem uh Stigler's diet which is just the the story is a bit fun behind it. The idea was uh this is um person that came up with this problem before linear programming was invented and so he originally solved it with some manual tweaks but not optimally and now it's kind of a standard thing. Uh the setup was how can you uh meet your nutritional needs uh with spending the least amount of money. And so uh he took um what was known at the time and this is uh 1940s. So uh people cared about calories and protein not about fiber.

24:10 And um I guess calories kind of subsumes carbs, but it's not a specific like it's not an extra item here. And a small selection of vitamins and minerals. Um and then he put in all the uh standard food items they could find and what they give you in terms of uh the nutritional value. uh plus a a standard price in terms of well US dollars in the 1940s. So the numbers that will come out will look uh really ridiculously small. But take into account that there's a a bit of inflation going on since then. I guess 40s to now is 80 years. So it should have doubled four times or so. Doubling every 20 years. Yeah, roundabout. Pardon? Which column is the price? Uh good question. So um 1939 prices in cents is the third column. So this one uh okay 10 pounds of wheat flour cost 44 cents. Wow. And you can you can do the same. So you can set up the solver uh and automatically add the constraints without typing them up another time. uh and let this thing solve. So if you do that just because it it makes one point I wanted to come to uh it shows you what you should do. Uh first of all the annual food price is $40. Even if you take that times four or whatever inflation makes of it. That's not much right. Uh now the catch is what should you eat? uh uh a good amount of wheat flour, um beef liver, a bit, cabbage, spinach, and lots of dried navy beans. Yeah. Uh so if you apply linear programming to the real world, it'll ruthlessly maximize the objective and stay within the constraints, but nothing else, right? Uh and it also means you take all the slack out of a system.

26:25 uh which sometimes if you look at uh at train time tables etc sometimes you get the feeling that there was one optimization function or one objective at the expense of some others uh so that that's always to be taken into account the LP only tells you the solution in your in your formal model of what you put in. I guess the other point to say is even if your problem is a tiny bit bigger like in this case has around 100 variables uh it basically solves it instantly. You don't see anything. Okay. What's the general LP problem? Um apart from these concrete examples in general you'll have um uh you'll have a bunch of variables say n variables x1 to xn they're all real numbers uh they may or may not be constrained to be non-positive non- negative um I'll sometimes write this less less and greater sign as just as a as a way to say there's nothing to see here it's not a constraint of any sort it just is an explicit way to write that there's no constraint for XJ. Um and you can have actually three types of of linear constraints. You can have um some coefficients times each of the variables equal to some right hand side that ties the values to some specific or ties uh the values somehow down exactly. Uh you can also have lesser equal or greater equal constraints. That's up for you. What whatever makes it more natural to model the problem. And of course here it's brought in the nice shape that all the variables are on one side and this constant is on the other side. Of course you can is it's equations linear inequalities. You can move things around.

28:27 Um in general if you write down such a problem uh what can happen is one of three things. It can have a finite clearly well- definfined optimal value like our examples. Uh it could also happen that your constraints are actually contradictory and you don't get any feasible point at all. If you're not careful, this could happen. Uh then we call the problem infeasible because there's not even a single point to pick let alone an optimal one. And the other option is it could be unbounded if somehow the constraints don't constrain you uh that much. Uh you could make like in this case for minimization you could make the objective arbitrarily small minus infinity. Um then the problem is called unbounded. So that's one one additional thing to take into account for algorithms. They have to detect which of the three cases happens and only in the first one it makes sense to compute an optimal solution.

29:28 uh as it turns out um all the algorithms for LPS can do that and in polomial worst case time they can tell you which of the cases applies and if it's case A they can spit out the optimal solution or a optimal solution okay uh let's see one one more algorithmic example of what we can use LPS for and this is maybe um the uh oldest uh thing modeled as an LP P um it's the max flow problem in graphs. So if you haven't seen this uh the the problem is given a graph with some uh vertices singled out S&T and the this in general is a directed graph. So it could be whatever arbitrary and think of these as as directed pipes or streets with a certain capacity. Um so the capacities are just telling you how much flow you can send across an edge. I'm not going to write these down. Uh the question is how much flow can you get out of S and into T constrained by how much you can put on each of these edges in between and the fact that you cannot lose objects in the middle or cannot use fluid in the middle. If if there's five units coming in through here, five through here and 10 through here, you should have 20 going out. only in S&T there can be an imbalance. That's that's a max flow problem. Um the goal is to maximize what you can uh route from S to T but that's actually the same as what leaves S. Right? So we call that capital F and then we have some capacity constraint on each edge.

31:14 If you write that as an LP it's a it's a very natural naturally fitting in this shape. We maximize this flow value. The flow value is actually what flows out of S. So you can write that formally as um I guess I should say what the little f is. Um that's a variable for the edges. Each edge has an amount of flow that you can send across it. It's some real some real number. Um it's got to be non- negative because uh we don't allow negative flow in this case and it should be bounded by the capacity of the edge. So f of the edge writing vw for the edge v going from v to w sometimes you would write it like this or you would write it as an ordered pair. I'm using the more uh space economic version here. So the total flow you can write as everything that goes from S to some other vertex minus everything that comes back because you could have edges leading back to S. And the other constraint the non not so trivial one maybe is this flow conservation constraint. You have this for every vertex. That's what I said before. Uh if it's not S or T, what go what goes in has to go out. And so this is what goes in. Everything that comes from some vertex W and goes into V. And that has to be the same as what goes out of V into some W. Summing over all the other vertices. And here these sums I mean um it's a bit of a a shortand uh you should interpret these sums if there is no edge then there's no summand for that vertex. So that's very very well uh is essentially fitting exactly the form of LPS that we had and so uh in undergrad algorithms uh classes usually develop some some tailor made algorithms for the max flow problem. Um, and indeed you can in general solve this a bit faster than general LPS, but you could also take your your network, encode it as a linear program, and let the LP solver do the rest of the work.