Probability chains: A general linearization technique for modeling reliability in facility location and related problems

J.R. O'Hanley, M.P. Scaparra, S. García

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In this paper, we propose an efficient technique for linearizing facility location problems with site-dependent failure probabilities, focusing on the unreliable p-median problem. Our approach is based on the use of a specialized flow network, which we refer to as a probability chain, to evaluate compound probability terms. The resulting linear model is compact in size. The method can be employed in a straightforward way to linearize similarly structured problems, such as the maximum expected covering problem. We further discuss how probability chains can be extended to problems with co-location and other, more general problem classes. Additional lower bounds as well as valid inequalities for use within a branch and cut algorithm are introduced to significantly speed up overall solution time. Computational results are presented for several test problems showing the efficiency of our linear model in comparison to existing problem formulations.
Original languageEnglish
Pages (from-to)63-75
Number of pages13
JournalEuropean Journal of Operational Research
Volume230
Issue number1
Early online date27 Mar 2013
DOIs
Publication statusPublished - 1 Oct 2013

Keywords / Materials (for Non-textual outputs)

  • Facility location
  • Reliability
  • Linearization
  • Probability chains
  • Probability flow networks
  • Valid inequalities

Fingerprint

Dive into the research topics of 'Probability chains: A general linearization technique for modeling reliability in facility location and related problems'. Together they form a unique fingerprint.

Cite this