Probabilistic partial set covering with an oracle for chance constraints

We consider a class of chance-constrained combinatorial optimization problems, which we refer to as probabilistic partial set-covering (PPSC) problems. Given a prespecified risk level 2 [0; 1], the PPSC problem aims to find the minimum cost selection of subsets of items such that a target number of items is covered with probability at least 1. We show that PPSC admits an efficient probability oracle that computes the coverage probability exactly, under certain distributions of the random variables representing the coverage relation. Using this oracle, we give a compact mixed-integer program that solves the PPSC problem for a special case. For large-scale instances for which an exact oracle-based method exhibits slow convergence, we propose a samplingbased approach that exploits the special structure of PPSC. The oracle can be used as a tool for checking and fixing the feasibility of the solution given by this approach. In particular, we introduce a new class of facet-defining inequalities for a submodular substructure of PPSC, and show that a sampling-based algorithm coupled with the probability oracle effectively provides high-quality feasible solutions to the large-scale test instances.