Analysis of Linear Programs By Sequential Projection

We apply what we call sequential projection to reformulate a block triangular linear program as a recursive optimization problem. We approximate the return function at each stage of the recursion by using either inner or outer linearization, and iteratively refine the approximation until the original linear program has been solved Special cases of methods in this class are, for example, the nested decomposition methods of Glassey and Ho-Manne, Dantzig-Wolfe decomposition, and the tangential approximation approach of Geoffrion. Special computational benefits accrue upon applying our approach to Dantzig‘s Leontief substitution model.