Logo of Humboldt-Universität zu BerlinLogo of Humboldt-Universität zu Berlin
edoc-Server
Open-Access-Publikationsserver der Humboldt-Universität
de|en
Header image: facade of Humboldt-Universität zu Berlin
View Item 
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2007
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2007
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
All of edoc-ServerCommunity & CollectionTitleAuthorSubjectThis CollectionTitleAuthorSubject
PublishLoginRegisterHelp
StatisticsView Usage Statistics
All of edoc-ServerCommunity & CollectionTitleAuthorSubjectThis CollectionTitleAuthorSubject
PublishLoginRegisterHelp
StatisticsView Usage Statistics
View Item 
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2007
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2007
  • View Item
2007-05-29Buch DOI: 10.18452/8375
A Short Note on the Probabilistic Set Covering Problem
Saxena, Anureet
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.
Files in this item
Thumbnail
3.pdf — Adobe PDF — 201.6 Kb
MD5: 2389e11c8ad254d95ee428517d2d83f8
Cite
BibTeX
EndNote
RIS
InCopyright
Details
DINI-Zertifikat 2019OpenAIRE validatedORCID Consortium
Imprint Policy Contact Data Privacy Statement
A service of University Library and Computer and Media Service
© Humboldt-Universität zu Berlin
 
DOI
10.18452/8375
Permanent URL
https://doi.org/10.18452/8375
HTML
<a href="https://doi.org/10.18452/8375">https://doi.org/10.18452/8375</a>