A property of certain multistage linear programs and some applications

In this paper, we present a property of certain linear multistage problems. To solve them, a method which takes this property into account is presented. It requires the resolution of 2N–1 subproblems, if there areN stages in the original problem. A sufficient condition is given on the matrix of the constraints for the property to be true. When only a submatrix has this property, we propose to use the Dantzig-Wolfe decomposition principle. We then can solve the subproblem with the proposed method. Applications to linear and nonlinear programming are presented.This work was done while the author was Visiting Scholar at the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, California.