Maximally diverse grouping and clique partitioning problems with skewed general variable neighborhood search

Abstract

The maximally diverse grouping problem (MDGP) requires finding a partition of a given set of elements into a fixed number of mutually disjoint subsets (or groups) in order to maximize the overall diversity between elements of the same group. The clique partitioning problem (CPP) has a similar form as the MDGP, but is defined as the minimization of dissimilarity of elements in an unknown number of groups. In this paper a new variant of variable neighborhood search referred to as skewed general variable neighborhood search (SGVNS) is used to solve both problems. Extensive computational results show that the developed heuristic significantly outperforms its competitors. This demonstrates the usefulness of a combined approach of diversification afforded with skewed VNS and intensification afforded with the local search in general VNS.