Bounds in multistage linear stochastic programming (Q467481)

The authors aim at generalizations of bounds developed for two-stage stochastic linear programming to scenario-based multistage stochastic linear programs. The starting points are the well-known convexity based Jensen and Edmundson-Madansky bounds and the value of stochastic solutions and their extensions, followed by heuristic bounds based on deterministic skeleton solutions, and several rolling horizon variants. Chains of inequalities among the proposed lower and upper bounds for the optimal value are provided and illustrated for a multistage single-sink transportation problem.