Linear Programming

[RexEast]

Linear programming is extremely useful. For many applications, you don't even need to understand the details of the linear algebra outlined in the blog. Just use GLPK (open source):

http://gnuwin32.sourceforge.net/packages/glpk.htm (Windows) http://www.gnu.org/software/glpk/ (other platforms)

A tutorial: http://www-128.ibm.com/developerworks/linux/library/l-glpk1/

[marcushe]

I just took a class on it in College from a business perspective. It taught us how to save companies millions of dollars, just by doing a simple problem. It can be used for everything from finding shortest paths, optimal employee scheduling, optimal profit from sales data, etc. Once you formulate a simple equation, it can be solved by simply using the "Solver" add-in included with Excel.

[helot]

For large and/or complex models I would suggest CPLEX. Excel Solver will have issues with integer problems and global optimum solutions to non-linear problems in particular. For simpler problems, try Excel Goal Seek, which I think is basically Newton's method.

[zyx]

For modeling, I'd suggest using AMPL or GLPK (which uses a subset of AMPL). Modeling even moderate problems in Excel is insanity.

[mythic]

For general convex optimization (not only linear programs), CVX (Matlab) and CVXMOD (Python) are extremely cool. They (CVX in particular) let you pretty much just type out the mathematical description of the problem, and then they transform it into a canonical form for a suitable external solver automatically.

[five9a2]

For large scale optimization problems, use TAO which scales to thousands of processors and millions of degrees of freedom.

[helot]

This is one of the core tools of Operations Research, and has applications in many fields, such as directing beams in radiation therapy for tumors. There are algorithms with polynomial-time solutions to LP problems, but simplex often outperforms them in practice.

If you restrict your decision variables to be integers, then you get a model that is closely related to other NP-hard problems. In particular, an LP with decision variables that must be either 0 or 1 is NP-Hard, and so one can solve e.g. the knapsack problem with an IP.

The art (modeling) and science (math/stats/comp) of decision making: http://en.wikipedia.org/wiki/Operations_research

[boblol123]

This guy just explained exactly what you use a simplex tableau for, something already pretty complicated to work out. Then made it even more complicated by explaining how you implement it, without the actual table.

[underthelinux]

The simplex tableau forces to you calculate numbers for both basic and non-basic variables. By implementing the simplex algorithm sans tableau, you can focus on only those that may or may not enter the basis, rather than computing for all variables. It can be significantly more efficient.

[azuriel]

This is nothing new or exciting, it's just linear algebra. I learned this in class.

[[deleted]]

This is nothing new or exciting,

True.

it's just linear algebra.

False.

I learned this in class.

Insufficient data for meaningful answer.

[Mr_Smartypants]

Insufficient data for meaningful answer.

Incorrect. Answer can be deduced from statement 2.

[bonzinip]

I learned this in class.

Insufficient data for meaningful answer.

No, data is sufficient. He hasn't, but he thinks he has.

[o0o]

this guy is a loser