Chance-constrained set covering with Wasserstein ambiguity

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...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2023-03, Vol.198 (1), p.621-674
Main Authors: Shen, Haoming, Jiang, Ruiwei
Format: Article
Language:English
Subjects:
Algorithms
Ambiguity
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Computational geometry
Convexity
Full Length Paper
Hardness
Inequalities
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Mechanical properties
Numerical Analysis
Robustness (mathematics)
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-022-01788-6