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

So sad.

[Shky]

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

Re:So sad.

[kfg]

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

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

KFG

Re:So sad.

[Anonymous Coward]

You may not have known him by that work, but I'm sure that you know his other work - the cultivation of the dreaded herpes simplex.

Re:So sad.

[hey!]

Reminds me of a story a friend of mine who attended MIT with me in the late 70s early 80s once told me. My friend's grandparents were Eastern European Jews, who emigrated to the UK in the 30s, and in the 60s to the US, finally settling in Florida.

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 is visiting, would you like to talk to her?"

"NOOOO!!!"

Damn!

[Anonymous Coward]

At least his teachers knew he wasn't cheating.

R.I.P., Dude.

Re:Damn!

[Anonymous Coward]

I have my doubts on whether it was Danzig being origin of this legend since I've heard this so many times before with other mathematicians names in place of his.

For instance, Milnor. Instead of a unsolved stat problem he solves a (then unsolved) problem relating a knotted space curve and its total curvature.

Re:Damn!

[Anonymous Coward]

R.I.P., Dude.

Where his tombstone reads:
"Muthaaa, do you wanna do math with mEEeee"

Re:Damn!

[hey!]

Well, given the nature of mathematical genius, it wouldn't be surprising if it weren't true of more than one of 'em.

Mathematical genius emerges in youth, and the early years are often the most productive for creative ideas. Mathematical insight is a kind of ability to leap off the beaten track onto an unexplored one; unfamiliarity with the corpus of work on the beaten track wouldn't necessarily preclude someone who had this faculty, say a gifted student who understood the basic problem, from accomplishing this.

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

[Anonymous Coward]

In most cases, I believe you can increase stimulation by introducing a bit of friction during mutual contact... Oh wait, you said simulation, my bad :)

Re:Karma-whoring clarifier

[Anonymous Coward]

I had hoped there was a +5 Funny post at the end of this thread, would make me feel a bit less ignorant

Re:Karma-whoring clarifier

[Pxtl]

iirc, the form used on computers is usually considered the "modified simplex method" because it involves calculating less of the tableau.

Re:Karma-whoring clarifier

[PlacidPundit]

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

I once used it to make a perfect ham sandwich.

Re:Karma-whoring clarifier

[Anonymous Coward]

does that apply to hands and breasts ?

Re:Karma-whoring clarifier

[Young Master Ploppy]

"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

