Video Excerpt

IRV
How did you get involved with Project Scoop?

Barankin did something really lovely for me: he contacted George Dantzig at the Pentagon and got me a job there for the summer. I went to Washington, met George, met the group of people at Project Scoop (Scientific Computation of Optimum Programs) under the air force, and I worked there all summer.

George handed me a partially solved problem of trying to straighten out an algorithm for handling a problem with degeneracy in the simplex method. Degeneracy is when you have a lot of zeros on the right hand side and it has a theoretical possibility of cycling, when you use the simplex method, and never terminating.

IRV
We've talked with Alan Hoffman about this. At the time, nobody knew that the simplex method would work, because there was a concern that it could go on forever. The problem Dantzig gave to Alan Hoffman was, "Is it possible that this could happen?" The question he was asking you was, "If it could happen, what could we do about it?"

PHIL
Alan answered the first question beautifully by presenting us with an example in which the simplex method would, indeed, cycle along without ever coming to a stop.

My angle was to read what little had been written about it. Harvey Edmonton, a student of Dantzig's, wrote a paper that proposed a certain kind of perturbation on the righthand side involving polynomials with epsilons in them that was theoretically promising.

From my study of logic, I rephrased this argument in a very crisp, mathematical form using what is now known as lexicographic ordering of the elements of the simplex method. That put this proposal on a firm footing and provided the method that would make the simplex method secure. If you use this procedure, it would terminate after a finite number of iterations.

That was a great summer! In 1951, Hoffman and I settled both ends of this issue. We've kept up a friendship ever since then.

Previous

Next