Measuring diversity. A review and an empirical analysis

Francisco Parreño, Ramón Álvarez-Valdés and Rafael Martí

European Journal of Operational Research, 2021, vol. 289, issue 2, 515-532

Abstract: 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.

Keywords: Combinatorial optimization; Maximum diversity; Mathematical formulations; Empirical comparison (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720306792
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:289:y:2021:i:2:p:515-532

DOI: 10.1016/j.ejor.2020.07.053

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().