[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

[JPelorat]

Feh, you don't need mathematics to make perfect sandwiches. You just need to roll 20s.

Re:Karma-whoring clarifier

[simpl3x]

i once used it as a id on slashdot!

Re:Karma-whoring clarifier

[Anonymous Coward]

> I once used it to make a perfect ham sandwich.

Pfff that's nothing. I made a toilet you never have to flush. Or so I keep telling myself...

Re:Karma-whoring clarifier

[Anonymous Coward]

I once used it to make a perfect ham sandwich.

You must mean a perfect Perfectly Normal Beast sandwich.

Re:Karma-whoring clarifier

[bdktty]

That's simulation, not sTimulation...

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.

Re:Karma-whoring clarifier

[decoutt]

It was also used in the Soviet era for planning manufacturing activities, transportation of goods between the Soviet states, etc.

The 1975 Nobel in Economics went actually to LP and its contribution to the understanding of these activities. Some people expressed their 'outrage' for not including Dantzig in the laureates.

Re:Karma-whoring clarifier

[r_j_howell]

but how did you cut it in half?

Re:Karma-whoring clarifier

[mforbes]

(sigh) Only on Slashdot would this sentence refer to a mathematical method rather than KY Jelly... ( ducks )

Um... just how many objects did you plan on using?

Re:Karma-whoring clarifier

[Anonymous Coward]

Even though interior point methods are polynomial, they always take the worst case number of steps and has a rather large constant multiplier. Simplex is still quite competitive for most problems.

Re:Karma-whoring clarifier

[JakeThompson1]

Yeah, but the stimulation is a simulation of a certain other activity involving 2 people...

Re:Karma-whoring clarifier

[fiftyfly]

I once used it to make a perfect ham sandwich.

You must mean a perfect Perfectly Normal Beast sandwich.

Actually further research indicates that the perfectly normal beast sandwich is only a local optimum (the beast being discontinuous). Following an earlier work it seems that the penultimate sandwich may be egg & cress though, too, may fail to prove universal as research has turned up empirical evidence for two conditions only - approx the creation of the universe and (with slight variations) the gi tract of one particular cryogenic time traveler.

Re:Karma-whoring clarifier

[Young Master Ploppy]

Um... just how many objects did you plan on using?

Two is enough. Any more is a bonus...

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.

Leonid Khachiyan Is Dead at 52; Advanced Computer

[Anonymous Coward]

Leonid Khachiyan Is Dead at 52; Advanced Computer Math

"Dr. Khachiyan proposed using an ellipsoid algorithm in approaching theoretical problems believed to be too demanding for the simplex method"

http://www.nytimes.com/2005/05/22/nyregion/22khach iyan.html?pagewanted=print

RIP

[Ignorant Aardvark]

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

[physicsphairy]

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.

Re:RIP

[WhatAmIDoingHere]

What does this have to do with anything? What is going on? These replies about previous stories are everywhere..

Is /. under attack?

Re:RIP

[X0563511]

Not only are they from other stories, but parts of whole actual threads are copied around. All as AC (or a different user than the origional) of course.

Makes me wonder how boring their jobs are, to be entertaining themselves like that. Or lack of job, depending on circumstance.

Re:RIP

[FuzzyBad-Mofo]

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

[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 hope Paul Erdos is right.

[FlyByPC]

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

Re:I hope Paul Erdos is right.

[FlyByPC]

Whiskey-tango-foxtrot, over?

Re:I hope Paul Erdos is right.

[Dasein]

Yep, I think he earned a good, long look. Someday, I hope to earn my peek.

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

Re:I hope Paul Erdos is right.

[mcg1969]

Actually I figure that mathematicians in Hell probably get to see it as well, so they can be tormented by the knowledge of just how inelegant their proofs were.

Re:I hope Paul Erdos is right.

[cerebis]

Since we've strayed onto the subject of Paul Erdös, I would like to build a bridge back by mentioning that George Dantzig had an Erdös number of 2, meaning that he co-authored a paper with a co-author of Erdös.

Something most any academic would be proud to claim. Erdös' publised 1521 papers, and was very fond of collaboration regardless of political divisions.

Read "The Man Who Loved Only Numbers", a very interesting book.

http://www.oakland.edu/enp/readme.html

Re:I hope Paul Erdos is right.

[Crazy Eight]

Here's a link to an NPR show about Erdos and a few others with commentary by someone who worked with him for a spell. Apparently, some of his prolific output can be attributed to amphetamines.

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

[DrHanser]

Can you elaborate on some of its ramifications/applications?

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

Re:LP's

[Lt.Hawkins]

Awesome! So basically... Starcraft/Warcraft/Age of Empires has been solved!

Re:LP's

[log2.0]

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

Re:LP's

[Anonymous Coward]

The business solution is simple:

Make only tables and, with a small part of the profits, buy a compnay that makes chairs (people have to sit on something if they have tables).

Re:LP's

[Forbman]

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

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, adjusts unit parameters to take the most glaring imbalances away...

Re:LP's

[Woy]

Warcraft is pretty balanced at high level play. It's not your common developed-released-forgotten RTS.

In fact, your ideal army is absolutelly dependant on the enemy's army. Scouting is where it's at.

Re:LP's

[lawpoop]

"Nothing like having 50 zerglings show up in your base, for example. "

And there's nothing *better* than having a few firebats waiting for them.

Unsolvable geek problems.

[Anonymous Coward]

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

Re:Unsolvable geek problems.

[HoneyBunchesOfGoats]

Well, he was married, so he must have solved that problem. Unfortunately he did not elect to share the proof publicly. :)

Re:Unsolvable geek problems.

[Anonymous Coward]

There is no cheese in the recipe. The cheese is just there so you know how long to leave it on a tray under the broiler.

Re:Unsolvable geek problems.

[halleluja]

How to get a date?

Just ask.

Re:Unsolvable geek problems.

[jabber01]

Maybe it just didn't fit in the margin?

Re:Unsolvable geek problems.

[Dan D.]

Your handle juxtaposed with your message is either Ironic or Serendipitous. Hopefully this message will start a huge flamewar where the answer doesn't come.

obtopic: find $Msg*Handle = Classifier$, minimizing $Classifier = Ironic^t*Serendipitous > 0$.

Re:Unsolvable geek problems.

[Alsee]

I think he was hoping for an answer that can actually be used by geeks.

-

I've been enlightened!

[Bifurcati]

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!

[metlin]

Yeah, but for the life of me, I cannot understand what's the question behind Goatse!?

Re:I've been enlightened!

[rokzy]

reminds me of someone's sig - "Microsoft is not the answer, Microsoft is the question. the answer is no."

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!

[papaia]

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

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

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:I've been enlightened!

[rhyno46]

I get your point. Unfortunately I must use my geekness to clarify... According to your equation "Meaning of life=42" your question is "What is the meaning of life?" 42 is actually the answer to The Ultimate Question, which we don't know.

Re:I've been enlightened!

[pcgabe]

Pardon my nerdiness, but...

>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 it as too obvious, overlooking the fact that he is from Earth, the planet/computer designed to come up with the Question. Earthlings' brains work different from other sentient beings, which is also why they can name a place "Belgium" without blushing, and why they are not so adversely affected by Vogon poetry.

Some could even argue that Earthlings can know both the Question and the Answer simultaneously without going insane, but those people are idiots who haven't been paying attention.

Re:I've been enlightened!

[pcgabe]

Pardon my foolishness, but...

That's actually the end of the second book, not the fourth book.

And the question was: "What do you get if you multiply six by nine".

Of course, you can always just ask Google for the answer, or look it up on Wikipedia.

...note to self: Research first, post on Slashdot second. But I'm new here.

Re:I've been enlightened!

[ozmanjusri]

Unfortunately I must use my geekness to clarify.

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.

Re:I've been enlightened!

[NicenessHimself]

unproven theorems? Is this science or maths?

If it is maths, and it is unproven, it is conjecture..

Re:I've been enlightened!

[Lifewish]

Well, we know they're theorems *now*...

Re:I've been enlightened!

[lyoz]

Indeed. According to Snopes, they weren't unsolvable problems. They were just unproven theorems.
This is getting silly. Obviously the problems were solvable; You cannot have a solution for known *unsolvable* problems, thus the title.
There is a difference between a conjecture and a theorem. Theorem is a statment, conjectured by someone, and proven to be true or false.
So here is how it should be stated. Dantzig mistook for homework a conjectured problem, which was infact proven to be *solvable* but no solution was known. Thus classifying them to be *open* problems.
So where was I....

Re:I've been enlightened!

[dillon_rinker]

Yup. Not unsolvable, merely unsolved. Anyone with a grasp of the English language would realize that. Snopes seems to delight in sneering at the obvious.

So what

[keziahw]

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

Re:So what

[Anonymous Coward]

I had a professor that used to give out "unsolvable" problems, and not tell us that they were unsolvable. It used to annoy the hell out of me.

Oh, and when did Slashdot start asking to input an obfuscated string before posting?

Re:So what

[hexadecimate]

> No big deal, I do unsolvable homework problems all the time. No, you _don't_ do unsolvable homework problems all the time. It's an important distinction.

Re:So what

[WhatAmIDoingHere]

Only as AC because of all the crapflooding.

Genius, ha

[Anonymous Coward]

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

Re:Genius, ha

[Anonymous Coward]

Better question:

If he's so smart, how come he's dead?

Re:Genius, ha

[Anonymous Coward]

Oh man, now THAT was funny.
*wipes tear from eye*

Re:Genius, ha

[unixbum]

It's a well known fact that intelligence is inversely proportional to common sence.

Re:Genius, ha

[Infinityis]

I think maybe his apprentice killed him.

How ironic...he could use the simplex method to save others, but he could not even save himself from death.

Re:Genius, ha

[FuzzyBad-Mofo]

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

[Taladar]

That would mean there are a lot of insanely intelligent people out there. I guess I am not the only one who doubts that...

Re:Genius, ha

[BlockedThreads]

It is possible that his belief that it was a homework problem gave him the confidence that there was a simple and elegant solution. Without this belief he might never have explored solutions that were "too simple" to work.

Re:Genius, ha

[Anonymous Coward]

Among the inversely intelligent, that is.

Re:Genius, ha

[Anonymous Coward]

"what's good about toddler murder"
"-it's EASY!!"

Re:Genius, ha

[Anonymous Coward]

He was tardy for the class and sat in while the theorems were on the chalk board, so he copied them down and took them home as homework.

It sometimes helps to read the links.

Re:Genius, ha

[Anonymous Coward]

which, in turn, is inversely proportional to spelling skills.

Re:Genius, ha

[DarkSarin]

What bothers me about this is not that it got moderated upward--it certainly deserves that, but what moron moderated it INSIGHTFUL?

Funny, yes, although sarcastic is more accurate (and not the same as funny in all cases).

Frankly, I think it is sad that so many people think that really smart people are lacking in common sense. Truth is that there is a strong correlation between the most classically accepted types of intelligence as defined by those that study such things. The correlation isn't that high, but it is there. In no case is there a negative correlation between the different types of intelligence.

Oh well.

Re:Genius, ha

[iphayd]

Spelling aside, can't you imagine that he loved his work so much that he saw the homework as a challenge as well as homework? I would imagine that even if he did know that the equations were "unsolvable", he would have still played with them and eventually solved them. Possibly not as fast as he did, but he would have solved them eventually.

Re:Genius, ha

[Rufus88]

Well, then, if you believe my wife and my mother, I must be infinitely intelligent.

Re:Genius, ha

[Anonymous Coward]

Being ignorant is not incompatible with being ignorant.

(I'm not sarcasm impaired... I did find that funny ;)

Re:Genius, ha

[Dan D.]

Just because its well-known doesn't mean its a fact.

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.

Simply wonderful algo

[RockoW]

this semester i learned this wonderful method for solving linear programs... the demonstration is so complicated. He must be one of those great minds that make the human being something that worth.

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.

Re:Karma-whoring clarifier X2

[Mr.Zong]

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

Well, to backtrack a bit, we can use linear programming for making predictions "pragmatically". Think the lame old spreadsheet neural net :P

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:Oh, now wait a minute...

[Anonymous Coward]

shut up

http://www.the7thhouse.com/

[Anonymous Coward]

For more lyrics...

Re:Oh, now wait a minute...

[jay-be-em]

what the hell are you talking about

He must be rolling in his grave!

[rokzy]

all that fancy computer work and it still took 10 days for news of his death to hit slashdot!

Re:He must be rolling in his grave!

[_KiTA_]

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.

Re:He must be rolling in his grave!

[rfernand79]

the date is a local minima...

Re:Karma-whoring clarifier X3

[ToasterofDOOM]

*cough* DATABASE *cough*

At least he was lucky.

[Spy der Mann]

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:At least he was lucky.

[Jumperalex]

DOH ... the SAME thing happened to me in my optimization class. Well someone else showed it was unsolvable, but at least our instructor manned-up to the situation and gave us the points.

Perhaps your instructor just figured since it was unsolvable, no one solved it, so it isn't like anyone got an advantage [shrug].

Re:At least he was lucky.

[YOU LIKEWISE FAIL IT]

If the problem was indeed unsolvable, then nobody in the set of exam students would have been able to solve it correctly either.

As the purpose of university exams since the invention of the grading curve is largely to sort the students by some semi-abstract form of academic capability, there really was no deleterious effect from you losing that mark.

YLFI

Re:At least he was lucky.

[mc6809e]

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

No amount of money will make a dolt a genius.

I know. I've tried.

Re:At least he was lucky.

[grammar fascist]

No amount of money will make a dolt a genius.

I know. I've tried.

What, to get paid more?

*ducks*

Re:At least he was lucky.

[Anonymous Coward]

I know. I've tried.

Bill Gates? Is that you?

Re:At least he was lucky.

[Anonymous Coward]

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!?

S: Professor, For question 23) "5 + 3 = ???" I put '8', but you marked it as wrong.

T: Question 23? The answer is '2'.

S: 5 + 3 = 2 ???

T: Hmm. Looks like a typo. It was supposed to be '5 - 3 = ???' I must have hit the wrong key.

S: So do I get credit for giving the correct answer?

T: No. The correct answer was '2'. The question was wrong. It should be obvious, isn't it?

S: [dumbstruck]

Re:At least he was lucky.

[Famatra]

"And my grade wasn't changed! Doesn't that suck!?"

Did you write down everything with a dated coverletter and explain what the problem is? Doing so means that you are making a case and will appeal, it is a subtle bluff (or perhaps not a bluff at all since I see no reason to appeal it above his or her head, why didn't you?).

I had something similiar happen to me, but the professor had marked things wrong on the exam that were marked right on the text that were word for word. Split the page up into two columns and write your answer down on the left, and write down what the text says (or what your other test said) then highlight the common points. Below put talking points, and clarification.

You also don't need to be confrontational, I said that perhaps his TA was confused when marking the test even though I knew it was them, you have to give these people a way out if your goal is the marks (sometimes a person's goal is to embarrass the professor which is nice, but a secondary consideration in my case :P).

If all that fails, you could aways make a webpage with a scan of the question, your arguement that it is unsolvable, then email his collegues asking for their opinions and include them on the site. The university doesn't want its professors looking stupid, that doesnt really attract students ;).

Re:At least he was lucky.

[VAXcat]

When I took an assembly language course, many years gone by, there was a question I answered by Bit clearing via a mask, and then bit setting via another mask. In this particular case, I trimmed 4 instructions out of the equivalent operation using CLRs and MOVs. Unfortunately, the labby grading the tests didn't know how to use BIS and BIC, and had no understanding of what bit masks were all about. It took a good solid hour of arguing to get her to understand the answer. She finally got it, after I explained those two instrucitons and a good bit of binary arithmetic about masks. I got the points on the test, and she got a much needed bit of tutoring in computer archtecture.

Re:At least he was lucky.

[Anonymous Coward]

Had a similar experience in physics. The test had a fairly complex wheeled pulley system, counterweights, etc. We were to find the length of time for one of the weights to drop to the point on the platform directly below it. After about half an hour of trying to write the equation I would then have to solve, I realized that the acceleration of the whole contraption would cause the weight to swing (why I was having such a hard time writing down the problem), and that it was vanishingly unlikely that the weight would hit the platform at the point directly below. With that realization, the answer was obvious: infinity.

I didn't get credit either. No one else solved the problem as asked, but most of them did receive credit. Never been willing to forgive pompous English visiting professors who won't admit to a mistake.

Re:Yep. He's really gone

[Withershins]

Registration required....

will hunting inspiration?

[Anonymous Coward]

My boy's wicked smart.

Re:Oh, now wait a minute...

[MustardMan]

This is your brain on drugs. Any questions?

Re:Oh, now wait a minute...

[Simon Garlick]

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

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:The connection between LP and digital computers

[plupster]

The existens dual problems was already known (discovered by von Neumann). And the dual to a LP is just another LP. So I'm not suprised that von Neumann could derive the dual solution rather quickly.

A new way of teaching?

[John Seminal]

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

Re:A new way of teaching?

[Lingur]

That's an excellent question. I have always been a bit frustrated in my math classes because they never teach you to think outside the box.

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?

[jd]

Actually, no, yours is not the only school. I ran up against that kind of mindset many times in England and eventually learned to "dumb down" my thinking for the benefit of the school/University.

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 at least some insight into the perceptions that underly why it is such a difficult challenge.

The difference between me and George Dantzig? About the same as between be and Neanderthal Man. Neanderthals had the capacity to do a great deal of creative thought, lateral thinking, etc. They didn't, not because they couldn't, but because they never took the steps it would have required.

Likewise, I may very well have the mental capacity to solve all sorts of complex, abstract problems. I've an IQ of 148, my range of knowledge in science and technology is extensive, but I've never really put that intelligence to the kind of use that it is theoretically capable of.

George Dantzig did. THAT, and nothing else, is what makes him the genius and me the Slashdot reader. Which is all credit to him. It is very tough to overcome real or imagined social conditioning that says that we should all be dumb and unthinking, and whilst I don't easily give into that, the difference is that George Dantzig clearly did not give in at all, but rather ignored it completely.

Unsolvable? Hah, mere homework.

Y'know, it wouldn't surprise me if schools expected students to have that kind of attitude, rather than one of "if the examiner is in a bad mood, we'll fail anyway, so we might as well not put in any more effort than we need to, to scrape by", that schools would produce such minds as a matter of course.

"Genius" is not really that rare of a thing for biological reasons. It is rare because we tell the next generation that it is rare. The only two groups who really succeed in life are those who are damn certain they're geniuses and work damn hard to prove it, or who drop out enough not to be affected by such banality.

All it should really take, to produce an entire nation of Einsteins and Dantzigs is to encourage even the briefest glimmer or the slightest spark of thought.

To me, the greatest honor we can give the greatest minds of all time is to allow all the other great minds to be as great as they want to be, rather than trampling them down into the mud as though creative thought were somehow dirty and disgusting, if it isn't in a different century and preferably a different country as well.

Re:A new way of teaching?

[Anonymous Coward]

Your IQ is 148, but you can't tell the difference between a "b" and an "m"?

"you'd be reading ABOUT be, not from me"
"About the same as between be and Neanderthal Man."

Re:A new way of teaching?

[Catullus]

I'm sorry, but I have to disagree. While there are, of course, many bad teachers, there are also many who encourage creative thinking and reward originality.

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

[Anonymous Coward]

Say some who encourage thinking and originality. The percentage was low when I went to school, and from all reports, has gotten lower still.

That this is at least partially because we pay our teachers so poorly is a side topic.

But the fact is, the vast majority of the educational effort is designed to teach students to sit down, shut up and blend in. All too often it has precious little to do with education.

Which might be why most geniuses do poorly in school; schools don't like people making their own rules.

As for the original poster, I wouldn't think that anyone with an IQ of 140+ would be stupid enough to post that comment. But, there ya go.

Re:A new way of teaching?

[gl4ss]

*Scientists (usually) do science because they want to discover new, exciting and creative things - not because they want to suppress independent thought.*

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 thus you have to buy _their_ book on the subject to know what are _their_ opinions so you know what is the 'correct' answer to questions that have 50 vastly different answers if asking from another profs. in the field - tha's not much to do with creativity).

Re:A new way of teaching?

[GreatBunzinni]

Likewise, I may very well have the mental capacity to solve all sorts of complex, abstract problems. I've an IQ of 148, my range of knowledge in science and technology is extensive, but I've never really put that intelligence to the kind of use that it is theoretically capable of.

Don't forget that IQ is meaningless. First of all, it is a quotient between two numbers that are supposed to measure inteligence (how do you measure something which isn't even defined?). Second, the IQ test was designed with children in mind (the IQ compares the subject's test score with the supposed normal score for the kid's age), to be able to filter the supposedly more advanced kids. And third, it is shown again and again that the test is absolutely meaningless. It is even not supposed to be applied to people over 18. The only practical use that is given to IQ tests is from those that are tested and have a high score. They use it again and again to try to elevate oneself above the others and to try to justify the unjustifiable: a supposedly higher inteligence.

