Let's take a look at what's needed to implement the simplex algorithm in Java.
so there's a basic idea that's very straightforward and that's the first thing
we have to do is just put everything in an array. and, that's going to be a simple
thing to do. So, we have in this case our input is our recipe for a recipe for beer.
and our profit which is our objective function. and then, all the slack
variables. so we put our matrix A, our M equations, and unknowns in this part of
the array. And then, we put our slack variables next to them and then the
right-hand sides of the equations which is B. and then the initial values of the
objective function, and we'll have to put in the constraints that everything's
positive. and so that's where we start, it's a tableau, it's really a the matrices
and vectors that we have of input to the problem, all put into a single array. And,
and that's again just to reduce the amount of code you have to worry about. so the
idea is that when we run the algorithm, what all we're doing is transforming a few
entries in this array. and when we're done, this is the representation of the
equations that we ended up with, with before. and what they tell us is the
immediately, they tell us the value of the objective function. And not only that,
they tell us what, how many barrels of beer and ale to make cuz we're sitting at
point where we have our A and B A and B in the basis. And the, and the therefore, the
slack variables are zero so it tell us immediately that we better make 28 barrels
of beer and twelve barrels of ale. so that's the idea. we just work with the
elements in this tableau. And then, all we're going to do is write the code to
build the tableau and then to do the pivots. and this is very straightforward
Java code so it's going to be 2-dimensional array, clearly. we have our
number of constraints and our number of variables. so and so we'll write a
constructor that takes the, the constraints. and the, then the array of
five for the constraints and the coefficients for the object ive function
as argument. so it picks out m and n, and so how big an array do we need? m + one
n + n + one. So we just make that array and just fill
it in from our argument. Fill in first the coefficients and then put the initial
values of the slack variables along the diagonal here. Java rays are initialized
to zero so we're going to have to initialize all of the others. and then,
you put the objective function in the right-hand side of the constraint
equations into the tableau simple as that. So, every one of those lines of that code
is completely transparent so that's building the initial, initial values of
the tableau. so now we have to find the column that is going to, we're going to
pivot on. So, we're going to need to pivot on some entry in the array. It's going
have to be in row p and column q in the rule we've given, which is called Bland's
Rule. Remember, Bland is the one who wrote the classic Scientific American article
about beer. So, we use Bland's Rule to just go through and look at the last row,
which is the objective function and look for a positive. So that's all it does, it
just goes through and looks for positive. if it finds positive it returns that
column, and that's what we're going to use. so it's the first one that's
positive. If you line them up positive, it always returns the first one. and if it
can't find one, then it's optimal we can stop. So that's the entering column. we
also have to find the entering row. and to find the entering row, we use the minimum
ratio rule. so we just go through for all of possible rows we just do this
calculation involving the ratio between the current element and the element that
we would pivot on. we only worry about the positive ones and so, it's just a little
check. And again, if there's a tie, you choose the first one and a simple
calculation going through all the entries to figure out which row gives you the
means ratio and then return p. so now, we have p and q where we want to pivot.
that's in, and so we have the values p and q and we just go throu gh and do the
pivot. and then, this is the same calculation that you do for Gaussian
elimination. scale everything, zero out in q, and then and then scale the row And
then, I'm not going to do the details of that calculation. that's what you get when
you solve for one variable, substituting into the other equations. It's the same
calculation as for when you're solving for simultaneous equations. and that's it. the
simplex algorithm is just until you get a -one return from Bland, you just compute
q, you compute p and pivot. And, and keep going and going until you're done. And
then, to look at your maximized value, just look in the corner. not too much code
to implement the bare bones implementation of simplex. It's a fairly straightforward
algorithm. Now, what's remarkable about it is, remember, in multiple dimensions the
number of points in the simplex could be high, could be exponential. But what's
remarkable about this simplex algorithm, and still today, even somewhat mysterious,
but certainly very mysterious for the first several decades that it was used, is
that it seems to find the answer after just a linear number of pivots. this, all
those points out there on the simplex. but when Delta Airlines is scheduling it's
airline pilots or another company is looking for a way to drill or whatever,
Walmart's trying to move its trucks around. these huge problems with millions
of variables it's linear time. It could be exponential time, but it's linear time.
That's why it's been so effective. now, you could use other pivoting rules and
there are certainly been a huge amount of research on trying to figure out exactly
what to do. nobody knows a pivot rule that'll guarantee that the algorithm is
fast, it runs in polynomial time. most of them are known to be exponential in the
worst case, but the real, again, the real-world problems maybe aren't worst
case. and certainly people have looked at all different ways to look at it to try to
understand why this simplex algorithm usually takes polynomial time. this is a,
a recen t paper on the topic. now there are things that can happen during the
execution of the algorithm that we've glossed over. one, one thing is that you
could get stuck in that you could have a new basis. You could make this
substitution but still wind up at the same extreme point. Like if a line, a bunch of
lines intersect at the same extreme point. so that's called stalling. and that would
be that, that's not a good situation that you have to watch out for. and the other
thing is when you have this kind of degeneracy, you could, you could get in a
cycle where you go through different basis always corresponding the same extreme
point. It doesn't seem to occur in practice in the way that we implement it
and the way that anyone would implement it. Just choosing the first one, that's
Bland's rule is going to guarantee that at least you, you don't get caught in an
infinite loop which would be bad. That doesn't seem to happen anyway. But it's a
problem to think about. there's a number of other things that have to be thought
about in order to actually try to use this to schedule airlines or whatever. so you,
you, you, you certainly have to be careful to avoid stalling. one thing is that there
tend to be, most of the equations tend to involved relatively few variables. and
people who have experience with calculating these systems of equations
know that in some situations you can find yourself filled up with lots of non-zero
values. so you want to take a, a rule that meant implements of things with sparse
matrix with, so your amount of space you take is proportional to the number of
non-zero entries. so, and we, we looked a couple of times at some data structures of
that sort, and that's certainly a consideration in simplex implementations.
the other thing that we haven't talked about much in this course, but whenever
you're working with floating point approximations of real numbers, and you're
making a lot of calculations you have to make sure that you have control over the
errors in the calculations. and scientific compu tation is certainly concerned with
keeping control of that situation and something that we haven't talked about
much in this course. and the other thing is that actually it could be the case that
your constraints are unfeasible, there's no way to satisfy them. and it's a bad
idea to run simplex for unfeasible situation cuz it won't ever get to the
optimum. So typically, what we have to do in practice is run a different simplex
algorithm on con transformed version of the problem. And there's theory, really
interesting theory behind that all. and it's, you use the same code to figure out
in-feasibility, but something has to be done. and the other possibility is there
aren't enough constraints. so that you missed with one of those half-planes. You
missed somewhere, and then it gets infinite. and that's also a situation that
you want to avoid. And with the code that we gave, that would be the case where you
use Bland's Rule to find a column, and. You're looking for a row and there's no
row, so you have to check for that as well. and each one of these things is
complicate, complicated enough that in this case we'd probably say the best
practices. don't, don't go in and try to implement a simplex unless you're prepared
to devote a really substantial amount of time to it. and there's really, no need to
do that nowadays because basic implementations of simplex are readily
available in many different programming environments. and routinely, nowadays,
people solve LPs with millions of variables airline and they're so easy to
reduce practical problems to an AP, and LP. Just throw in another constraint. Any
constraints that you might have a certain pilot doesn't want to be scheduled early
in the day, or late in the day, or union rules, or whatever. You just put all these
things in as constraints without worrying that much about it. And then, add more
variables, whatever you need to do. and then send it to an industrial strength
solver and people nowadays solve LPs with huge numbers of variables. And not only
are there solv ers. Nowadays, there's modeling languages that
make it even easier to write down the LP. and so, there's plenty of resources
available to make use of the simplex algorithm nowadays. and it's important.
This is a really, you know, important quote from just a few, few years ago
that's worth reviewing. so, they have this is so widely used. They have benchmarks on
how well linear programming implementations do. So, even in 1988, it's
not all that far back, they have a benchmark that would have taken 82 years
to solve and even that's just a guess. and using the best linear programming
algorithms of the day would take 82 years. Just fifteen years later, you could solve
the same problem in one minute, that's a factor of 43 million. of this, factor of
1000 was due to increased processor speed, so fifteen years we have computers that
are 1000 times faster but 43,000 is due to algorithm improvements. And there has been
more even since then. So, the importance of knowing good algorithms and working
with good algorithms is unquestioned, in this case. and, of course, this algorithm
is still being heavily, heavily studied. so, it's starting with Dantzig's simplex
algorithm and other basic knowledge about the algorithm and about linear programming
that was applied in practice in nineteen 48.
The, the basic idea of linear programming actually precedes Danlig, Dantzig, and
actually wound up with a Nobel Prize. but what's interesting is rhere was, that
algorithm was so good, there was actually not much development on it for about three
decades. But then, an amazing surprising result Khachiyan proved that you could
solve linear programming problems in polynomial time. that was quite a quite a
shock at the time and we'll talk more about that in the last lecture of the
course. And then since then, knowing that there are algorithms that potentially
could beat simplex, people have actually developed algorithms that do beat simplex.
And so, there's still a great deal of research going on, on the simplex on
implementations of linear programmi ng solvers. So that's quick outline of what
it means to implement and solve linear programs.