Measuring diversity. A review and an empirical analysis

Maximum diversity problems arise in many practical settings from facility location to social networks, and constitute an important class of NP-hard problems in combinatorial optimization. There has been a growing interest in these problems in recent years, and different mathematical programming models have been proposed to capture the notion of diversity. They basically consist of selecting a subset of elements of a given set in such a way that a measure based on their pairwise distances is maximized to achieve dispersion or representativeness. In this paper, we perform an exhaustive comparison of four mathematical models to achieve diversity over the public domain library MDPLIB, studying the structure of the solutions obtained with each of them. We extend this library by including new Euclidean instances which permit to analyze the geometrical distribution of the solutions. Our study concludes which models are better suited for dispersion and which ones for representativeness in terms of the structure of their solutions, as well as which instances are difficult to solve. We also identify in our conclusions one of the models which is not recommended in any setting. We finalize by proposing two improvements, one related to the models and one to solving methods. The computational testing shows the value of the analysis and merit of our proposals.