P.S.: Boy, you are just full of yourself, aren't you?

Re:A new way of teaching?

[Skye16]

I don't know if it's just your school, but I know the Calc I and II prof I had at the University of Pittsburgh at Johnstown was way different. He didn't want to just tell you a method and have you figure it out. First he went through why it was necessary to come up with a method for solving a certain type of problem, and then he worked with us to come up with our own way through it. Sometimes it took 2 or 3 classes before we finally figured out how to actually do it (eventually he would give us hints to guide us, but he mostly wanted to see what we were going to come up with on our own). Having had Calc before I went to college, I knew most of the methods, but I didn't know how those methods were discovered in the first place. This made my calc class somewhat difficult (in that I had to show up), but I also learned an awful lot as well.

It's been about 5 years and everything is hazy, but I remember on our final project in calc 1, we had to do a series of somewhat-related problems that lead us to answering the final question, write a paper on it, and show some nice diagrams. I was skimming through the final problem and I realized there was a different - and much easier way to solve it. I did it and showed him and he told me to include it in with the paper, but to do the others as well. The two "math guys" (myself and another) finished our part, and the "paper people" wrote up the paper (which was a bad idea). The math was right, but the paper was messed up. However, by turning in the new method of solving the problem, we got enough bonus points to give us a perfect grade on the final project.

