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/8374
MIP Reformulations of the Probabilistic Set Covering Problem
Saxena, Anureet
Goyal, Vineet
Lejeune, Miguel
In this paper we address the following probabilistic version (PSC) of the set cover-ing problem: $ min{cx | P(Ax ≥ ξ) ≥ p, x_j \in {0, 1}N }$ where A is a 0-1 matrix, ξ is arandom 0-1 vector and $p \in (0, 1]$ is the threshold probability level. We formulate (PSC)as a mixed integer non-linear program (MINLP) and linearize the resulting (MINLP)to obtain a MIP reformulation. We introduce the concepts of p-inefficiency and polaritycuts. While the former is aimed at reducing the number of constraints in our model,the later is used as a strengthening device to obtain stronger formulations. A hierarchy of relaxations for (PSC) is introduced, and fundamental relationships between therelaxations are established culminating with a MIP reformulation of (PSC) with noadditional integer constrained variables. Simplifications of the MIP model which resultwhen one of the following conditions hold are briefly discussed: A is a balanced matrix,A has the circular ones property, the components of ξ are pairwise independent, thedistribution function of ξ is a stationary distribution or has the so-called disjunctiveshattering property. We corroborate our theoretical findings by an extensive computational experiment on a test-bed consisting of almost 10,000 probabilistic instances.This test-bed was created using deterministic instances from the literature and consistsof probabilistic variants of the set-covering model and capacitated versions of facilitylocation, warehouse location and k-median models. Our computational results showthat our procedure is orders of magnitude faster than any of the existing approachesto solve (PSC), and in many cases can reduce hours of computing time to fraction ofseconds.
Files in this item
Thumbnail
2.pdf — Adobe PDF — 501.9 Kb
MD5: 1032af73a8b4cbc9eec964d5dc1c5844
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/8374
Permanent URL
https://doi.org/10.18452/8374
HTML
<a href="https://doi.org/10.18452/8374">https://doi.org/10.18452/8374</a>