Optimization Online


Probabilistic Set Covering with Correlations

Shabbir Ahmed(sahmed***at***isye.gatech.edu)
Dimitri Papageorgiou(djpapag***at***isye.gatech.edu)

Abstract: We consider a probabilistic set covering problem where 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 pre-specified probability. To date, literature on this problem has focused on the special case in which uncertainties are independent. In this paper, we formulate conservative deterministic mixed-integer programming models for probabilistic set covering problems with correlated uncertainties. By exploiting the supermodularity properties of the probabilistic covering constraints and analyzing their polyhedral structure, we develop strong valid inequalities to strengthen the formulations. Computational results illustrate that our modeling approach outperforms formulations in which correlations are ignored and that our algorithms can significantly reduce overall computation time.

Keywords: ambiguous chance constraint, integer programming, set covering, stochastic programming, supermodularity

Category 1: Stochastic Programming

Category 2: Integer Programming

Citation: Georgia Institute of Technology, ISyE Technical Report, July 2011

Download: [PDF]

Entry Submitted: 07/30/2011
Entry Accepted: 07/31/2011
Entry Last Modified: 07/30/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society