A branch and bound algorithm for the maximum diversity problem
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 line…
GRASP and path relinking for the max–min diversity problem
The max-min diversity problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method-based on the GRASP and path relinking methodologies-for finding approximate solutions to this optimization problem. We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary p…
Tabu search with strategic oscillation for the maximally diverse grouping problem
We propose new heuristic procedures for the maximally diverse grouping problem (MDGP). This NP-hard problem consists of forming maximally diverse groups—of equal or different size—from a given set of elements. The most general formulation, which we address, allows for the size of each group to fall within specified limits. The MDGP has applications in academics, such as creating diverse teams of students, or in training settings where it may be desired to create groups that are as diverse as possible. Search mechanisms, based on the tabu search methodology, are developed for the MDGP, including a strategic oscillation that enables search paths to cross a feasibility boundary. We evaluate co…
The Scatter Search Methodology
Scatter search (SS) is an evolutionary approach for optimization. It has been applied to problems with continuous and discrete variables and with a single or multiple objectives. The success of SS as an optimization technique is well documented in a constantly growing number of journal articles and book chapters. This article first focuses on the basic SS framework, which is responsible for most of the outcomes reported in the literature, and then covers advanced elements that have been introduced in a few selected papers, such as the hybridization with tabu search, a well-known memory-based metaheuristic. We consider the maximum diversity problem to illustrate the search elements, methods …
Tabu search for the Max–Mean Dispersion Problem
In this paper, we address a variant of a classical optimization model in the context of maximizing the diversity of a set of elements. In particular, we propose heuristics to maximize the mean dispersion of the selected elements in a given set. This NP-hard problem was recently introduced as the maximum mean dispersion problem (MaxMeanDP), and it models several real problems, from pollution control to ranking of web pages. In this paper, we first review the previous methods for the MaxMeanDP, and then explore different tabu search approaches, and their influence on the quality of the solutions obtained. As a result, we propose a dynamic tabu search algorithm, based on three different neighb…