I had him later for a Math History class as well (not just memorizing mathematicians and dates, but also how they determined their methods and why) and we had various problems to solve. There were a few times where I (and others) would do it in a different way to what he had expected us to do it, but that just made him even happier when it happened. He never shut us down on new method we used, even if he was pretty adamant on us at least learning how it was usually done. I still think he was one of the best professors I ever had.

Other than him, though, that whole college sucked. There were a good 4 professors that I had that I thought did an amazing job of teaching. The others were just a big waste of time. I was better off teaching myself from the book and saving myself all the time I would have wasted sitting through their pointless classes.

Re:A new way of teaching?

[jallen02]

One of the greatest faults anyone can possess is an inflated view of ones self. It is REALLY common. If you read about many people who have performed amazing works you will find they don't think to much of it. They are just doing their best. There are some people who are smart and they both know and act like it.

I think the best strength/flaw in human existence is TRULY knowing where you stand as a strength and thinking more highly of yourself than you actually are as a flaw. Its quite insidious because in America you MUST make yourself truly valuable and sell yourself as valuable after developing marketable skills. So you get used to promoting yourself. Unfortunately most people don't understand where to stop with the self promotion and they develop a much higher view of themselves than they should. It is really hard to keep yourself grounded, but if you pay attention life regularly serves up humility :)

