Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets
Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets
复制标题
DOI：
10.1007/s10107-020-01580-4
复制
发表时间：
2020-02
影响因子：
2.7
通讯作者：
Xian Yu;Siqian Shen
中科院分区：
文献类型：
--
作者：
Xian Yu;Siqian Shen
研究了内生不确定性下的多阶段分布鲁棒混合整数规划，其中阶段不确定性的概率分布取决于前一阶段的决策。我们首先考虑由不确定参数的第一阶矩和第二阶矩的决策依赖界和分别由与决策依赖经验矩阵完全匹配的均值和协方差矩阵定义的两个模糊集。对于这两个集合，我们证明了每个阶段的子问题可以被重铸为一个混合整数线性规划（MILP）。此外，我们将Delage和Ye （Oper Res 58(3): 595-612, 2010）中的一般基于矩的模糊集扩展到多阶段决策依赖设置，并推导了阶段子问题的混合整数半确定规划（MISDP）重新表述。我们开发了获得多级misdp最优目标值的下界和上界的方法，并使用一系列milp来近似它们。采用随机对偶动态整数规划（SDDiP）方法求解具有风险中性或风险厌恶目标函数的三种模糊集下的问题，并对不同参数和不确定性设置下不同规模的多级设施选址实例进行了数值研究。我们的研究结果表明，SDDiP在前两个模糊集下快速找到中等规模实例的最优解，并且在第三个模糊集下推导出的多阶段misdp也找到了很好的近似边界。我们还证明了在多阶段决策过程中纳入决策依赖的分配歧义的有效性。
We study multistage distributionally robust mixed-integer programs under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We first consider two ambiguity sets defined by decision-dependent bounds on the first and second moments of uncertain parameters and by mean and covariance matrix that exactly match decision-dependent empirical ones, respectively. For both sets, we show that the subproblem in each stage can be recast as a mixed-integer linear program (MILP). Moreover, we extend the general moment-based ambiguity set in Delage and Ye (Oper Res 58(3):595–612, 2010) to the multistage decision-dependent setting, and derive mixed-integer semidefinite programming (MISDP) reformulations of stage-wise subproblems. We develop methods for attaining lower and upper bounds of the optimal objective value of the multistage MISDPs, and approximate them using a series of MILPs. We deploy the Stochastic Dual Dynamic integer Programming (SDDiP) method for solving the problem under the three ambiguity sets with risk-neutral or risk-averse objective functions, and conduct numerical studies on multistage facility-location instances having diverse sizes under different parameter and uncertainty settings. Our results show that the SDDiP quickly finds optimal solutions for moderate-sized instances under the first two ambiguity sets, and also finds good approximate bounds for the multistage MISDPs derived under the third ambiguity set. We also demonstrate the efficacy of incorporating decision-dependent distributional ambiguity in multistage decision-making processes.