6533b81ffe1ef96bd12779e5

RESEARCH PRODUCT

A branch and bound algorithm for the maximum diversity problem

Rafael MartíMicael GallegoAbraham Duarte

subject

Mathematical optimizationInformation Systems and ManagementGeneral Computer ScienceBranch and boundbusiness.industryBranch and bound methodManagement Science and Operations ResearchUpper and lower boundsIndustrial and Manufacturing EngineeringSet (abstract data type)SoftwareModeling and SimulationbusinessInteger programmingAlgorithmInteger (computer science)Mathematics

description

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.

yearjournalcountryeditionlanguage
2010-01-01European Journal of Operational Research
https://doi.org/10.1016/j.ejor.2008.12.023