Globally Converging Algorithm for Multistage Stochastic Mixed-Integer Programs via Enhanced Lagrangian Cuts

This paper proposes a globally converging cutting-plane algorithm for solving multistage stochastic mixed-integer programs with general mixed-integer state variables. We demonstrate the generation process of Lagrangian cuts and show that Lagrangian cuts capture the convex envelope of value functions on a restricted region. To approximate nonconvex value functions to exactness, we propose to iteratively add binary state variables and generate Lagrangian cuts on the lifted state space. This lift-and-cut procedure converges to the global optimum with probability one. We further propose two types of enhanced Lagrangian cuts, Pareto-optimal Lagrangian cuts and square minimization cuts, to improve the computational performance of vanilla Lagrangian cuts. Extensive computational experiments on the generation expansion planning and stochastic unit commitment problems demonstrate the effectiveness and efficiency of our proposed methodology in solving large-scale, multistage stochastic mixed-integer programs.

Article

Download

View PDF