George Dantzig, 1914-2005

Markus Registrada writes "George Dantzig, the inventor of the Simplex method for solving Linear Programming problems, died on May 13. He was also the now-legendary student who turned in solutions for what he had taken to be a homework assignment, only to find out they had been posted as examples of what were suspected to be unsolvable problems."

Comments

Karma-whoring clarifier

[Knights who say 'INT]

"Linear programming" (as well as "mathematical programming", "convex programming", etc.) has little to do with computer programming. It's about finding the solution to problems like maximize f(x) subject to restrictions r1(x)=0 .. rn(x)=0, r1(x)>0... rn(x)>0.

Incidentally, the Simplex method -- unlike differential calculus-based methods for more general problems like the Kuhn-Tucker method -- is quite programmable on a computer, and quite efficient.

Re:Karma-whoring clarifier

[KeyboardMonkey]

Incidentally, the Simplex method -- unlike differential calculus-based methods for more general problems like the Kuhn-Tucker method -- is quite programmable on a computer, and quite efficient.

The Simplex method can be combined with Kuhn-Tucker conditions and a few small tweaks to solve quadratic problems. This is know as Quadratic Programming (QP).

Quadratic Programming is used in solving portfolio optimisation problems, a mathematical way to ensure a portfolio of risky assets are diversified.

Re:Karma-whoring clarifier

[Pseudonym]

Quadratic Programming is used in solving portfolio optimisation problems, a mathematical way to ensure a portfolio of risky assets are diversified.

It's also used in physical simulation to solve the static friction conditions that arise when many objects are in mutual contact.

Re:Karma-whoring clarifier

[rsilva]

I heard this from Dantzing himself in a pleneray at the International Synmposium on Mathematical Programming at Lausanne in 1997:

In that old days, where computers were new toys, the term programmin had the conotation of "planning". If I remember well, Dantzing said that one of the first uses of the Simplex was to help the Air Force to plan its operations during the war.

As for the non-implementability of gradient based methods in computers. They are as implementable as ODE solvers. This is the domain of floating point numbers, there is no exact implementations of methods. However, there are many good solvers out there solving thousands of real world problems every day. Since I come from academia, I can said some good solvers emerging from universities: the Galahad library, whose web page also provides a list of other good solver like Minos, Knitro, Snopt, Loqo. There is also TANGO which was written and is mantained by some good friends of mine, and the Open Source (CPL) IPOPT.

Things don't stop there. There also many methods non non-smooth problems that employ generalization of the classical concept of gradient and Hessians, like bundle methods from Lemarechal and company, or generalized Newton methos (from Qi and company) and much more.

Optimization is a very rich field from both practical and theoretical aspects. That's why work with it.

For those of you who don't know anything about LP

[Dancin_Santa]

Here's a FAQ: http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-p rogramming-faq.html

What is most interesting about LP is not that it is just a method of finding the solution to a problem, but that it extends in range over many diverse fields from (obviously) computer programming to fields such as economics and even business planning.

Yep. He's really gone

[Anonymous Coward]

Since neither link indicated that Mr. Dantzig had actually died, here is a link to the San Jose Mercury News article on him.

Re:LP's

[log2.0]

There are way too many applications to list here. Ill give you an example though. Say you are a company that produces Chairs and Tables. You sell chairs for $10 and tables for $20. It costs you 5 units of wood to make a chair and 8 units of wood to make a table. It costs you 2 units of labour to make a chair and 3 units of labour to make a table.

Now say you have a certain amount of wood and labour to "spend", how much of each product should you produce to max yield, min waste, min cost, max profit...All different objectives give different answers.

This is a simple example that can be solved without simplex but if you were to scale it up to 1000 products with 3000 resources to be split, it can still be solved with the simplex algorithm.

I have written my own simplex solver and they are tricky but the basic algorithm is elegant.

Of course, the example I gave above is only one and there are many applications in the area of Operations Research (thats not my field btw).

The connection between LP and digital computers

[chris huntley]

Linear programming was among the first "real" applications of digital computers. I saw Dantzig give a talk about it at an INFORMS conference back in the 1980s.

It seems that in a visit to Von Neumann in 1947 he described LP and the simplex method a bit. (See http://www.pupress.princeton.edu/chapters/i7802.ht ml.) It seems that Von Neumann understood everything pretty much immediately, and even derived the dual solution to LP in the first sitting.

I suppose we all know what Von Neumann did next ...

Re:I've been enlightened!

[WaterBreath]

the part about handing in unsolvable homework is great, though probably slightly embellished.

Indeed. According to Snopes, they weren't unsolvable problems. They were just unproven theorems. He didn't know this, and just thought the assignment was to prove them. And so he did. =)

Leonid Khachiyan

[mesterha]

I'm sad to say Leonid Khachiyan also died recently. He proved that linear programming can be solved in polynomial time with the ellipsoid method. I took a class on algorithms from him many years ago at Rutgers. He was an excellent teacher, and he will be missed.