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

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

0.00 Avg rating0 Votes
Article ID: iaor20133612
Volume: 230
Issue: 1
Start Page Number: 63
End Page Number: 75
Publication Date: Oct 2013
Journal: European Journal of Operational Research
Authors: , ,
Keywords: probability
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.