George Dantzig, 1914-2005 298
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. (Score:5, Funny)
We hardly knew ye.
And we certainly had no idea what you were talking about.
Re:So sad. (Score:5, Insightful)
Yes, that is the sad part. Not for him, mind you.
KFG
From the FWIW department... (Score:4, Interesting)
As a physics major, and grad student I bumped into a couple of three fellow students in physics that were down right scary. In all three instances they came from academic families and had *very* strong backgrounds in the subject.
One of these guys had a dad who was a professor of physics, and a mother who was a professor of mathematics. This dude graduated college Summa Cum Laude (he had a 4.0) in three years with a double major in physics and math. He was a really nice guy, quite athletic, and ---drum roll please-- dated regularly.
One seriously scary dude...
One day I said something to one of my physics profs about the dude and my prof told me about his background. My prof who was 'grand old man' of the department point out that having a background such as this fellow had put him at *great* advantage with respect to other students.
My prof was not putting the fellow down. He's point was the the fellow was without question quite gifted, but those gifts would not have been realized without his background.
Same here. (Score:4, Interesting)
I remember his Masters' Thesis defense well. At one point he made an assertion and proceeded to use it as the basis for a greater proof. He was interrupted by one of his examiners, who noted something to the effect that he hadn't mentioned that his proof was conditional on the "blah" conjecture having been proved.
He stopped, looked somewhat confused, and then a look of understanding and pride swept across his face. In his halting English he responded, "No. Wait. I prove. Last week. I have preprint of paper. Want see?" (Yes, he did, and it turned out to be correct).
As I recall, there were two more such incidents during his defense, which lasted about two hours.
Needless to say, his thesis was accepted as submitted (which is rare: most Masters' thesis are accept "with minor modification" (as in, someone found a typo, or an uncited reference)). What's ironic is that he'd effectively had enough material for three PhDs in that Masters thesis.
He went on to a doctorate, and possibly a post-doc in Mathematics.
What's really scary is that he claimed to have an older brother who was much smarter than he was.
Re:So sad. (Score:3, Interesting)
One day he called his grandmother to see how she was getting on. She mentioned that she couldn't talk long because she was having Mr. Dirac over for tea.
"Oh," he says without thinking, "like Dirac Delta function."
"Yes," said his grandmother, "Paul's wife Margit
You're all missing a very important point! (Score:3, Funny)
HE DIED ON FRIDAY THE 13th!
Dear god, when will the madness end? When will we do something about these evil days? Sure, Ashcroft deals with the evil black cats (or was it calico), but what did he do about the terrorism that is friday the 13th?!
DEAR GOD, MY FELLOW AMERICANS, WON'T YOU PLEASE THINK OF THE CHILDREN!!!
(And the elderly scientists).
Damn! (Score:5, Funny)
R.I.P., Dude.
Karma-whoring clarifier (Score:5, Informative)
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 (Score:5, Informative)
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 (Score:5, Informative)
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 (Score:5, Funny)
I once used it to make a perfect ham sandwich.
Re:Karma-whoring clarifier (Score:3, Informative)
Re:Karma-whoring clarifier (Score:2, Funny)
"It's also used in physical simulation to solve the static friction conditions that arise when many objects are in mutual contact."
(sigh) Only on Slashdot would this sentence refer to a mathematical method rather than KY Jelly... ( ducks )
Re:Karma-whoring clarifier X2 (Score:4, Interesting)
Well, to backtrack a bit, we can use linear programming for making predictions "pragmatically". Think the lame old spreadsheet neural net
I mean, saying that linear programming has little to do with computing kind of slaps the best program ever made in its face.
The Spread Sheet (I default to Excel, but insert you fav modern flavor)
Excel is probably the most powerful, robust, versatile, used for everything and the kitchen sink, program ever created. It's a freaking Swiss army knife, and it's because of Linear Programming.
We may not directly use it (ever), but Linear Programming has shaped modern computing as we know it.
Re:Karma-whoring clarifier (Score:2)
Further clarifier (Score:4, Informative)
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 (Score:2)
Well, too bad they didn't have Patton, or they would not have had problems on offense. *:)
Re:Further clarifier (Score:3, Informative)
While Operations researchers do use this algorithym, Operations Researchers [orsoc.org.uk] 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 b
Re:Karma-whoring clarifier (Score:4, Informative)
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 [rl.ac.uk], whose web page also provides a list [rl.ac.uk] of other good solver like Minos, Knitro, Snopt, Loqo. There is also TANGO [ime.usp.br] which was written and is mantained by some good friends of mine, and the Open Source (CPL) IPOPT [coin-or.org].
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 (Score:5, Informative)
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.
Re:For those of you who don't know anything about (Score:2, Insightful)
And of course, optimization is found everywhere you want to do something in the cheapest, fastest, or otherwise most effective way possible. Sometimes yo
RIP (Score:5, Funny)
Re:RIP (Score:5, Funny)
Well, now we have a motive for the murder, at least.
Re:RIP (Score:2)
Makes me wonder how boring their jobs are, to be entertaining themselves like that. Or lack of job, depending on circumstance.
Re:RIP (Score:3, Funny)
It's always sad when a great scientific mind dies.
Meh, he'll be back. Just gotta wait 20 or 30 years for the respawn..
Re:RIP (Score:4, Informative)
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 hope Paul Erdos is right. (Score:5, Interesting)
Re:I hope Paul Erdos is right. (Score:2)
Re:I hope Paul Erdos is right. (Score:4, Informative)
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... ;-)
Re:I hope Paul Erdos is right. (Score:4, Insightful)
LP's (Score:4, Informative)
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.
Simplex method mature? (Score:2)
Re:Simplex method mature? (Score:2)
Hehe, but I am adpopting the simplex algorithm to make it do something else.
Re:LP's (Score:4, Informative)
Re:LP's (Score:5, Informative)
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 (Score:2)
Re:LP's (Score:5, Interesting)
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
Re:LP's (Score:3, Insightful)
You've not played these online? You are likely to find out rather quickly some stunningly effective short-term strategies/techniques used against you.
Nothing like having 50 zerglings show up in your base, for example.
There are some imbalances that only become apparant when a few thousand monkeys have been set loose at the consoles to see what shakes out. Then, they come out with a patch that, oh by the way, a
Not really... (Score:5, Interesting)
Kjella
Re:Not really... (Score:2)
Theoretically not true. In a 2-player game, the optimal strategy is always independant of the opponent's strategy.
Unsolvable geek problems. (Score:5, Funny)
How to get a date?
Re:Unsolvable geek problems. (Score:4, Funny)
Re:Unsolvable geek problems. (Score:5, Insightful)
Just ask.
Re:Unsolvable geek problems. (Score:3, Funny)
-
I've been enlightened! (Score:5, Insightful)
Re:I've been enlightened! (Score:2, Funny)
Yeah, but for the life of me, I cannot understand what's the question behind Goatse!?
Re:I've been enlightened! (Score:3, Funny)
not wanting this to be an OS flamefest though, just take the above as a joke or leave it alone.
the part about handing in unsolvable homework is great, though probably slightly embellished.
Re:I've been enlightened! (Score:5, Informative)
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:I've been enlightened! (Score:3, Insightful)
As long as Rush Limbaugh hasn't succeeded in brain-washing all the Americans, some of them may still have a chance to find such tidbits here [npr.org]
Re:I've been enlightened! (Score:2, Interesting)
>Meaning of life=42, Question=???
In the fourth book, they devise a method of approximating what the Question was. What they come up with was "What do you get when you multiply six by nine".
Now, while 6 * 9 = 42 (in base 13), they make a point of mentioning how this method will only approximate the true Question.
The true Question is, of course, "What do you get when you multiply six by seven" and is mentioned by Arthur several books earlier. He immediately dismisses i
Re:I've been enlightened! (Score:2)
Of course, if you were a nerd as well as a geek, you'd have pointed out that Adams - sadly - got it wrong.
As any physicist will tell you, the ultimate answer is actually 43.
So what (Score:5, Funny)
Genius, ha (Score:5, Funny)
If he was so smart, why did he make the mistake of thinking it was homework?
Re:Genius, ha (Score:2, Funny)
If he's so smart, how come he's dead?
Re:Genius, ha (Score:4, Insightful)
Re:Genius, ha (Score:2, Funny)
Coincidently, it is also well known that mathematical talents are completely separate from spelling ability. For instance, at the very moment you said "intelligence is inversely proportional to common sence", an immense fleet of microscopic warships was consumed by a small dog in the vicinity of Islington. Fortunately this is nothing to be concerned by, because this sort of this is usually Somebody Else's Problem.
Re:Genius, ha (Score:4, Funny)
Re:Genius, ha (Score:2, Insightful)
Yep. He's really gone (Score:5, Informative)
Stupid (but useful) Knight Ridder trick (Score:2)
http://www.mercurynews.com/mld/mercurynews/news/l o cal/states/california/the_valley/11665968.htm [mercurynews.com]
Substitute macon.com for any Knight Ridder paper's native domain name in the url. For brevity and a longer-lived link, also trim the path between the paper's name and
http://www.macon.com/mld/mercurynews/11665968.htm [macon.com]
The Macon Telgraph doesn't require registration yet; all KR papers share article number namespace.
Re:Yep. He's really gone (Score:2)
The connection between LP and digital computers (Score:5, Informative)
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.h
I suppose we all know what Von Neumann did next
A new way of teaching? (Score:5, Interesting)
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
Re:A new way of teaching? (Score:3, Interesting)
It's always "Do this if that comes out but do that if this comes out".
They never, ever, want you to do anything on your own, it's always:
Teacher: Do this
Me: But what if we...
Teacher: Just do it like this, you don't know what your talking about!
Who knows... maybe my school just sucks.
Re:A new way of teaching? (Score:2, Interesting)
I can remember all kinds of arguments and debates I did have, before then, over such things as NP-Complete problems (as related to network topologies), and the like. Although I did not prove NP-Complete (if I had, you'd be reading ABOUT be, not from me), I believe that this is a solvable problem and that I gained
Re:A new way of teaching? (Score:5, Insightful)
"P=NP?" and many other important problems in theoretical computer science are also perfect examples of problems that could be solved by someone working on their own, without even needing much input from a university. The reason that they haven't been solved so far is that they're hard - not because teachers have been "trampling creative geniuses down into the mud".
Scientists (usually) do science because they want to discover new, exciting and creative things - not because they want to suppress independent thought.
I'm also kind of amused by your claim that you'd have achieved as much as George Dantzig if you hadn't given in to all that "social conditioning" thrust upon you.
Re:A new way of teaching? (Score:2)
if you've teached the same course over and over again for 25 years with the same material you probably are pretty much out of any creativity(and most probably using 10 year old transparencies too).
of course then there's the other end of which someone teaching a course on something so new that they don't have actually anything else than opinions on it(and
Re:A new way of teaching? (Score:3, Insightful)
Re:A new way of teaching? (Score:3, Interesting)
familiar (Score:3)
I guess it can be summed up by "choose your battles" although that is a fairly passivist theology.
Translation (Score:5, Funny)
Link [gizoogle.com]
Re:Translation (Score:2)
Re:Translation (Score:2)
Mother (Score:5, Funny)
Re:Mother (Score:2)
Nope.
oblig ATHF quote (Score:2)
Interview ref (Score:3, Informative)
No big loss (Score:4, Funny)
None of his solo stuff after he left the Misfits was any good.
"Muthaaa!" indeed.
I really suffered LP (Score:5, Interesting)
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
reminds me a similar story (Score:4, Informative)
Re:reminds me a similar story (Score:2)
Re:reminds me a similar story (Score:4, Informative)
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:reminds me a similar story (Score:3, Funny)
Leonid Khachiyan (Score:5, Informative)
I'm sad to say Leonid Khachiyan [rutgers.edu] 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.
Travelling Salesman Problem (Score:3, Interesting)
Another thing I'll remember him for is his interesting exercise in urban design Compact City
cheers-raga
Re:Travelling Salesman Problem (Score:2)
the story (Score:3, Interesting)
Wikipedia link (Score:2, Informative)
Sad to hear... (Score:2)
ntpdate (Score:2, Interesting)
To me it seems as though there was a 10 day delay. Did it take that long to realize who this guy was?
I was wrong. Thought the story was about Huffman (Score:3, Informative)
At least he was lucky. (Score:5, Interesting)
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:At least he was lucky. (Score:2, Insightful)
No amount of money will make a dolt a genius.
I know. I've tried.
Re:At least he was lucky. (Score:2)
I know. I've tried.
What, to get paid more?
*ducks*
Re:Oh, now wait a minute... (Score:5, Funny)
Re:Oh, now wait a minute... (Score:2)
Re:He must be rolling in his grave! (Score:4, Funny)
Re:He must be rolling in his grave! (Score:2)
Re:Unsolvable? (Score:2, Informative)
*sigh*
Re:It's 2005 ... (Score:3, Insightful)
From what I can gather airline reservation systems probably work on a similar "dynamic" scheduling system.