0:00

So, discrete optimization, again, linear programming part two.

Okay, so this is getting really exciting. Okay, so what we saw last time was the

geometric view and linear programming and what we going to do now is do the

connection between this geometric view and the algebraic view.

Okay, so we going to link the two and this is where this thing gets really

nice. Okay, so remember what we saw last time,

is that we could solve this problem from a, from a geometry standpoint by simply

looking at all the vertices, and taking the one which is the best value for the

objective function, okay? Of course you know it's like, oh, how do

I get these vertices? You know it's like, hey it's crazy right,

writing an algorithm to get these vertices.

doesn't seem so simple. Okay.

We can do that by hand. But how do we do that, you know, on a

computer? And that's the key point here.

Okay? So the simplex algorithm is essentially

a, a, an intelligent way of actually exploring these vertices.

And as I told you, you know, this is where the connection between the geometry

and the algebraic view, the, is, is really interesting.

Okay. So once again, I told you that, you know,

this algorithm was invented by Charles Dantzig.

And one of the things you have to understand is that this, this algorithm

is actually still, after, you know, like, 60, 65 years, actually, wow, this is 65

years. After 65 years it's still a complete

enigma, right. It works incredibly well in practice,

always solving this problem really fast in general.

But it does an exponential worse case so in the worst case it's terrible right.

But this worst case doesn't seem to happen in almost never okay.

So you have to you can construct an example where it can happen but it don't

seem to happen in practice. So from a theoretical standpoint, nobody

really understands why this is the case. And they are really some very nice

theoretical issue, which are very simply state, that nobody knows the answer to.

Okay? So very interesting algorithm.

And so what I'm going to do today is to actually Try to present this thing in an

intuitive way, what the simplex algorithm do.

And so this is, this is the wa-, this is the way I would, you know, I could

characterize this algorithm. Okay.

It's very simple, right? So what you want to do is to be on top of

the world. Okay.

So that's the goal, okay? The goal is to go, to be on top of the

world. Now, I'm going to give you five facts,

okay, that will allow you to go, to be on top of the world, okay?

The first fact that I'm going to give you is that the top of the world is the top

of a mountain, okay? Basic fact, right?

No, the string in fact, is the most interesting one, okay?

So the top of the mountain is a beautiful, fantastic spot, okay?

We are going to be talking about beautiful, fantastic spot all the time.

And I call this guy BFS, okay? So, beautiful, fantastic spot, okay?

So you have to to know, okay, that the top of the world is at the top of a

mountain, and the top of a mountain is a beautiful fantastic spot.

Okay? Now, the third thing that I'm going to

tell you, okay, the third fact, is that you can move from a beautiful fantastic

point to a neighboring beautiful fantastic spot.

That's easy to do. Okay, you are at the beautiful fantastic

point. You see another one.

You can move there. Okay.

So, and then the fourth fact is that, and this is important, when you are at the

top of the world, you know you are at the top of the world.

Okay, fact four, okay. And then the last fact is that if you

aren't a Beautiful Fantastic Spot, there will always be an opportunity to move to

a higher Beautiful Fantastic Spot. Okay?

So if you understand these five points, okay, so you understand linear

programming. Okay?

So this is as simple as that. Okay?

You know that the top of the world is a top of a mountain.

You know that the top of a mountain is a Beautiful Fantastic Spot.

That you can move from Beautiful Fantastic Spot to another neighboring

Beautiful Fantastic Point. When you are on top of the world, you

know it, okay. And then, every time you are at a

beautiful, fantastic spot, there is a way for you to go to a more, to a higher, you

know, beautiful, fantastic spot. Now, so this is too simple, right, and,

and we have to make it complicated. And that's what we're going to, that's

what I'm going to do, okay. I'm going to do on the next slide, okay.

I'm going to take these facts and make them a little bit more complicated, okay.

Because otherwise, people will say, what you do in science is too easy.

I mean, we're not the only one to do that right?

So you know, a doctor would talk abut the distant part of your fibula.

What is that, right? So can't they say, this is the part of

your fibula next to your ankle? No.

They would say, beautifully, you know the distant part of your fibula is the

problem. Right?

Anyway. So, lawyers sound the same right?

So when you buy a hose in the US they would say, they would write things like

expected performance. And you say, wow, what is this expected