Jeremy

Re:A new way of teaching?

[Just Some Guy]

Don't forget that IQ is meaningless.

If that were generally accepted, we wouldn't be having this conversation. Your stating it as fact doesn't necessarily make it so.

First of all, it is a quotient

Most mappings from test score -> 100-centered scale involve standard deviations. That is, IQ = 100 + (number of standard devations from the mean) * (15 or 16). 15 or 16 comes from an effort to correlate that score with the rational score you mentioned, but that's about the only tie between the two.

Second, the IQ test was designed with children in mind

There is no "the" IQ test. There are many to choose from, depending on who and what you wish to attempt to measure.

Boy, you are just full of yourself, aren't you?

Yes; yes, he was. I'll give you that one. :-)

Re:A new way of teaching?

[Anonymous Coward]

Cut the brother some slack; he's got a cold.

Re:A new way of teaching?

[Nate4D]

Sometimes the teachers really do know better.

Certainly when it comes to mathematical proofs, when a professor warns you that you won't be able to do the proof, it's usually because you haven't had training in the types of proof methods that are likely to be required.

Yeah, it's possible that you'll find the brilliant, elegant, simple proof. But it's not that likely, if no one else has found it yet...

I'm not saying don't try; I'm saying there's a reason why they warn you about them.

That said, nothing has ever annoyed me more than my discrete math professor saying, "Don't worry about this proof; a student could not understand it."

Re:A new way of teaching?

[danharan]

If you are so smart, learn to undo your conitionning.

Re:A new way of teaching?

[Kiryat Malachi]

There's a world of difference between a scientist, a professor, and a teacher.

Re:A new way of teaching?

[Anonymous Coward]

One of the greatest faults anyone can possess is an inflated view of ones self. It is REALLY common. If you read about many people who have performed amazing works you will find they don't think to much of it.

Newton had quite an ego. Gauss did as well. Aristotle wasn't some shrinking violet, either. That's three of the best mathematicians in history.

Galilleo had the nickname "Wranger" for being contrary. Socrates was nicknamed "the Gadfly"; he used his superior intelligence to simultaneously annoy and educate.

One promiant mathematician (Kumer? Dedekind?) was known for his pronounced beliefs in the perfect of of the integers ("Die Zahlen hat Gott gemacht; alles anderes ist Menchenwerk" -- 'God created the Integers, all else is the work of Man').

Like all people, there are egotists, and humble people among geniuses: brilliance isn't due to any religion, politics, nor social beliefs, despite the pressing claims by various partisan factions.
--
AC

Translation

[autojive]

Translation for today's college students. :-)

Link

Re:Translation

[KD5YPT]

... College student don't talk like that. Maybe those Stanford rich kids do, but not serious Engineers.

Re:Translation

[Stealth Potato]

Damn... I didn't even get past "computatizzle optimizzle" before my soda was all over the keyboard.

Re:Translation

[fbjon]

What the hell is that all about??

Mother

[cloudmaster]

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

Unsolvable?

[at2000]

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", like P=?NP.

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

Re:Oh, now wait a minute...

[MustardMan]

No kidding. Out of morbid curiosity I went back through this guy's posts. Not all are as bad as this one, but few make any more sense. The guy is either an incredibly eccentric troll, a complete idiot, or totally fucking batshit insane.

Re:Mother

[Anonymous Coward]

There for a second, I thought all hope for a Misfits reunion was lost.

Interview ref

[Jimmy Breeze]

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

Re:Interview ref

[sv0f]

Great reference. Just downloaded it from JSTOR.

Thanks!

Re:Mother

[psykocrime]

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

Nope.

Re:Mother

[keziahw]

AND... Why does it show Einstein next to the Pi next to the article? ---- Your dogma ran over my karma, so now you have to mod me up, or I'll call the poundma.

No!

[FAUrrego]

