A Converging Benders’ Decomposition Algorithm for Two-Stage Mixed-Integer Recourse Models
提出一种新的最优性割族，能充分逼近两阶段随机混合整数规划的第二阶段期望成本函数，从而保证算法收敛到全局最优解，适用于两阶段均含混合整数变量且数据随机的场景。
Novel Optimality Cuts for Two-Stage Stochastic Mixed-Integer Programs The applicability and use of two-stage stochastic mixed-integer programs is well-established, thus calling for efficient decomposition algorithms to solve them. Such algorithms typically rely on optimality cuts to approximate the expected second stage cost function from below. In “A Converging Benders’ Decomposition Algorithm for Mixed-Integer Recourse Models,” van der Laan and Romeijnders derive a new family of optimality cuts that is sufficiently rich to identify the optimal solution of two-stage stochastic mixed-integer programs in general. That is, general mixed-integer decision variables are allowed in both stages, and all data elements are allowed to be random. Moreover, these new optimality cuts require computations that decompose by scenario, and thus, they can be computed efficiently. Van der Laan and Romeijnders demonstrate the potential of their approach on a range of problem instances, including the DCAP instances from SIPLIB.