论文标题
与Wasserstein歧义的机会约束套装
Chance-Constrained Set Covering with Wasserstein Ambiguity
论文作者
论文摘要
我们研究了具有沃斯坦（Wasserstein）歧义集的广义分布稳健的机会约束套装问题（DRC），其中决策和不确定性都是二元评估的。我们建立了DRC的NP硬度，并将其重塑为一个两阶段的随机程序，从而促进分解算法。此外，我们得出了两个有效不平等的家族。第一个家庭的目标是“转移”的suppodull功能的射合仪，这与两阶段重新印象的每种情况有关。我们表明，有效的不平等给出了射仪的凸壳的完整描述。第二个家庭在多种情况下混合了不平等现象，并通过举重获得了进一步的力量。我们的数值实验证明了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 reliability of the DRC model and the effectiveness of our proposed reformulation and valid inequalities.
