15. Linear Programming: LP, reductions, Simplex

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-0...
Instructor: Srinivas Devadas
In this lecture, Professor Devadas introduces linear programming.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@gustavo5320]

One of the best explanations about the fundamentals of Simplex. Thank you, Professor!

[@Ludiusvox]

Thank you so much for this lecture, because I have taken Analysis of Algorithms and supposedly it was ABET accredited and I didn't miss any lectures but somehow this lecture wasn't included in my class. In my theory you guys are all working off of the public education budget from the DoE so thank you for filling in where the other teachers skip subjects in school

[@minhazjisan3074]

simplex method/big m method are fundamental part of operations research course

[@karansvnit]

Simplex algo: 58:38

[@juliotufino4246]

Not all heroes wear capes

[@biswajeetsethi7689]

At 16 min.. what is that / 111 ?? I dnt get it

[@polymathmaktaba9092]

@@biswajeetsethi7689 it's a fraction.

[@abramwestrick9790]

Thanks

[@abhilashc2965]

Blessyou

[@henryzhu7309]

One of the interesting class for the whole series. No boring proof and analysis

[@SubhamKumar-eg1pw]

Simplex algorithm at 59:53

[@lilyshawn5454]

What a great lecture! I love that the professor handed out Frisbee to his students.

[@ariellubonja7856]

39:45 - Expressing Max-Flow as LP

[@caio-jl6qw]

Golden lecture! On top of that, a charismatic professor :)

[@KofiKrules]

This dude is rolling of a bean rn

[@KofiKrules]

never mind, I had my speed on 1.25

[@gatoquantico3925]

How did he get the constants for getting the certificate of optimality?

[@XiaosChannel]

oh dear, never thought I'd learn how politics work here.

[@andriwmunoz9006]

Xiao'sChannel amazing, isn't it?

[@user-hs7qg5tt8t]

unbelievable! how they decide what to say to let people vote to them

[@bhushan8362]

@1:17:23 equation for slack variable x5 is wrongly written (last term should be x6 /2 instead of x1 /2)

[@junzhai1715]

correct

[@kallishanti]

prof was high af

[@AvanagantiAkshathreddy]

He proved that x1+x2+x3+x4 has 3100000/111 as a possible lower bound, but where did he prove that it is the minimum possible lower bound in the certificate of optimality??

[@ubershh]

33:11 Converting LP problem to standart form

[@PedroFPardo]

I couldn't get a better solution than (x1, x2, x3) = (8, 4, 0) >> 28 How can Professor Devadas get to 30?

[@victornyborg6569]

I get the same answer as you using a different method.

[@lounesbenali4889]

I think that z is equal to 27 + x2/4 - x3/2 -3x6/4 instead of 27 + x2/4 +x3/2 -3x6/4 But despite that I still find like you (8, 4, 0) >> 28

[@jwarha7797]

Great lecture. That board though...I wish I could clean it myself.

[@user-hs7qg5tt8t]

hahha +1

[@lilyshawn5454]

lol

[@binwangcu]

I can make an unapproved claim that the optimality is smaller, but how come using cost function itself certifies the optimality?

[@SakosTechSpot]

how relevant to current events.

[@dariusduesentrieb]

yeah

[@nyahhbinghi]

LP is super relevant - since many systems are linear, but LP is also very useful as part of the algorithm for IP (integer programming) which is used for scheduling algorithms

[@gulnursonmez9539]

For the limitation equations, dollar spent per issue times number of people gained or lost per issue gives dollars, but the right hand side constant shows number of people. there's a type mismach. I got lost. I mean 50000 $, 100000 $ or 25000$ could be, but they are not dollars, they are number of people, 50000 people, 100000 people, 25000 people, but the x1, x2, x3, x4 are dollars/issue.

[@junzhai1715]

the coefficient: -2,5,3,etc. are votes/dollar. So -2*X1 means votes/dollar*dollars/issue=votes/issue. Therefore, the constraint is how many total votes for each issue. Here it also assumes each people has one vote. People=Vote

[@hsujerry7231]

How can we prove the time complexity of the simplex algorithm? The professor seems to omit the proof

[@lounesbenali4889]

at 1:16:45 z = 27 + x2/4 - x3/2 -3x6/4 a small typo ! But Thank you !

[@guillemf2486]

28:34 Did he just throw a frisbee? Why are his classes so much fun?

[@harrywang6792]

I guess you are new here lol. Yeah, he throws a frisbee to the students who answers questions

[@ZhanCaitao]

Good lecture.

[@mustafa7891]

