kuniga.me > NP-Incompleteness > The Simplex Algorithm

The Simplex Algorithm

30 Jul 2010

George Dantzig (1914-2005) can be considered the father of linear programming, since he invented the simplex algorithm, the first algorithm for solving linear programs. In its worst case, the simplex algorithm has exponential complexity as a function of the input size, and polynomial algorithms have been developed to solve linear programs, such as the interior-point method.

In practice, however, the simplex algorithm performs very well. Furthermore, it possesses characteristics that make it ideal for branch-and-bound algorithms, which are used to solve integer linear programs.

Solving open problems

Legend has it that Dantzig once arrived late for his first day of statistics class at Berkeley University. When he arrived, he saw two problems written on the board and, thinking they were homework assignments, wrote them down in his notebook.

After a few days, he handed the exercises to the professor and apologized for taking so long to solve them, as they were more difficult than usual. The professor didn’t seem to care much at the time, but later revealed to Dantzig that he had solved two open-ended problems in statistics.

Good Will Hunting

The movie Good Will Hunting was inspired by this story. For those who haven’t seen it or don’t remember, Will Hunting was a university janitor, a troublemaker with a criminal record, and a mathematical genius. One day, professors were discussing a theorem on a blackboard, and after leaving, they left the theorem’s statement written down.

The next day, the theorem is solved by an anonymous author. Later, they discover it was the janitor, and the film unfolds with the professors trying to convince Hunting to study mathematics and seek a psychologist to curb his impulses. It’s a movie I really enjoyed and recommend.

Nobel Prize

In 1975, economists Tjalling Koopmans and Leonid Kantorovich were awarded the Nobel Prize for their theory of optimal allocation of resources, which was essentially linear programming. Unjustly, Dantzig was not awarded the prize.

Notes

This is a review and translation done in 2025 of my original post in Portuguese: George Dantzig e o Algoritmo Simplex from 2010. I omitted the part about Integer Linear Programming constraints as it didn’t fit the title.