Slashdot Mirror
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."
Goodbye, dear friend.
We hardly knew ye.
And we certainly had no idea what you were talking about.
CC Licensed Serialized Story and Podcast: Ingenioustries
At least his teachers knew he wasn't cheating.
R.I.P., Dude.
"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.
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.
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.
Cyde Weys Musings - Scrutinizing the inscrutable
If so, George has certainly earned a look at The Book. (The one containing all possible mathematical theorems...)
Paleotechnologist and connoisseur of pretty shiny things.
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.
Can your karma go above being Excellent?
"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?
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!)
Physicist, consultant, science communicator
"examples of what were suspected to be unsolvable problems" No big deal, I do unsolvable homework problems all the time.
If he was so smart, why did he make the mistake of thinking it was homework?
Since neither link indicated that Mr. Dantzig had actually died, here is a link to the San Jose Mercury News article on him.
Quadratic Programming is used in solving portfolio optimisation problems, a mathematical way to ensure a portfolio of risky assets are diversified.
:P
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.
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.
Well, the mods wanted to post it, but they were waiting for one of them to mathematically prove his death, and CowboyNeil insisted they show their work.
It's times like these we need a moderation option of "-1, crack baby".
-----
PGP Key ID 0xCB8FF658
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.
t ml.) It seems that Von Neumann understood everything pretty much immediately, and even derived the dual solution to LP in the first sitting.
...
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
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
Rosco: "If brains were gunpowder, Enos couldn't blow his nose."
Translation for today's college students. :-)
Link
I wish my lawn was emo, so it would cut itself.
Am I the onlyone who read this and initially thought something along the lines of "what does Glenn Danzig have to do with Pi"?
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"
...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."
*sigh*
College Mathematics Journal, 1986, 16(4), 292-314
None of his solo stuff after he left the Misfits was any good.
"Muthaaa!" indeed.
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
I just read
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.
I doubt that we will ever figure out - and I suspect that even if we did figure out we couldn't do much about it
This is the same feeling I got when studying Physics 2 with no in-depth lecture and a poorly written book. Einstien's theory of relativity just makes rules about what cannot be, and when you look at things as if they cannot happen, usually they dont.
I guess it can be summed up by "choose your battles" although that is a fairly passivist theology.
"And we have seen and do testify that the Father sent the Son to be the Savior of the World"
1 John 4:14
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.
Chris Mesterharm
Another thing I'll remember him for is his interesting exercise in urban design Compact City
cheers-raga
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.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
I worked for many years on a large Telco's work dispatch system based on LP, (8000 users & ~30,000 "jobs" per day). The LP algorithim ran in the background and updated the dispatch plan every 15 minutes, I'm not sure if it "contributed to the well-being and stability of the world".
From what I can gather airline reservation systems probably work on a similar "dynamic" scheduling system.
And did you exchange a walk on part in the war for a lead role in a cage? - Pink Floyd.
I remember taking my required Probablistic Models in Operations Research course back in 2003. I wasnt doing too well in the class and miserably failed my first test. The second half the semester was spent on the simplex method. I remember the class before the test our professor, rather than reviewing decided to mention the names of some prominent Mathematicians. George Dantzing was one of them. How I despised him at the time for nearly ruining my academic life! I would always screw up some thing while trying to do the simplex method. The pivot tables etc. Just too much to keep track of in my head I suppose. I studied my ass off to learn the simplex method. One hour before the exam, I had figured it out. I was so happy that I went searching for a program for my ti89 calculator to check my answers. Low and behold victory was mine!! I will never forget that day cause I strugged so much to learn the simplex. Only later did I realize the significance of what this man had done. RIP
It shouldn't be a surprise if you think about it. Linear programming is the simplest generic form of constrained optimization -- the objective function is linear, all the constraints are linear, and that's it. Once you have figured out how to solve the simple case efficiently, you can use it as a basis to develop solutions for more complicated problems.
And of course, optimization is found everywhere you want to do something in the cheapest, fastest, or otherwise most effective way possible. Sometimes you can make an accurate non-linear model that is solvable, but most of the time you need to simplify the situation. Once you simplify enough, you'll end up with the simplest possible objective function and constraints, in other word, a linear programming problem.
Wikipedia's article on Dantzig. Still a bit thin, but contributors are of course welcome to add up to it!
Quantum hacker.
...if you had a unique goal function and linear equations perhaps. First of all, you are playing against an opponent, so the optimal strategy will depend on his strategy. If they have done this well, there should be a "scissors-paper-rock" balance with no dominant strategy. Secondly, the strength of a battle group is not linear (that is why you have a certain mix of heavy fortifications, long-range artillery, light troopers etc etc). It's not like you can describe it as A*x1+B*x2+C*x3.... = strength, because any one troop type alone would probably be wiped out quickly (unless you have a dominant type, which would make the game rather silly).
Kjella
Live today, because you never know what tomorrow brings
You are all missing a very vital and important point here.
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).
Does anybody see anything wrong with this picture? Died on May 13th... Today's date: May 23rd
To me it seems as though there was a 10 day delay. Did it take that long to realize who this guy was?
What I find interesting is that his father Tobias Dantzig. Ol' Tobias was a Russian mathematician, was a student of Henri Poincaré at the Sorbonne and the author of NUMBER: The Language of Science.
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.
"Oh drat these computers, they're so naughty and so complex, I could pinch them." --Marvin the Martian
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'.
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.
You could've hired me.