What did the professor throw, when the student answered correctly? Do anyone know?

[@OakCMC]

It's a frisbee.

[@KundoKun]

I learned that people gift frisbees to politicians based on the message they want to hear.

[@xavierdsouza8885]

1:04:53 simplex derive

[@englishmotherfucker1058]

1:20 the chalk looks like the upper left quarter of a face looking towards the exit

[@rahulkasar124]

Can someone timestamp when he starts talking about Simplex please?

[@_ahmedkira]

can you add timestamp please

[@SarveshBhatnagar1214]

I enjoy learning algorithms here... nice work...

[@biswajeetsethi7689]

At 16 min.. what is that / 111 ?? I dnt get it

[@hernanodi2877]

@@biswajeetsethi7689 I don't understand either

[@rongrongmiao4638]

When introducing general form of LP, shouldn't the objective function be x*c transpose? Since c is also a vector which means that it's a column matrix...

[@mateusrochacruz7966]

Yes! But C is generally considered as a matrix os 1 line and n columns, avoiding the transpose.

[@wademarshall2364]

You can, but what he wrote is valid because he wrote the coefficients as a column vector and multiplied them with the dot product. Which is equivalent to matrix multiplication with the transpose

[@yashotkarshmanitripathi3694]

why we are equating money spent on each issue to the population of that demography ?

[@Aiwon]

That also bothered me. I think that X1 through X4 are simply dollar and the coefficients associated are in Vote/Dollar. For exemple Urban/Gun control coefficient is +8 meaning that the more money you spend the more vote you get until you have a majority. 8*X1 = the vote you get by spending X1 DOLLARS in urban ad campaign on gun control.

[@junzhai1715]

the coefficient: -2,5,3,etc. are votes/dollar. So -2*X1 means votes/dollar*dollars/issue=votes/issue. Therefore, the constraint is how many total votes for each issue. Here it also assumes each people has one vote. People=Vote

[@Catloverassam]

Is there restriction on the number of decision variables and constraints used in an LPP?

[@TommasoFerracina]

no

[@jeongminyoun5388]

Can anybody tell me how did 140/222 come out?

[@ttobg]

I don't know also

[@shubhamide]

sir multiplied some coefficients to all three constraints equations....and then added all three equations

[@mustafa7891]

Do you till want to know?

[@rasraster]

Lucky for him the optimal solution had x3 = 0, because otherwise x1 + x2 + x3 + x4 would be strictly greater than 3100000/111!

[@Giesela0815]

28:08 Haha that was funny!

[@fallug2501]

I didn´t undestand what happened! Can you explain please? Thanks. :)

[@Giesela0815]

He said, she has her head down. Then proceeds to throw the Frisbee at the student.

[@cyanide4u539]

Is this person Indian??

[@batman76781]

Yes

[@subhamraj2500]

Yup

[@ramizhossain9082]

Explain an easy way .

[@brandongomes7321]

This is great

[@ShaunYCheng]

My #1 take away from this lecture: How does politics work? "You buy elections!"

[@AI7KTD]

The assumption at 4:49 would imply that you could decide to spend different amounts of money per issue per region, instead of having a global budget per issue. Now that's how real politics work!

[@nishchayshah6356]

What are the space and time complexity of the simplex algo? how to find that?

[@Marshal4o]

It's exponential in time, you can find it in the notes here: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec15.pdf

[@aaditshah4689]

It should be noted that the time complexity of the simplex algorithm is only exponential in the worst case. For practical problems, the simplex algorithm is quite efficient running in cubic time.

[@jacquestaschereau7645]

mention @2:10 and 1:02:10

[@IceTurf]

how come Xi --> Xi' - Xi''?

[@junzhai1715]

because any real number Xi can be represented as the difference of two non-negative numbers Xi' and Xi''.

[@IceTurf]

@@junzhai1715 Xi' usually implies the first derivative on Xi.... and Xi'' usually implies the second derivative of Xi....?

[@junzhai1715]

@@IceTurf oh no. sry. They are just two different variables. You can treat them as Yi and Zi if you want. Nothing to do with derivative.

[@vinayakkambli7278]

Sy bsc mumbai university lecture

[@payndha6228]

Am I the only 8th grader that watches this kind of stuff cuz its interesting?

[@harshtiwari9315]

Just use a Neural Network!

[@SacknoobGaming]

this is MIT yet I'm doing this in 10th grade fml

[@nayankumarbarwa4317]

lol and i doing it now hahah in second year engineering Even I was in 10th 5 years back, didnt even cared to watch anything other than cartoons