performance? That just means you have to buy the host,

okay? But, you know, so we going to do the

same. We're going to take this very simple

algorithm and make it look complicated, such that people believe we are really

clever. Okay?

So this is what we're going to do, okay? So, we, we, instead of saying we want to

be one top of the world, we want to solve a linear program.

Okay? Fact number one, you know, what I told

you is that the top of the world is at the top of the mountain.

That's basically telling you that the optimal solution is located to the

vertex. So when you think of a vertex, think the

top of a mountain. Right?

Now, a vertex, okay, is actually a beautiful, fantastic spot but we can't

talk about beautiful, fantastic spot so we going to say it's a basic feasible

solution. Okay, but let's say BFS, you know, you

can think BFS, basic feasible solution or beautiful fantastic spot.

Okay, and then the three other facts are going to be essentially the same, because

we are talking about BFSs, right? So we can move from a BFS to another one.

Beautiful fantastic boat to a beautiful fantastic boat, a basic feasible solution

to another basic feasible solution. You know that you can detect if a

beautiful fantastic spot is at the top of the world, okay.

you, you can detect it so basic feasible solution is optimal.

And then you can move from any BFS to a not a BFS which has a better cost.

Okay? Well, smaller cost if you minimize, you

know, higher cost if you maximize. Okay.

So this is once again, a little bit more complicated now.

We are talking about this basic feasible solution, that we don't really know what

they are. But this is the same thing as what I've

shown you on the previous slide, okay? But this is the simplex algorithm.

So, what I'm going to do in the lecture is going to, through these various facts

and telling, and explaining how they work.

Okay? So, we know what a linear program is,

right? So, minimizing this linear function and

then these constraints. Okay?

And all the variables have to be graded on 0.

We'll come back to that, this is an important part, okay?

So, so let's start, let's back up a little bit.

Okay, I'm back, backing up, okay, right? And so, what we are looking at here,

first. We have a system of linear equation and

we want to solve it. How do we do that?

How do we do that, okay. Go back to high school.

That's what we did, right? And so essentially what you do is you

perform you know, Gaussian elimination to actually solve a system of linear

equations like that, right? So you basically express some of the

variables in terms of the other ones, okay.

And so you basically isolate a bunch of variables, x one to x n and you express

them in terms of the other variables. And so this is basically what we call a

basic solution. The variable on the left sides are going

to be called the basic variables. Sometimes we tell them they are the basic

Right? So, but they are the basic variable.

Okay? And we going to love these guys.

Okay? You'll see why.

And the, and the other variables, I call the non basic variables.

Okay? They are the guys that we don't really

care about. Okay?

And then of course you have the bs which are the values that we're going to give

to the basic variables. Okay?

So, this is a basic solution. Why?

Because essentially we're going to take the basic variables that you see there,

we're going to give them as values, the b's.

Okay? And then we're going to take the basic

variable, the nonbasic variables and we're going to give them all zeros, okay?

And if we do that obviously these equations are going to be satisfied,

right? I'm basically saying xi is equal to b, x1

is equal to b1, you know, and xm is equal to bm and all these guys are zeros so

these equations are obviously satisfied. Okay?

So this is a basic solution. Okay?

So I'm basically taking all the xi giving them the bi.

I'm taking out all the non-basic variables, assigning them to zero.

So in a sense, think about this. In this is some of equation, there are

bunch of variables that are all zeros and that happens all the time in linear

programming, right? So you will have a massive amount of

variables typically assigned to zero and then these beautiful basic variables are

going to be assigned the bi's that you see there, okay?

So that's a basic solution, okay? We'll talk about basic solution.

Now remember a beautiful fantastic post and this F in there.

Right. So this is feasible or fantastic okay.

So you going to be fantastic or feasible when you satisfy these constraints, okay.

So you have to make sure that all the variables.

All the variables here have to be greater than 0 okay.

And so how do you that? Well, you know for the non-basic

variables it's easy, right? So all these guys are already zero.

But you want to make sure that these guys are assigned non-negative values, okay?

And so that means testing when you actually isolate the X1 to XN, that these

guys are actually non-negative, okay? And if they are non-negative, what you

have is a beautiful fantastic spot. You have a basic feasible solution.

Okay? So that's what you have here.

Okay? So a basic feasible solution is a

