Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 230, Issue 1, Pages 63-75Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2013.03.021
Keywords
Facility location; Reliability; Linearization; Probability chains; Probability flow networks; Valid inequalities
Funding
- EPSRC [EP/E048552/1]
- Plan Nacional de Investigacion Cientifica, Desarrollo e Innovacion Tecnologica (I+D+I) [MTM2009-14039-C06-04]
- Fundacion Seneca [02911/PI/05]
- EPSRC [EP/E048552/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/E048552/1] Funding Source: researchfish
Ask authors/readers for more resources
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. (c) 2013 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available