×

L-shaped linear programs with applications to optimal control and stochastic programming. (English) Zbl 0197.45602

L-shaped linear programs are structured linear programs of the form:
\[ \begin{gathered}\text{Minimize }z = \underline{c}^1\underline{x} + \underline{c}^2\underline{y} \\ \text{subject to }\underline{A}^{11}\underline{x} = \underline{b}^1, \underline{A}^{21}\underline{x} + \underline{A}^{22}\underline{y}= \underline{b}^2,\ \underline{x}\ge 0,\ \underline{y}\ge 0. \end{gathered} \]
An algorithm is suggested which is essentially equivalent to the partition procedure of J. F. Benders although it can also be looked at (as is done here) as a dual of the decomposition method of Dantzig and Wolfe. The method is applied to discrete optimal control problems with state space constraints where the first set of constraints corresponds to the problem without state space constraints and the second set of equations corresponds to the state space constraints. Two stage stochastic linear programs with random right hand sides can also be solved by the algorithm. The results of Dantzig and Madansky for the same problem are generalized.
Reviewer: R. M. van Slyke

MSC:

90C05 Linear programming
90C15 Stochastic programming
49-XX Calculus of variations and optimal control; optimization
PDFBibTeX XMLCite
Full Text: DOI