Hacker News Reader

I nailed them on their description that the simplex algorithm was like Gaussian elimination for systems of linear inequalities.

I found your additional input on the topic helpful, but I'm having trouble picking out more helpful insights about LP from all the other unrelated discussion.

View on HN

The core of the simplex algorithm, and the key to its considerable power, is a cute application of elementary row operations selected to improve the value of the objective function. That's the 'algebraic' part. There is a cute, and significant, geometric part: The collection of feasible solutions is an intersection of finitely many closed half spaces and, thus, is closed and convex. The set has finitely many extreme points. At each iteration, the simplex algorithm starts at an extreme point. The elementary row operation causes the algorithm to try to move along an edge that improves the value of the objective function. In case of 'degeneracy', the algorithm can execute algebraically but stand still geometrically, but there are techniques to do the right things in this case.

So, the core really isn't Gaussian elimination for systems of linear inequalities.

For more, LP and the simplex algorithm are surprisingly powerful: Part of the reason is, for a huge range of optimization problems, taking a local linear approximation and then attacking that with simplex is often the best technique known. There are also surprising connections with combinatorial optimization and some classic NP-complete problems. What LP and simplex do on networks is also surprising and powerful; e.g., there simplex takes on a special form based on spanning trees.

Reply on news.ycombinator.com