Probabilistic Set Covering with Correlations

Shabbir Ahmed () and Dimitri J. Papageorgiou ()
Additional contact information
Shabbir Ahmed: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Dimitri J. Papageorgiou: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Operations Research, 2013, vol. 61, issue 2, 438-452

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

Keywords: distributionally robust models; integer programming; set covering; stochastic programming; supermodularity (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1135 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:2:p:438-452

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().