.png){kind=icon}
.png){kind=icon}
Return
A branch and bound algorithm for the maximum diversity problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2008.12.023.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2008 Elsevier B.V. All rights reserved
Keywords:
Maximum diversity problem
Branch and bound
Integer programming
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W