ALAN: Alan Hoffman
IRV: Irvin Lustig
IRV
Can you give us an example of what kind of work you were doing?
ALAN
There were certain models that they were working on, for example, building a certain number of air force wings over a period of time while considering the requirements for purchasing and training. George gave me the Activity Analysis and Allocation book to read, so I did. He wanted to discuss the question of degeneracy.
He said that the proof that the simplex method worked depended on the assumption of non-degeneracy. It's analogous to this situation: you're looking at a polyhedron in space, generally you would expect that a vertex of that polyhedron would be the intersection of three planes. But it might be the intersection of four or more planes. By accident, more than three planes might have come together to generate the vertex. And if you look at the algebraic analog of that situation, it might lead to the possibility that the simplex method, which George had developed, would not work. It might cycle. You might repeat yourself. George and other folks had developed devices to prevent these occurring cycles, but they didn't know whether they were necessary. So he posed the question to me, could it happen? I worked on it for a couple weeks and eventually I found an argument that showed it could.
IRV
So, the significance of this work is that while the simplex method existed, it wasn't clear that it would work and that it would ever actually terminate?
ALAN
Theoretically, yes. I showed that cycling could occur. I found the first example, then other people found more.
IRV
Were there lines of study at that time that didn't work?
ALAN
Well, in terms of mathematics, almost nothing works. It's one of the secrets of the profession; mathematicians live with constant failure. Ninety-eight percent of what you try fails. So, were there lines that didn't work out? Oh, countless!
IRV
The work you did on the simplex method and cycling has been written about, hasn't it?
ALAN
Yes. Actually, I didn't really think much about it, but a few years afterwards, people asked me to write about it. I wrote a report; it's in Saul Gass's book, George's book, and others, but I think Jon Lee's piece in the Siam Journal is the best representation of what my mental processes were at the time.
|