So, well finish off by taking a brief look at reductions to linear programming problems. So, first, first of all, is the idea of re, reducing to the standard form. when we first proposed the problem, we did it in terms of inequalities. And there's all sorts of different versions that you might imagine are more convenient for different types of problems with fewer restrictions. so as we've talked about there's easy ways to deal with each of them the, the standard form is not that different than the types of things people might want to do. So, one thing, if maybe somebody wants to minimize. So, if somebody wants to minimize, you replace that minimization with the standard form says maximize. So, you just negate everything so that's equivalent. if you have inequalities, add a slack variable. subtract the slack variable, it's going to be positive. That converts a greater than or equal to constraint to an equality just by adding a variable. and if you have variables that are supposed to unrestricted, just replace it as the difference between two variables that both have to be positive. so, so those are just examples of taking nonstandard form and reducing it to a problem that's in the standard form. so for any particular problem that we might want to come up, then we can use the less restricted nonstandard knowing, knowing that, you know, it's easy to for the LP solver to do the reduction from our nonstandard form to the standard form. And certainly that's something that the solver can do for us. So actually, I didn't mention at the beginning is why is it called linear programming? We're, we're used to programming that's, say, write Java code to solve a problem. but you have to remember, this is 1947 that's actually well before computers came into use and people were write, were writing programs to do this stuff. And actually, for smaller variables, you can basically solve it by hand. So, what they meant by programming was more, there was another term, it's called planning. And, and so that was more take your probl 'em and put it into a form that we can solve. Nowadays, we call that reduction. redu, collect reduction to the linear programming problem. So, it's the process of formulating your problem at the linear programming problem. and so, and again, it's reduction solution to the linear program gives the solution to your problem. so what do you have to do? You have to identify what are the variables, you have to define the constraints, the inequalities and equations, and you have to identify and define an objective function. That's all you have to do, though. once you have those things, and pretty much you have a linear programming problem. and you do have to convert to the standard form. But usually, you can count on the software to go ahead and do that. so, let's look at some examples that I have said, reduce to linear programming problems or can be modeled as linear programming problems. and, you know, we'll just use the modern term of reduction. So, for example, Maxflow problem. so this is the Maxflow problem that we consider. and it's input is a weighted digraph. and there's a source vertex s in a sync vertex t. and the, the weights indicate capacity. and we're, we're supposed to find out is what's the maximum flow from s to t. It doesn't seem to be that much related to linear programming. But, if you just look at the idea, well what are the variables going to be? the that's going to be and what are the constraints going to be and what are the variable flow, the variables are the amount of flow along each edge. And the constraints is going to be a positive flow and it's constrained by the capacity. So, this is just a mathematical formulation of the problem. from zero to one, you have to flow this between zero and one. from zero to two you have to flow through zero and three, like that. That is what I am saying, that's what the capacity constraints are. And the other thing about the flow is that we said, the inflow has to equal the outflow at every vertex. so we have a variable corresponding to the flow in each edge and then we can just express the flow conservation constraints, the amount that comes into vertex one, which is X01, has to equal the amount that comes out which is X13 + fourteen. And you have one of those constraints for each one of the vertices. and then, what's the objective function? Well, you want to maximize the amount of flow that goes into number five which is X35 + X45. That's an LP formulation of the Maxflow problem. It's really and it illustrates how really easy it is to represent a maximization problem as an LP problem. And again, you have an LP solver you just put in those, those constraints. so, the variables are positive, it's just all inequalities and a couple of equations. then the software converts it to the standard form and gives you the solution. Now, it might take longer than our specialized algorithm that we looked at based on searching in the graph and so forth which is a very wonderful algorithm and very useful and lots of applications. but the advantage of the LP formulation is that if the problem gets more complicated, say, we also want to insist may be there's cost assigned with each flow. so you want to maximize it, but you also want to keep the cost under control. or any kind of specialized constraints that might come up. In the LP formulation, you just add those constraints you know, in other formulation it might completely ruin our approach to the problem. That's the advantage of LP and why it's so widely used. here's another example, this doesn't seem at all to have that much to do with linear programming but it's the bi-part, maximum cardinality bipartite matching problem that we considered, and that's matching students to jobs. and so this is for we've got a bipartite graph one set of nodes corresponds to students, the other set of nodes corresponds to jobs, we have edges corresponding to job offers. And if we want to know the maximum set of edges connecting one to another the matches a student to a job. and we did that one by reducing it to Maxflow, actually. but also you can just specify it as a an LP, formulation of an LP problem. So, it's kind of that's going to be, everything has got to be zero and it's just going to maximize this is all the possible matchings. and then, the constraints are there has to be at most one job per person. So, if A has three edges, just say X0 plus X0 plus the two, less than or equal to one and do that for each person. And then, at most one person per job, just do it that way. Now, these this is not a trivial reduction. There was some math, quite a bit of math done early on, including Von Neumann was involved. So, if you have a polyhedron like this that where the right-hand sides of the inequalities are all one. all the extreme points of this polyhedron have integer coordinates that are either zero or one so we need that theorem. But and it's not always so lucky, but in this case, you can, you can do it. and you can just use this linear programming linear program to solve the matching problem. Again, no specialized algorithm, I just throw in your constraints and you have the solution. use your LP solver. so that's just two examples. and there's many, many more examples. And again, as I said, you can take a problem like one that we solved and just add more things. So, I want the shortest path that doesn't go through a certain node or that only has the certain number of nodes on it, or whatever else. Any other kind of constraints that you might think of you can just throw them in if you've got an optimization problem, one thing you can do is definitely you know, use an algorithm that you learned and go to the literature and try to find the solution. And that is certainly very effective for many of the fundamental problems that we've considered. but if things start to get complicated, it's really a good idea to think about using linear programming cuz it's often easy to model your problem as a linear program. And you can solve it with a commercial solver or available, if it's a small one, a readily available solver. It might take a little longer than your sp ecialized solution if you had one, but you might not care and you might not have one. And the idea is, it really is a good idea to learn to use an LP solver. the really the takeaway from this is there's a lot of problems that reduce right to linear programming and we've got a fast way to solve it. so that's a powerful problem solving model with broad scope. it's we can solve it. And we can reduce a lot of important practical problems to it and that's why it's important. So, this leads us to a really profound question that's called the P and P question. and that'll tell us and we'll talk about this in detail in, in the next lecture that there's condition that is very fundamental to the efficiency of computation that'll tell us that people don't think that there is a universal problem-solving model. for the time being, however, and for the last 50 years, the closest thing that we have to a universal problem-solving model is linear programming.