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.

Re:Karma-whoring clarifier

[decoutt]

Quote:

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.

In theory, the simplex method is a non-polynomial-time (NP) algorithm, and actually of the worst kind. It is an extremely clever algorithm: it jumps from point to point in order to check whether it is optimal or not, and it can do so exhaustively and in a coherent way. However, it has to check many many points, so many that in theory is the worst thing you can apply to an LP problem.

However, it works quite efficient in practice, and for reasonable problem sizes it spits the solution very fast so that someone can put a simplex solver in a loop and bootstrap it with no remorse.

Of course, nowadays, Interior Point Methods dominate the picture. They are polynomial-time (P) algorithms, they work extremely fast, and they are also very very reliable.

Re:Karma-whoring clarifier

[LifesABeach]

Another way to view the Simplex Method is to find the Identity Matrix for a non-square matrix. It's a very clever way of handling Maximum Profit, Minimum Cost, and Maximum Revenue. This type of problem solving is very interesting when using it to applied systems of mechanics. I never knew the man, but his single contribution changed the way complex systems can be simplified for the great un-washed like myself.

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.

LP's

[log2.0]

I am actually doing part of my PhD on Linear Programming and the Simplex method. This guy was very smart to come up with what he did!

The real world application that the simplex method has is HUGE. I think he has made everyones life a little bit better although most people wouldnt realise it.

Re:LP's

[HermanAB]

LP is commonly used in the design of electronic circuits and filters - so it affected the development of just about anything with a battery or a power cord.

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).

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.

Applications of LP

[Capt. Dick Jackman]

Optimization problems involving several constrained variables

Optimal path choice if we assign costs to each path (Very handy for logistics.)

Works really well with game theory and optimal strategies.

Quadratic programming builds on this and can be used to determine the optimal portfolio using Markowitz mean-variance.

That's all I can think of for now, but there are plenty more applications. Linear programming has to be one of the most handy areas of math and easiest for optimization problems.

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. =)

Re:Unsolvable?

[Anonymous Coward]

If something is unsolvable, coming up a solution is definately impossible. If now we see a solution, that means the person should not have claimed unsolvable. It is at most "no solution to date"

*sigh* ...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."

Interview ref

[Jimmy Breeze]

College Mathematics Journal, 1986, 16(4), 292-314

reminds me a similar story

[Muhammar]

Kids in a second grade class in Brunswick, Germany were asked to sum all integers from 1 to 100. That should have kept them busy for a while but some 8-year old boy - son of a peasant gardener - said in bored voice: "the result is 5050 of course, 50 times 101 ". His name was Gauss.

Re:reminds me a similar story

[Katchina'404]

Either are correct. It depends on how you split the problem... Think about it.

You're calculating the average (50,5) and multiplying it by the number of items (100). 50,5 * 100 = 5050.

The other way is to add 1 + 100 = 101, then 2 + 99 = 101, etc, up to 50 + 51, hence 50 * 101 = 5050.

Re:I hope Paul Erdos is right.

[Quixote]

The one containing all possible mathematical theorems...

Sorry, that's incorrect. Erdos's "The Book" is supposed to contain only the most elegant proofs. Once in a while a mathematician will come up with a proof that is very elegant; such a proof is referred to as being "from The Book". Of course, there's no such "Book" in real life; one gets to see it only in the afterlife, and that too if one's been good... ;-)

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.

Further clarifier

[jd]

Simplex is also known as Operational Research, as early versions were used during military conflicts as a way to produce the optimum use of planes/ships/men in a combat zone, allowing for time spent away from the front-line.

The military value of Simplex was simple. Resources cost money. Lots of money. You also, generally, don't have that many of them. You desperately need to get them to as many missions as possible in the shortest time (allowing for flight times to and from zones, refuelling, etc), allowing for repairs and replacements.

You've also got to find the optimum distribution of fuel, weapons, bases, etc. as the further these places are from where they need to be, the greater the risks (travel is dangerous) and the greater the delays.

Simplex is not "ideal" for a problem of this complexity, but it does a hell of a lot better than guesswork and pencil & paper solutions on the back of an envelope, which is what the British War Office was often reduced to in World War II. They had RADAR, which helped for defence, but offense was substantially more problematic.

Re:Further clarifier

[StrawberryFrog]

Simplex is also known as Operational Research

While Operations researchers do use this algorithym, Operations Researchers would be very upset if you claimed that thier field was just this method.

O.R. in general is the use of mathemicatical, statistical and simulation methods to model and improve the way that companies work, and make their operations more cost-effective. The transport sector is a major employer e.g. it costs more than a few million and takes years to build a railroad - you'd like to know beforehand just how many people are likely to use it if you do. It costs loads of money to have to fly an empty 747 in from New York because you need it in London today. You'd like to plan your air schedule so that doesn't happen.

Wikipedia link

[etnoy]

Wikipedia's article on Dantzig. Still a bit thin, but contributors are of course welcome to add up to it!

Re:RIP

[fbform]

someone was joking about using the simplex method to find the best seat in a theater to see Star Wars.

You and the person who made that comment are both confusing the simplex method in linear programming with the Nelder-Mead downhill simplex method in non-linear programming. Yes, I am an optimization geek.

I was wrong. Thought the story was about Huffman

[ishmalius]

For years, I had confused the parable of the prodigal student with that of David Huffman (of the ubiquitous huffman code). But the story is very similar. He said that he never felt famous until he saw his code spelled with a small 'h'.

Re:Oh, now wait a minute...

[Anonymous Coward]

3seas, aka Tim Rue, is a well-known nutjob (to the point that someone even wrote a FAQ about him and his irrational behavior in the Amiga newsgroups). Wait 'til he metabolizes a little more of his meds and starts claiming to be Jesus. No, I'm not exaggerating.

You think Gentoo zealots are annoying? Imagine hearing that buying Windows is like crucifying Jesus and that Trinity and Morpheus don't like it, either.