This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.
Linear Programming Reductions
Loading...
來自 Princeton University 的課程
Algorithms, Part II
457 個評分
從本節課中
Linear Programming (optional)
The quintessential problem-solving model is known as linear programming, and the simplex method for solving it is one of the most widely used algorithms. In this lecture, we given an overview of this central topic in operations research and describe its relationship to algorithms that we have considered.
與講師見面
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Kevin WayneSenior Lecturer
Computer Science
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.
