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
复制标题
DOI：
10.1016/j.ejor.2013.03.021
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
J. O’Hanley;M. P. Scaparra;Sergio García
中科院分区：
文献类型：
--
作者：
J. O’Hanley;M. P. Scaparra;Sergio García
在本文中，我们提出了一个有效的技术线性化设施选址问题与站点相关的故障概率，重点是不可靠的p-中位数问题。我们的方法是基于使用一个专门的流网络，我们称为概率链，以评估复合概率项。所得到的线性模型在尺寸上是紧凑的。该方法可以采用一种简单的方式来线性化类似结构的问题，如最大期望覆盖问题。我们进一步讨论了如何概率链可以扩展到问题的协同定位和其他更一般的问题类。额外的下限以及有效的不等式内使用的分支和切割算法，显着加快整体解决方案的时间。几个测试问题的计算结果表明，我们的线性模型的效率相比，现有的问题配方。
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.