May 13th? Well Happy Birthday to me :( On a side note: This year May 13th was also a Friday. *puts on tinfoil hat*

What?

[Anonymous Coward]

That guy from the misfits died?!?!

No big loss

[andy@petdance.com]

It's hardly a loss.

None of his solo stuff after he left the Misfits was any good.

"Muthaaa!" indeed.

Re:No big loss

[ArgieNomad]

Man you're nuts! Glenn Danzig i/was great. He starred my wardrobe across high school. I don't remember how he sounds like, but I really loved GD back then.

(lookin' for my creepy buffalo skull tee)

Re:No big loss

[Moses_Gunn]

Offtopic, but I beg to differ. Yes, what the Misfits did was fantastic and their influence on metal/hard rock is difficult to overstate, but some of Danzig's later stuff is phenomenal. Sure, his lyrics tend to be self-congratulatory and often cheesy, but the quality of the vocals truly stands out against the swamp that modern metal has become. Glenn has an ear for melody and harmony that is truly refreshing.

Of course, take this all with a grain of salt since I also think Type O Negative is one of the most underappreciated bands on the scene today.

Re:No big loss

[norsk_hedensk]

i would have to say that life of agony is more underappreciated than type o.

Re:No big loss

[Moses_Gunn]

I'm ashamed to say I don't know much about Life of Agony. Time to look them up and check it out...

I really suffered LP

[ArgieNomad]

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:I really suffered LP

[caluml]

but I really doubt an graduate from Facultad de Ciencias Economicas - Universidad Nacional de Cordoba would read /.

Nope, but I've been there.

Re:I really suffered LP

[ccp]

but I really doubt an graduate from Facultad de Ciencias Economicas - Universidad Nacional de Cordoba would read /.

Y por qué la duda?

Saludos,

Carlos (no graduado en la UNC)

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

[Anonymous Coward]

Nope. He simply wrote down his answer on his slate, exclaimed "Ligget se!" (here it lies!), turned his slate over, and sat there for an hour or so.

Re:reminds me a similar story

[Anonymous Coward]

I don't know where you heard that, but I've heard the particulars of that story in a dozen different varieties. So I wouldn't be so sure (unless you know your source is decent).

Re:reminds me a similar story

[QuantumG]

Jesus man! Did you ever stop to think that he might have been there? You insensitive clod.

Re:reminds me a similar story

[Aphelion]

That would have to have been 50.5 times 100, since 50.5 is halfway between 1 and 101, and 100 is the number of integers in the set.

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:reminds me a similar story

[Anonymous Coward]

So I wouldn't be so sure (unless you know your source is decent).

She wasn't, she didn't have a stitch on while we sat there having a smoke, but I still believe her story.

familiar

[Penguinoflight]

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.

Izzle So sad.

[Anonymous Coward]

Goodbye, dizzy friend.
We hardly knizzew ye.
And we certainly had no idea wizzy you wizzle rapping `bout.

Izzle Damn!

[Anonymous Coward]

At least his killa knew he wasn't spendin'.

R.I.P., Dude.

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.

Re:Leonid Khachiyan

[Anonymous Coward]

First Leonid, now George, and I'm not feeling to well, either.

Re:Leonid Khachiyan

[Anonymous Coward]

I submitted this as news over 2 weeks ago and it
was rejected. Silly Slashdot people

Travelling Salesman Problem

[raga]

Dantzig (with Fulkerson and Johnson) was also the first to publish a TSP algorithm that optimized a 49-city tour. Of course these days, 13k-city solutions are considered par for the course, but back in the 1950's a 49-city tour was a very big deal.

Another thing I'll remember him for is his interesting exercise in urban design Compact City

cheers-raga

Re:Travelling Salesman Problem

[fbjon]

Hm, well a Sweden tour seems to be the largest currently optimised tour at 24,978 cities.

oblig ATHF quote

[bladesjester]

"Can we get the blood to flow, up the walls?"

Re:Yep. He's really gone

[Topmounter]

www.bugmenot.com

Re:Alternative Rock

[Anonymous Coward]

Nothing. Slashdot's "upgrade" is putting comments on the wrong thread on the wrong story, because they can't program any better than they can spell. Editors are now mass-moderating hundreds of comments "Overrated" to hide their fuckup.

Simplex method mature?

[Goonie]

I only studied linear programming at the undergraduate level, but as I understood it simplex implementations have been around for a very long time and have been tweaked to within an inch of their life. Briefly and approximately, are you working an improved simplex implementation, or some new application for linear programming?

Re:Simplex method mature?

[log2.0]

Since I haven't published anything on it I don't want to talk about it :)

Hehe, but I am adpopting the simplex algorithm to make it do something else.

It's 2005 ...

[Anonymous Coward]

Has this been solved yet?

"In retrospect," Dantzig wrote in the 1991 history book, "it is interesting to note that the original problem that started my research is still outstanding -- namely the problem of planning or scheduling dynamically over time, particularly planning dynamically under uncertainty. If such a problem could be successfully solved it could eventually through better planning contribute to the well-being and stability of the world."

Re:It's 2005 ...

[TapeCutter]

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.

Re:It's 2005 ...

[Anonymous Coward]

Just about any practical planning or scheduling problem is NP-hard, so no perfect solution is expected any time soon. There are pretty good solution methods that can work in practice in many cases when the problem is deterministic. However, AFAIK progress in stochastic scheduling and planning problems is much more limited, since the known solution methods tend to require the equivalent computational work of solving a large number of deterministic problems.

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

[Forbman]

They had RADAR, which helped for defence, but offense was substantially more problematic.

Well, too bad they didn't have Patton, or they would not have had problems on offense. *:)

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.

Re:Further clarifier

[wisdom_brewing]

and here youre referring mostly to hard OR as opposed to soft OR (cue the jokes). hard OR is where you have relatively quantifiable values to work with, with soft OR you have much less tangible goals such as "improve morale" as opposed to "schedule trains in such a way as to minimise resource use while using fewer resources" which is common of the hard. the simplex model is used heavily in hard OR but, as you stated, even the point of your post, it is in no way near the sum of Operational Research.

Re:For those of you who don't know anything about

[Anonymous Coward]

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.

What is most interesting about (addition | multiplication | exponential decay | negative numbers | fractions | any_other-math-thingy) 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.

[/sarcasm] The fact that LP is useful outside of CS is totally unsurprising.

the story

[Statman]

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

Re:Oh, now wait a minute...

[hamfactorial]

The question mark!

Re:Oh, now wait a minute...

[mc_barron]

I'm hoping for the "totally fucking batshit insane"...hell, i'd even settle for "mostly underwear-outside-his-pants insane" or even "somewhat claims-he-invented-the-question-mark insane"
...God knows we don't have enough crazy people. :)

Re:For those of you who don't know anything about

[Anonymous Coward]

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 link

[etnoy]

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

Re:Wikipedia link

[Anonymous Coward]

Wikipedia? Shouldn't that be George Gdantsk then?

Not really...

[Kjella]

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

Re:Not really...

[Chuck Messenger]

First of all, you are playing against an opponent, so the optimal strategy will depend on his strategy.

Theoretically not true. In a 2-player game, the optimal strategy is always independant of the opponent's strategy.

Re:Not really...

[cellocgw]

In a 2-player game, the optimal strategy is always independant of the opponent's strategy
Can you elaborate on this? For example, chess masters will pick a defense based on their opponent's choice of offense.
Is there a theoretical line of defense that works regardless of the attack sequence chosen? And if so, why do people select other defenses?

Re:Not really...

[Chuck Messenger]

The optimal move is a function of the current game state. Hence, your optimal move is a function of the cumulative moves you and your opponent make.

Chess is not a "solved" game (and even if it were, only a computer would be able to execute perfect play). Why do people select defences other than the optimal one? Because only near the end of a game can anyone perfectly evaluate all the possible lines of play, and thus be able to choose the optimal move(s).

If both sides play perfectly, then every possible game state is already decided as either White wins, Black wins, or draw. It's even possible that the starting position is a White win (or even, I suppose, tho less likely, a Black win). Most likely, it's a draw. But nobody can say for sure.

Which brings me to my Controversial Thesis: chess is a game of luck. Why? Because whenever you make a move whose consequences you can't fully evaluate (which is generally the case in chess, or any other interesting game), then you are making a blind choice (not necessarily totally blind -- the more skilled you are, the less blind your move is -- but still at least partly blind). Whenever you do that, you are trusting to luck. The move may turn out to be either better or worse than you hoped. In the former case, you're lucky; in the latter, you're unlucky.

I don't expect you to agree with my Controversial Thesis -- I haven't yet found anyone who agrees with me that chess is a game of luck!

Re:Mother

[daemon_mf]

What doesn't Glenn have to do with Pi?? But I guess only a fan would know that... sheesh ;)

Sad to hear...

[GeorgeMcBay]

Not only a great mathematician, but he could really rock out. His song "Mother" will always be a classic.

You're all missing a very important point!

[Seumas]

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

Motheeer! Tell your children not to

[Anonymous Coward]

heal my unsolvable equations!

ntpdate

[Piranhaa]

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?

Re:ntpdate

[Anonymous Coward]

You think 10 days is bad? Wait until the /. editors find out about it and post a dupe a week from now!

From the FWIW department...

[Spock the Baptist]

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.

Re:From the FWIW department...

[pahles]

Talking about mathematics:

...a couple of three fellow students...

couple = two
three = three

ergo: two = three

Re:From the FWIW department...

[Anonymous Coward]

...a couple of three fellow students...

hmm that would make six actually since its two units of three.

Re:From the FWIW department...

[mforbes]

I read it this way:

...a couple of three fellow students...

A couple = 2
The word "of" indicates that the expressions on either side of it should be multiplied.
three = 3

Therefore: 2 x 3 = 6.

Re:From the FWIW department...

[plumby]

No. It's two of the three fellow students, surely.

I really can't believe I'm posting this. There must be some work that I should be doing...

Stupid (but useful) Knight Ridder trick

[Jayfar]

No login needed, just a quick edit of the url.

http://www.mercurynews.com/mld/mercurynews/news/lo cal/states/california/the_valley/11665968.htm

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

http://www.macon.com/mld/mercurynews/11665968.htm

The Macon Telgraph doesn't require registration yet; all KR papers share article number namespace.

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

Yes you can.

[orlanz]

You can approximate a non-linear system using multiple linear prices. You might have A*x1^3+B*x2^2+SUM(KiXi). But the A and B terms can be broken down to multiple linear lines so that Ax1^3 = SUM(Aj*x1j) and Bx2^2 = SUM(Bj*x2j). It wouldn't be too hard because you are dealing with integers. You can't have half a unit, you got one fighting or not.

Anyway, that could become too complex. You would probably have a simple dummied down approach. Although the answer is optimized for the simple problem, it will give you much insight into the input parameters that you can use in your overall strategy (like there is a really high chance I will win this battle with half my troops...). It would definetly give you a major leg up against a human opp who needs to what you do AND what the program is doing.

i liked him the most in the misfits...

[Anonymous Coward]

because he'd sing about killing babies and raping mothers. funny shit, y'all. he'll be missed.

Re:Yep. He's really gone

[caluml]

Did you miss the "George Dantzig, 1914-2005" title?

I'll never get to do this again!

[triskaidekaphile]

I better post this now since there will probably never be another opportunity to post this and still be ON TOPIC!

My Master's thesis compared Simplex Method algorithms. I can almost remember the many nights I fell asleep (quickly) reading the research material.

I'm an English major, you insensitive clod!

[Anonymous Coward]

To-morrow, n to-morrow, n to-morrow,
Creeps in this P-E-Double-Tizzy pizzle fizzle day ta day
To tha last syllable of recorded time,
And all our yesterdays have lighted fools
The way ta dusty death. Out, out, brief candle!
Life's but a rhymin' shadow, a poor gangsta
That struts n frets his hizzle upon tha stage
And tizzle is heard no more: it is a tale
Told by an idiot, F-to-tha-izzull of sound n fury,
Signify'n mobbin'.

Simplex on Star Wars seats

[solomonrex]

Simplex says turn around. Simplex says go out the door. Simplex says make a right. Simplex says walk to next door. Simplex says go through door. Simplex says sit in middle. Simplex says enjoy Hitchhiker's Guide.

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.

Damn

[killtherat]

I've actually been spending the past few weeks trying to figure out how to apply Dantzig-Wolfe decomposition to one of my optimization problems. I usually feel pretty smart, but once I start reading papers about this stuff, I get the distinct feeling that I may actually be very,very stupid.

Danzig's Black Aria II coming soon

[KlomDark]

But Glenn Danzig will continue on with Black Aria II:

The follow up to 1993's "Black Aria" which reached the #1 position on Billboard's Classical chart.

"Black Aria II" focuses on Lilith, a mythical figure and Eve's predecessor as the first wife of Adam who has come to symbolize female independence and rebellion. It is said that Lilith was banished to the desert, had sex with demons, brought plagues to the Earth, and, taking on the form of a serpent, seduced Eve to eat the fateful apple. "Black Aria II" was produced by Danzig. An early summer 2005 release on Danzig's Evilive label is expected.

You'll either really love it, or really hate it. There doesn't seem to be any in-between.

"This record has no failings; the reason some people are disappointed in it is because of something they lack, not because Black Aria lacks anything. So be aware that this album is a test, a test for the existence of a soul. If you possess a soul, you will find that this recording will give it new wings. If you lack a soul, you will find that this recording will cast you down into the pit, never to rise again. You have been warned."

"A Soundtrack to Last War On Earth?"

"If you have been searching for the perfect ritual musick, look into this one. Here is an exceptional work which will effectively aid to bring many successful Magical operations. The cover is graced by an incubus demon, & an angel in romantic rapport. To listen & absorb this etherial & carnal opus is to trancend the earth plane, & sail across the heavenly spheres. One is taken deep into the cavernous wombs of the earth, & to the highest mountaintops, even unto the very depths of the soul. This is sonic darkness..."

"That's the weird paradox I feel when I listen to Black Aria-I don't like it and it's not long enough."

"If you are familiar with Glenn Danzigs prior work then this will become a bit of a shock for you. This album is purely instrumental with some background female vocals that are truly moving. I would not classify it as Rock, but Ambient. This is truly a beautiful piece of art that he has put together with this album. I had a very hard time finding it because there were only a limited number of them released the first time, I was ecstatic to find that it had been re-released."

"One of the greatest cds ever recorded"

"Danzig at his best!"

"This is Not Typical Danzig - It's Better!"

http://www.amazon.com/gp/product/customer-reviews/ B00004NKGH/

Then again, other people say:

"Easily the worst cd of all time"

"Total rubbish!"

Oops, wrong Dantzig guy... Sorry.

Re:Danzig's Black Aria II coming soon

[Anonymous Coward]

Thank you for that most original and never-before-done reference in this thread. You truly are a tulip of creativity among a sea of doo-doos.

Damn! you beat me to it!

[elrous0]

You've got to be quick on /. I was almost to the bottom too and thought I would be the first.

-Eric

Re:Yep. He's really gone

[Rufus88]

He figured it was just a prediction. The year is still young.

Re:Mother

[Rufus88]

Yes. The rest of us were wondering what George Dantzig has to do with Pi.

Simplex says ...

[operagost]

Simplex has pretty crappy taste in movies.

So this is the guy...

[suitepotato]

I heard this story about the "unsolvable" problem mistakenly done as homework from my junior year algebra teacher in high school and wished I could get something like that to happen but all he ever put on the board was a series of quadratic equations that no one in class noticed were linked by variables and values. We ended up piecemeal solving a problem for him for his brush-up night course at university. RIP...

Re:Karma-whoring clarifier X2

[Kiryat Malachi]

The statement was more in regard to the fact that the "programming" in linear programming does not refer to computer programming, but to an obscure/obsolete military usage of the term.

Of course you can use computers to perform LP. Then again, you can use computers to play chess as well, and no one would dispute that chess has little to do with computing.

Independent tech news missing from U.S.

[SgtChaireBourne]

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

Non-tech stuff, yes. It's still rather good.

ICT issues? Not anymore.

Not since Slate (created to take out Salon) has taken over content in that area. But that's not alone, Chairman Bill's foundation dumps many hundreds of thousands of dollars on NPR each year. Probably those 'donations' have strings attached if places like India, Australia show us anything.

Re:Karma-whoring clarifier X2

[Pollardito]

Excel is probably the most powerful, robust, versatile, used for everything and the kitchen sink, program ever created.

be careful saying this on Slashdot, you're likely to get skewered by the Emacs fanboys

I'm skeptical...

[davew2040]

Not that it matters to anyone but me, but I really don't see how a student can be so out of touch with coursework that they could solve unsolvable problems and not realize that they were a bit tougher than usual.

Maybe it was the course's first homework, but I suspect he just thought it would be a funny way to stroke his own ego.

I don't need simplex to find the best seat

[wsanders]

Find min(R) where R is the distance from the center of the theatre. KISS is my co-pilot.

I retract that comment

[wsanders]

.. I forgot that there are contraints on the problem - no climbing over seat and spilling your drinks on people. You could formulate it as an LP, then, maybe with each variable as a row in the theatre. Have to dif out my old textbooks . . .

Same here.

[renehollan]

While an undergrad, and later in grad school, I knew this short (I am short at 5'7", but he was shorter, about 5'2"), Vietnamese fellow, who spoke in halting English. He was scary brilliant.

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:Karma-whoring clarifier X3

[Anonymous Coward]

*cough* I have a hammer *cough* I see a nail.

Yes you can do things like databases in a spreadsheet. But you are not playing to its strengths. Just as you can do things like spreadsheets in a database. Again though you are not playing to its stengths.

Use the right tool for the right job.

For large blobs of data that need a relationship between them a database is it. For things like acounting type things excel is it...

I have setup acounting type systems in a database and it is a real drag. What would take about 10 mins to setup in excel takes several days of work in a db. On the inverse I have done db like things in excel and it is a real drag. What is like 10 mins of work in a db takes quite a bit of time to do in a spreadsheet.

Re:Mother

[cloudmaster]

You forgot to italicise Dantzig, which is not the same as Danzig. HTH.

So what were those two problems already?

[J.R. Random]

Unfortunately the two links don't tell us what those uberhard problems were. Anybody know?

Kudos

[Crazy Eight]

That is the funniest one-liner I've read here all year.

wavelet decomposition

[Dr.Ruud]

Simplex is also used for wavelet decomposition.