Chance-constrained set covering with Wasserstein ambiguity
Chance-constrained set covering with Wasserstein ambiguity
复制标题
DOI：
10.1007/s10107-022-01788-6
复制
发表时间：
2020-10
影响因子：
2.7
通讯作者：
Haoming Shen;Ruiwei Jiang
中科院分区：
文献类型：
--
作者：
Haoming Shen;Ruiwei Jiang
研究了一类具有Wasserstein模糊集的广义分布鲁棒机会约束集覆盖问题（DRC），其中决策和不确定性均为二值。我们建立了DRC的np -硬度，并将其重构为两阶段随机规划，从而简化了分解算法。进一步，我们导出了两类有效不等式。第一个家族的目标是一个“移位”的子模函数的下位图，它与两阶段重构的每个场景相关联。我们证明了有效不等式完整地描述了形图的凸包。第二个家庭混合了多种情况下的不平等，并通过提升获得进一步的力量。我们的数值实验证明了DRC模型的样本外性能以及我们提出的重新表述和有效不等式的有效性。
We study a generalized distributionally robust chance-constrained set covering problem (DRC) with a Wasserstein ambiguity set, where both decisions and uncertainty are binary-valued. We establish the NP-hardness of DRC and recast it as a two-stage stochastic program, which facilitates decomposition algorithms. Furthermore, we derive two families of valid inequalities. The first family targets the hypograph of a “shifted” submodular function, which is associated with each scenario of the two-stage reformulation. We show that the valid inequalities give a complete description of the convex hull of the hypograph. The second family mixes inequalities across multiple scenarios and gains further strength via lifting. Our numerical experiments demonstrate the out-of-sample performance of the DRC model and the effectiveness of our proposed reformulation and valid inequalities.