Chance-Constrained Set Covering with Wasserstein Ambiguity
arXiv:2010.05671 · doi:10.1007/s10107-022-01788-6
Abstract
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.
arXiv commentMath. Program. (2022)
References in corpus (4)
- Wasserstein Distributionally Robust Stochastic Control: A Data-Driven Approach
- Chance-Constrained Combinatorial Optimization with a Probability Oracle and Its Application to Probabilistic Partial Set Covering
- Distributionally Robust Chance-Constrained Programs with Right-Hand Side Uncertainty under Wasserstein Ambiguity
- Strong Formulations for Distributionally Robust Chance-Constrained Programs with Left-Hand Side Uncertainty under Wasserstein Ambiguity