0:03

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.

Â