Chance-constrained set covering with Wasserstein ambiguity

• 成果类型: Article
• 署名作者: Shen, Haoming; Jiang, Ruiwei
• 署名单位: University of Michigan System; University of Michigan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01788-6
• 发表日期: 2023
• 页码: 621-674
• 关键词: Optimization; approximation; formulations; PROGRAMS; RISK

摘要

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.