Iterated greedy for the maximum diversity problem

The problem of choosing a subset of elements with maximum diversity from a given set is known as the maximum diversity problem. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we present a simple iterated greedy metaheuristic that generates a sequence of solutions by iterating over a greedy construction heuristic using destruction and construction phases. Extensive computational experiments reveal that the proposed algorithm is highly effective as compared to the best-so-far metaheuristics for the problem under consideration.