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

So sad.

Goodbye, dear friend.
We hardly knew ye.
And we certainly had no idea what you were talking about.

Re:So sad.

And we certainly had no idea what you were talking about.

Yes, that is the sad part. Not for him, mind you.

KFG

Damn!

At least his teachers knew he wasn't cheating.

R.I.P., Dude.

Karma-whoring clarifier

"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

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

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.

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

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

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.

RIP

It's always sad when a great scientific mind dies. And I recall, just recently, someone was joking about using the simplex method to find the best seat in a theater to see Star Wars.

Re:RIP

And I recall, just recently, someone was joking about using the simplex method to find the best seat in a theater to see Star Wars.

Well, now we have a motive for the murder, at least.

I hope Paul Erdos is right.

If so, George has certainly earned a look at The Book. [c2.com] (The one containing all possible mathematical theorems...)

Unsolvable geek problems.

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

How to get a date?

I've been enlightened!

Now this is why I read Slashdot - where else can you get such a diverse range of people, and pick up wonderful little tidbits like the true story behind that wonderful legend about solving unsolved problems? Sure, it's available on Snopes for you to find if you know what you're looking for, but asking the right question is often a lot harder than the answer, as best illustrated bythe Hitch Hiker's guide: Meaning of life=42, Question=???. (Hey, perhaps if they'd put that up on the board, he might have been able to solve that as well!)

Re:I've been enlightened!

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

So what

"examples of what were suspected to be unsolvable problems" No big deal, I do unsolvable homework problems all the time.

Genius, ha

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

If he was so smart, why did he make the mistake of thinking it was homework?

Yep. He's really gone

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

The connection between LP and digital computers

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 [princeton.edu].) 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 ...

A new way of teaching?

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

I can't help but think if he ever would have solved those problems had he been taught first that they were unsolvable??

Schizo Person #1- "Look, there is an elephant in the room"
Schizo Person #2- "Shhh!!! There is no elephant"
Schizo Person #1- "But..."
Schizo Person #2- "No buts, you don't want them to think you're crazy"

Soon Schizo Person #1 stopps seeing the elephant. It really does not exists to him

Translation

Translation for today's college students. :-)

Link [gizoogle.com]

Mother

Am I the onlyone who read this and initially thought something along the lines of "what does Glenn Danzig have to do with Pi"?

I really suffered LP

Well folks, I'm an accountant. You can have all the fun you want about having an accountant here, but that's the way it is. In Argentina, where I come from, that was the best way to land a management position in no time, which I'm still waiting for.

All that aside, I love technology in all its forms, just in case.

Studying my 4th year, we've been teached LP, as a way to solve transport route problems, and minimum stock estimates, optimizing resources and stuff, in an assignment called "Operations Research".

I hope one of my fellow students will read this, but I really doubt an graduate from Facultad de Ciencias Economicas - Universidad Nacional de Cordoba would read /.

We always dreamed about finding the damn mf that invented the simplex method, but the net was far from being an accesible thing those days, so now that I find out about Dantzig, I'm kinda sad. There was a time when I would have cursed his family and chased him if he was within reach, but now I pay him honors, as one of many bright minds that go by unnoticed for students and developing minds all over the world.

My respect

Re:LP's

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

Re:LP's

hehe, I was thinking about applying the LP solving technique to these types of games but they made it difficult...For example, in warcraft 3, there are different types of armour and "attacks". So you have to choose which type of armoured and attack units to make. I am very certain that Blizzard looked at the linear space and made sure that the constraints in the system all had the same n-dimensional slope.

A few years ago, I looked into it for night elves and that was the case for a few units.

Either way, if the game did have some inbalance, you *could* find it if you could be bothered :)

At least he was lucky.

What happend to me was the opposite.

A few years ago my math teacher gave us an exam with one particular problem that I couldn't solve. (Apparently a typo or misplaced sign made a rather simple problem into an unsolvable one).
So I went to the library, researched on the problem, and found out it was unsolvable. I PROVED IT mathematically, but the teacher didn't believe me.
And my grade wasn't changed! Doesn't that suck!?

Lesson to be learned: Life's not fair. SPECIALLY with underpaid teachers designing the exams. Hmph.

Re:Oh, now wait a minute...

It's times like these we need a moderation option of "-1, crack baby".