Orateur
Description
This work proposes a globally converging cutting-plane algorithm for solving stochastic mixed-integer programs (SMIP) with general mixed-integer state variables. We show that Lagrangian cuts can approximate the convex envelope of the value function. To approximate the nonconvex value function to exactness, we need to iteratively add binary state variables and generate Lagrangian cuts on the lifted state space. We demonstrate that this lift-and-cut procedure converges to the global optimum asymptotically. However, we show that vanilla Lagrangian cuts can be steep and lead to a poor lower approximation. We propose enhanced Lagrangian cuts, which strengthen the vanilla Lagrangian cut and yield good geometric properties. Extensive computational experiments on the generation expansion planning and security-constrained unit commitment problem demonstrate the effectiveness of our proposed methodology in solving large-scale, multistage stochastic mixed-integer optimization problems.
