Probabilistic Set Covering with Correlations

We consider two variants of a probabilistic set covering (PSC) problem. The first variant assumes that there is uncertainty regarding whether a selected set can cover an item, and the objective is to determine a minimum-cost combination of sets so that each item is covered with a prespecified probability. The second variant seeks to maximize the minimum probability that a selected set can cover all items. To date, literature on this problem has focused on the special case in which uncertainties are independent. In this paper, we formulate deterministic mixed-integer programming models for distributionally robust PSC problems with correlated uncertainties. By exploiting the supermodularity of certain substructures and analyzing their polyhedral properties, we develop strong valid inequalities to strengthen the formulations. Computational results illustrate that our modeling approach can outperform formulations in which correlations are ignored and that our algorithms can significantly reduce overall computation time.