Linear programming is a fundamental course in every operations research curriculum. The implication of including a course on linear models at the core of our discipline is that linearity is realistic for many applications. Bill Cook addresses this big assumption in his book In Pursuit of the Traveling Salesman, which features an important moment in operations research history at the University of Wisconsin-Madison.
News of the general linear-programming model, and the simplex algorithm for its solution, was delivered by George Dantzig in 1948 at a meeting held at the University of Wisconsin. The event was a defining moment for Dantzig, who has described often its proceedings. Like many good stories, repeated telling may have shifted a few details over the years, but all versions capture the spirit of a nervous rising star facing a large and distinguished group of mathematicians and economists. During the discussion following Dantzig’s lecture, Harold Hotelling, great in both academic stature and physical size, rose from his seat, stated simply, “But we all know the world is nonlinear,” and sat down. Dantzig was lost for a reply to such a sweeping criticism.
Suddenly another hand in the audience was raised. It was John von Neumann. “Mr. Chairman, Mr. Chairman,” he said, “if the speaker does not mind, I would like to reply for him.” Naturally I agreed. von Neumann said: “The speaker titled his talk ‘linear programming’ and carefully stated his axioms. If you have an application that satisfies the axioms, well use it. If it does not, then don’t.”
Fortunately for the world, many of its complexities can in fact be described in sufficient detail by linear models. The episode with Dantzig, Hotelling, and John von Neumann is summed up nicely by a cartoon Dantzig’s colleagues reported as hanging outside his office. It featured the Peanuts character Linus in his traditional pose, sucking his thumb and holding a blanket. The caption read, “Happiness is assuming the world is linear.”
HT to Jeff Linderoth for reminding me to blog about this.
April 29th, 2014 at 12:58 pm
Oh to be in that room with Dantzig and Neumann et al
April 29th, 2014 at 1:08 pm
It’s easy to say, “Use linear methods if your application fits the assumptions.”
It’s harder when everyone on your team initially believes that your application fits linear assumptions, but then in the course of developing something, you discover that the application is not really linear.
November 18th, 2016 at 5:37 pm
If Dantzig were answering that question today he might say that discrete and nonlinear optimization models are used extensively, but that linear programming remains worthy of emphasis because it is the foundation upon which many more complex optimization methods are built.
And if you are planning an operations research curriculum today you might consider an Introduction to Optimization that only starts with LP, rather than an Introduction to Linear Programming that focuses on LP. It’s when you drag out linear programming for a whole semester that the assumption of linearity becomes such an issue.