Among my friends and associates, we have a varied group of heroes we follow, so much so that confusion sometimes occurs. For example, a while back I mentioned to my colleague Hal Tolley, “I love Patterson’s work.” He asked, “the powerlifter?” I responded, “No the father of integrated computer architecture that won the 2017 Turing Award (the Noble Prize for computer science).” He then said, “yeah, he’s the powerlifter.” I looked into it and sure enough, Patterson was a powerlifter, a rare thing among elite computer scientists. When I came to think about it, Hal’s characterization made sense. After all, how many Turing Award winners have ever been competitive powerlifters? After my search, I found only one—David Patterson.
Those of you who know me well know that I listen to a lot of Heavy Metal and this came into the names used for my servers. For example, when I worked at the world’s largest investment manager, the most powerful server that was largely for me and my small group was called “Pantera.” So it’s only logical when I mention “Dantzig” that people think I mean Danzig, but I assure you that while Mother is still on my favorites, Glenn Danzig is not one of my heroes, but George Dantzig is. So, who is George Dantzig, and how does he relate to the DARQ Art of Optimization? In my view, he is one of the greatest applied mathematical Wizards of all time and the father of modern optimization.
The Real Will Hunting
Matt Damon and Ben Affleck, otherwise known as Jason Bourne and Batman were introduced to the world in an amazing movie that they co-write about a mathematical genius who was a guy that you’d get a beer with. While this guy did construction work and worked as a janitor, he solved the world’s hardest math problems simply because he could. The real man that inspired that Oscar-winning story was my hero George Dantzig, the father of modern optimization. Dantzig really did solve two unsolvable applied math problems, not because he was sweeping the floor, but rather because he mistook them for homework. After his Ph.D. at Berkeley, he stayed “out West” like Good Will Hunting and founded the legendary artificial intelligence group at Stanford called the Systems Optimization Laboratory or SOL. I followed him from when I was an undergrad and used his group’s program MINOS when I was at Columbia. Dantzig was and still is one of my heroes.
George Bernard Dantzig was the son of two linguists, his father having studied mathematics under the famous French mathematician Henri Poincare. George never put himself above anyone but was always willing to just work like his father Tobias, who worked as a lumberjack, road worker, and house painter in Oregon after the family emigrated to the United States. Eventually, Tobias returned to academia just as his son did after a stint in the military and some time at the Pentagon. It was in academia that my dad met George Dantzig, a natural occurrence because my father was an undergrad at Stanford who went on to receive his Ph.D. at nearby UC Berkeley. At Berkeley my dad studied optimization applying it to transportation, using Dantzig’s DARQ discipline to help determine the “optimal placement of gas stations,” using good old Santa Clara County (a.ka. Silicon Valley) as his calibration model. My dad’s Berkeley dissertation then became the model used for years by petroleum companies in North America for locating gas stations. Relatedly, I grew up hearing stories of great applied mathematicians like George Dantzig that made all that possible (think of that next time you do a pit stop on the highway and find a gas station exactly where you need it).
Solving the Unsolvable Problem
Dantzig started his Ph.D. and then took a leave of absence when WWII hit. He had family back in Poland and that inevitably inspired him, like Captain America, to fight the Nazis. While not getting the super solider serum, within no time Dantzig made an equivalent contribution to Cap by was serving as the head of the combat analysis for the Army Air Forces. It was also in WWII, that Dantzig encountered additional unsolvable problems that we needed to solve to help us push humanity forward. He described the mathematics of such “unsolvable problems” as being similar to assigning people to jobs in the Air Force., using the simple example of taking 70 people that needed to be optimally assigned to 70 jobs, pointing out that there were 70! (70 factorial) possible solutions to this relatively easy to state problem. When he said this, he found that most didn’t grasp how big this number 70! was because normal people don’t think in mathematical terms, so he came up with a simple explanation that everyone could understand, similar to Feynman’s description of why the Challenger exploded by dropping an O-ring into a glass of ice water.
Dantzig pointed out that even if the entire Earth were filled with super-computers that could make 1 billion complete calculations per second, it would take trillions and trillions and trillions (10040 ) of such “calculator planets” working from the Big Bang until the sun runs cold to attempt to do the calculation. In other words, calculating 70! combinations are “intractable” or unsolvable. When one can’t solve such a problem by brute force, Dantzig knew that unsolvable problems just have to be reformulated into solvable pieces. In order to do this Dantzig determined to use a computer properly.
The Proper Use of a Computer—Axiomatization and the Birth of Linear Programming
Dantzig understood the proper use of a computer, taking a lesson from the father of the modern computer John von Neumann (he also did some pretty interesting economics work, in addition to numerous other areas). Von Neumann said for a computer to be used “intelligently” (yes, this is related to artificial intelligence), that a model must be formulated, and good algorithms developed. While building a model might seem simple enough, building a valid model requires the “axiomatization” of a subject matter area. Axiomatization is a very difficult thing, essentially breaking down knowledge into fundamental mathematical statements, something that von Neumann noted required rare individuals with “the background and tastes of a mathematician or logician.” Luckily for all of us, the real Good Will Hunting was just such a person. It’s best that I have Dantzig describe what he did next:
“By mid-1947, I had formulated a model which satisfactorily represented the technological relations usually encountered in practice. I decided that ad hoc ground rules had to be discarded and replaced by an explicit objective function. I formulated the planning problem in mathematical terms using a set of axioms. The axioms concerned the relations between two kinds of sets: the first was the set of items being produced or consumed and the second, the set of activities or production processes in which these items would be inputted or outputted in fixed proportions providing these proportions were non-negative multiples of each other. The resulting system to be solved was the minimization of a linear form subject to linear equations and inequalities. The use (at the time it was proposed) of a linear form as the objective function to be extremized was a novel feature of the model.”
The Real Use of that Unsolvable Homework Problem
Once Dantzig formulated the problem, he went to numerous individuals that he thought could solve it, in particular, economists because they had written about such matters. These were not just any economists, but guys who eventually won the Nobel Prize. Just like Socrates when he searched Athens for the wisest man, Dantzig found that none of the old wise men of economics or even mathematics could solve his problem and after his search, he realized that he was the person that he was searching for. Luckily, the “particular geometry” involved one of the unsolvable problems he solved as homework proved to be exactly what he needed. It was this math formulation that allowed him to gain insight that his particular algorithm, called the simplex method, would be an efficient solution technique.
With his solution, Dantzig went to the mountain to confirm the results with no less than John von Neumann himself. As Dantzig wrote down a geometric and algebraic formation of the problem, Von Neumann immediately responded that he’d been working on the same thing. In short, he got the approval and support of one of the greatest minds in the world and the rest is history. So was born the discipline of Linear Programming or the first step of the DARQ Art known as “Optimization.”
Clarification of a Few Terms
The term linear programming comes from the fact that Air Force plans or proposed schedules of training, logistical supply, or combat deployment (all things that optimization is used for today) were called “programs.” This term was used in the military long before strings of computer code became known as programs. When Dantzig studied these programs and found that they could be formulated as a system of linear inequalities, he called it Programming in a Linear Structure. The Nobel Prize-winning economist T.C. Koopmans suggested shortening the name to linear programming. As far as Dantzig’s simplex algorithm, it was named by the Israeli-American mathematician Theodore Motzkin who noted that Dantzig’s method could be described geometrically as moving from one simplex to another.