Orateur
Description
Multistage stochastic mixed-integer programming (MS-MIP) is a powerful framework for sequential decision-making under uncertainty, yet its computational complexity poses significant challenges. This paper presents a convergent cutting-plane algorithm for solving MS-MIP with binary state variables. Our method exploits a geometric interpretation of the convex envelope of value functions and the convex hull of feasible regions. By employing the cutting-plane tree algorithm, we iteratively refine LP relaxations using multi-term disjunctive cuts (MDCs) and generate Benders’ cut to construct precise approximations of the value functions, eliminating the need for solving MIP subproblems to generate tight cuts. A key theoretical contribution of this work is proving the finite convergence of our proposed algorithm. Through a toy example, we provide a clear illustration to demonstrate how MDCs strengthen LP relaxation. However, we also highlight the drawbacks of MDCs, such as their adverse impact on overall computational performance due to the increased problem size and complexity. To address this issue, we propose an improved strategy that balances the trade-off between cut strength and computational efficiency, ensuring the practical applicability of the approach. Computational experiments on generation expansion planning validate its efficiency and scalability in solving large-scale MS-MIP problems.
