Modeling and Solution Procedures for Diversity Maximization
Abstract
Many important problems involve selecting a subset from a larger population such that the aggregate diversity of the subset selected is a large as possible. This problem, known as the diversity maximization problem, is known to be NP-hard. As such, it is very challenging from a computational point of view and only very small (toy) problems can be solved to optimality. Accordingly, most research into the important area has focused on various heuristic approaches. In this research, we report on a new tabu search-based approach to the diversity maximization (MD) problem. We also indicate how additional considerations (constraints) can be folded into the MD model and readily accommodated. Our results are very attractive in terms of both effectiveness and efficiency as we are now quickly solving problems many times larger than previously reported in the literature. Moreover, the solution method we developed for MD has application to a wide variety of other problem areas for which a common thread with MD had not previously been noted in the literature. Thus we are able to greatly leverage the work pioneered here to provide solution procedures for other problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 2002
- Accession Number
- ADA409029
Entities
People
- Bahram Alidaee
- Fred Glover
- Gary Kochenberger
- Keith Womer
Organizations
- University of Mississippi