کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
474305 | 698860 | 2006 | 19 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Upper bounds and exact algorithms for pp-dispersion problems Upper bounds and exact algorithms for pp-dispersion problems](/preview/png/474305.png)
The p-dispersion-sum problem is the problem of locating p facilities at some of n predefined locations, such that the distance sum between the p facilities is maximized. The problem has applications in telecommunication (where it is desirable to disperse the transceivers in order to minimize interference problems), and in location of shops and service-stations (where the mutual competition should be minimized).A number of fast upper bounds are presented based on Lagrangian relaxation, semidefinite programming and reformulation techniques. A branch-and-bound algorithm is then derived, which at each branching node is able to compute the reformulation-based upper bound in O(n)O(n) time. Computational experiments show that the algorithm may solve geometric problems of size up to n=90n=90, and weighted geometric problems of size n=250n=250.The related p-dispersion problem is the problem of locating p facilities such that the minimum distance between two facilities is as large as possible. New formulations and fast upper bounds are presented, and it is discussed whether a similar framework as for the p-dispersion sum problem can be used to tighten the upper bounds. A solution algorithm based on transformation of the p-dispersion problem to the p-dispersion-sum problem is finally presented, and its performance is evaluated through several computational experiments.
Journal: Computers & Operations Research - Volume 33, Issue 5, May 2006, Pages 1380–1398