A Short Note on the Probabilistic Set Covering Problem

Abstract

In this paper we address the following probabilistic version (PSC) of the set coveringproblem: $ min{cx | P(Ax ≥ ξ) ≥ p, x_j \in {0, 1} j \in N }$ where A is a 0-1 matrix, ξis a random 0-1 vector and $p \in (0, 1]$ is the threshold probability level. In a recentdevelopment Saxena, Goyal and Lejeune proposed a MIP reformulation of (PSC) andreported extensive computational results with small and medium sized (PSC) instances.Their reformulation, however, suffers from the curse of exponentiality − the number ofconstraints in their model can grow exponentially rendering the MIP reformulation intractable for all practical purposes. In this paper, we give a polynomial-time algorithmto separate the (possibly exponential sized) constraint set of their MIP reformulation.Our separation routine is independent of the specific nature (concave, convex, linear,non-linear etc) of the distribution function of ξ, and can be easily embedded within abranch-and-cut framework yielding a distribution-free algorithm to solve (PSC). The resulting algorithm can solve (PSC) instances of arbitrarily large block sizes by generatingonly a small subset of constraints in the MIP reformulation and verifying the remainingconstraints implicitly. Furthermore, the constraints generated by the separation routineare independent of the coefficient matrix A and cost-vector c thereby facilitating theirapplication in sensitivity analysis, re-optimization and warm-starting (PSC). We givepreliminary computational results to illustrate our findings on a test-bed of 40 (PSC)instances created from OR-Lib set-covering instance scp41.