PHIL: Phil Wolfe
IRV: Irvin Lustig
IRV
What's the story behind the decomposition algorithm?
PHIL
George would often call me in and talk about something on his mind. One day in around 1959, he told me about a couple of problem areas: something that Ray Fulkerson worked on, something else whose details I forget.
In both cases, he was using a linear programming model and the simplex method on a problem that had a tremendous amount of data. Dantzig in one case, Fulkerson in another, had devised an ad hoc method of creating the data at the moment it was needed to fit into the problem.
I reflected on this problem for quite awhile. And then it suddenly occurred to me that they were all doing the same thing! They were essentially solving a linear programming problem whose data - whose columns - being an important part of the data, were too many to write down. But you could devise a procedure for creating one when you needed it, and creating one that the simplex method would choose to work with at that moment.
Call it the column-generation method. The immediate, lovely looking application was to the linear programming problem, in which you have a number of linear programming problems connected only by a small number of constraints. That fit in beautifully with the pattern. It was a way of decomposing such a problem. So we referred to it as the decomposition algorithm. And that rapidly became very famous.
|