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.