Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 200, Issue 1, Pages 36-44Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2008.12.023
Keywords
Maximum diversity problem; Branch and bound; Integer programming
Funding
- Ministerio de Educacion y Ciencia of Spain [TIN2006-02696]
- Comunidad de Madrid - Universidad Rey Juan Carlos [CCG08-URJC/TIC-3731]
Ask authors/readers for more resources
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
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