کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
480850 | 1446137 | 2010 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A branch and bound algorithm for the maximum diversity problem A branch and bound algorithm for the maximum diversity problem](/preview/png/480850.png)
This article begins with a review of previously proposed integer formulations for the maximum diversity problem (MDP). This problem consists of selecting a subset of elements from a larger set in such a way that the sum of the distances between the chosen elements is maximized. We propose a branch and bound algorithm and develop several upper bounds on the objective function values of partial solutions to the MDP. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the medium-sized instances (with 50 elements) as well as some large-sized instances (with 100 elements). We compare our method with the best previous linear integer formulation solved with the well-known software Cplex. The comparison favors the proposed procedure.
Journal: European Journal of Operational Research - Volume 200, Issue 1, 1 January 2010, Pages 36–44