We consider Benders decomposition algorithms for multistage stochastic mixed-integer programs (SMIPs) with general mixed-integer decision variables at every node in the scenario tree. We derive a hierarchy of convex polyhedral lower bounds for the value functions and expected cost to-go functions in multistage SMIPs using affine parametric cutting planes in extended spaces for the feasible regions in the problem. We improve this hierarchy of convex polyhedral lower bounds using so-called scaled cuts, and moreover we construct a scaled-cut decomposition algorithm that iteratively improves the convex polyhedral lower bounds of the expected cost to-go functions at every node of the scenario tree in such a way that the first-stage lower bound converges uniformly to the convex envelope of the first-stage expected cost to-go function. This is the best convex polyhedral lower bound possible. Our main convergence result depends on novel results for scaled cuts of expectations over lower semi-continuous value functions, and on the analysis of so-called delta-exact scaled cuts.
Article
View Benders decomposition with scaled cuts for multistage stochastic mixed-integer programs