solution where you isolate some of the variables, x 1 to x m.

It can be any one of these variables, right?

So they are called the basic variables. They are assigned these bs that, you

know, that you have, and all of the non-basic variables which are there are

assigned to 0. Okay, basic feasible solution, okay.

You're going to say, why this, this guy actually obsessed with this and you'll

see why in a moment, okay. So, how do we find a beautiful, fantastic

spot? We select environments, okay.

So there will be the basic feasible, the basic variables.

We re express them in terms of the other ones, okay.

Not in terms of each other, right. Only in terms of the non basic variables,

okay. We can do that easily by performing

Gaussian elimination, okay. And if all the non, if all the b's are

nonnegative, we know that we have a basic feasible solution.

Okay. So, you're going to tell me yeah, yeah,

yeah, yeah, yeah. But you are dealing with equations now.

But in my simplex algorithm, I mean inequalities, right?

So what are we going to do? Well, you know there is a very simple

thing that we can do. Okay?

If you have a set of inequalities like this, okay?

What you can do is always you can add some new variable okay?

From S1 to SM, okay? And transform this inequalities into,

into equations. okay?

So this adds one to the left and it has to be greater or equal to zero, so you

add them and there is one for everyone on of the contraints.

They are all forced to be greater than zero and we call these guys the slack

variables. And the intuition here is very simple,

look at the expression you have there. They will have a value when you assign

the basic variables, and then there will be the value of the b's.

Okay. So typically they have to be smaller or

equal to that. So they may, so either they are equal, in

which case the slack variable is going to be zero, otherwise the slack variable is

going to be the difference between the b and then the, you know the left hand

side. Okay.

So essentially they are making, they are transforming this inequality, okay.

They are transforming these inequalities into equations by picking up the slack,

and really having a variable capturing that slack, okay?

So, very simple, right? So if you have a long, if you have a

linear program with inequalities, you can transform these inequalities to

equations, and that's what we want to do, when we are actually implementing this

method on a computer. Right?

Okay? So, once again, to summarize, you start

with your linear programs, you take all these inequalities, okay?

You have slack variables and you have equations, and now you select m

variables, so these are going to be the basic variables.

You re-express them in terms of the non-basic variables, performing Gaussian

elimination and then if all the b's are non-negative you have a basic feasible

solution, you have a beautiful fantastic spot, okay?

So, so, now, this is the key point. Okay.

This is the most important fact that you need to know.

A vertex, in the geometrical sense that I've shown you in the last lecture, is

actually a beautiful, fantastic spot. It's a basic feasible solution.

Okay. So in a sense now, we have a beautiful

algorithm. I'm, I'm giving you an algorithm, right,

that you can actually code in a computer. Right?

So the naive algorithm that we have now is that we just want to look at all the

vertices. Okay.

But the vertices are basically a basic feasible solution.

So you can just enumerate all these basic feasible solution, and then take the one

which is best. So you generate all the basic feasible

solution. How do you do that?

Well that's just what I explained to you, right?

You isolate end variables. You express them in terms of the

non-basic variables, okay? And then you perform Gaussian elimination

and then you can test if this is feasible.

If it is feasible, you have a basic feasible solution, okay?

So I have noticed, you know, naive algorithm which you can implement on a

computer which will generate all these basic feasible solutions and for everyone

on of them you can computer a value of the objective function.

You essnetially plug the values that are in that solution Okay?

And then you select the one which has the best cost.

Now how many of these? Well, that's the issue, right?

So they will be a very large number of them, right?

It's like picking up m variables inside the m, and you want to explore all these

combinations. Okay?

So there are many of them. Okay?

And so, in practice, the naive algorithm that I'm showing you here Is not going to

work you know, nicely from a computational standpoint, from a

performance standpoint. But we'll see how to improve it, you

know, in the next lecture. Okay?

So, basically summarizing what we have seen.

Okay? So, what you want to do.

Okay? Is to be on top of the world.

Is basically a vertex. Okay?

And what you can do To get to. And a vertex is a basic feasible

solution. And getting a basic feasible solution is

actually pretty easy. It basically consists in isolated end

variables, okay, expressing them in terms of the other one, and testing the value

that you assigned to them is actually not negative.

Okay? We'll see a more clever way of actually

exploring all these vertices, basic feasible solutions You know next time.

Thank you very much.