What is Linear Programming (LP)? (in 2 minutes)

Overview of Linear Programming in 2 minutes.

----------------------
Additional Information on the distinction between "Polynomial" vs "Strongly Polynomial" algorithms:
An algorithm for solving LPs of the form
max c^t x s.t. Ax \le b
runs in polynomial time if its running time can be bounded by a polynomial D^r, where "r" is some integer, and D is the bit-size of the data of the problem, or in other words, D is the amount of memory that it takes to store the matrix A and the vectors b and c. On the other hand, an algorithm runs in strongly polynomial time if its running time can be bounded by a polynomial n^r m^s, where "r" and "s" are integers, "n" is the number of variables and "m" is the number of constraints.

The distinction is subtle, but is an important one. Essentially, a polynomial time algorithm is allowed to take more time as the size of the coefficients of A grows (while keeping the dimensions of A constant), but a strongly polynomial time algorithm is not.

(I glossed over some details here. For example in the definition of strong polynomial time algorithms, we assume that the basic arithmetic operations take a constant time no matter the size of the operands.)

----------------------
Typos:
- "Schedueling" should be "Scheduling"

--------------

Timestamps:
- 0:00 Motivating Example
- 0:39 Definition
- 1:07 Applications
- 1:42 Code
- 2:00 Open Problems

---------------
Credit:

This video would not have been possible without the help of Gökçe Dayanıklı.

[prolixescalation]

Ahhh, so nice to see this video while I'm taking classes about methods of optimization

[tanishqawasthi]

It's so great to see someone taking out time and doing efforts to make us understand optimization better in visualisation....kudos to you....
Please make more videos on optimization including topic like duality, Non-Linear optimization and constraint Non linear optimization and on Neural network as well...

[BrianAmedee]

So this is a code that optimises stuff based on constraints? Nice. Straight to the point, well done

[mayureshjoshi]

Wow simply awesome, visuals were awsome and so are you!!!

[VS-wqws]

Super informative video with visualisations
Thank You from india

[aleocho]

Here from Ahmad Bazzi 's NVIDIA video. Awesome stuff mate.

[PeekPost]

Video visually showing comparison between simplex on kkt and IP on kkt (along with their performance) would be great!🤠

[philippvetter]

I love these videos. These are amazing explanations and really helpful for people that are new to optimization!

[hyukppen]

Is the semidefinite programming different from the linear programming? It seems similar but I don't understand the difference.

[AKfire]

Beautiful animation.. Please make a making video tutorial for the part that you did in Blender.

[vTutorLive]

Great work! It's been a few years since I've done LP, but it would have been nice to have a visual as sharp as this when I first learned it. I actually wasn't familiar with "strongly" polynomial time (as opposed to just polynomial time). I'm sure these videos are made with brevity in mind, but consider putting a quick, informal definition off to the side? Unless I just missed it

[hbasu]

Thanks for explaining it so well. I had a question: why in LP the optimal solution is found at one of the vertices of the polyhedron ( feasible set) ?

[fodgopp]

Could you add english caption so that it make easier for foreigner

[michael-nef]

lol, solving the second open question is equivalent to solving the P=NP conjecture.

[bigbuckey]

Great production value, horrendous music.

[Piipolinoo]

Whats up with that horrible music in the background? the fuck