van Slyke, R. M.; Wets, Roger L-shaped linear programs with applications to optimal control and stochastic programming. (English) Zbl 0197.45602 SIAM J. Appl. Math. 17, 638-663 (1969). 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 Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 323 Documents MSC: 90C05 Linear programming 90C15 Stochastic programming 49-XX Calculus of variations and optimal control; optimization Keywords:L-shaped linear programs; application to stochastic programming; application to discrete optimal control problems with state space constraints PDFBibTeX XMLCite \textit{R. M. van Slyke} and \textit{R. Wets}, SIAM J. Appl. Math. 17, 638--663 (1969; Zbl 0197.45602) Full Text: DOI