This paper presents a general variable neighborhood search (GVNS) heuristic for solving the maximum diverse grouping problem. Extensive computational experiments performed on a series of large random graphs as well as on several instances of the maximum diversity problem taken from the literature show that the results obtained by GVNS consistently outperform the best heuristics from the literature. | Yugoslav Journal of Operations Research 24 (2014) Number 1, 21-33 DOI: VARIABLE NEIGHBORHOOD SEARCH FOR MAXIMUM DIVERSE GROUPING PROBLEM Dragan UROŠEVIĆ Mathematical Institute SANU draganu@ Received: December 2012 / Accepted: January 2013 Abstract: This paper presents a general variable neighborhood search (GVNS) heuristic for solving the maximum diverse grouping problem. Extensive computational experiments performed on a series of large random graphs as well as on several instances of the maximum diversity problem taken from the literature show that the results obtained by GVNS consistently outperform the best heuristics from the literature. Keywords: Combinatorial optimization, Maximum Diverse Grouping, Metaheuristics, Variable Neighborhood Search. MSC: 90C59, 90C27, 90C06, 90C20. 1. INTRODUCTION The maximum diverse grouping problem (MDGP) consists of finding a way to divide a set of n elements into m mutually disjoint groups so that the total diversity among the elements belonging to the same group is maximized. The diversity among the elements in a group is calculated as the sum of the individual distance between each pair of elements. The objective of the problem is to maximize the overall diversity, ., the sum of the diversity of all groups. Feo and Khellaf [10] proved that the MDGP is NP-hard. The MDGP is also known as the k-partition problem (Feo et al. [9]), and the equitable partition problem (Mingers and O’Brien [17], O’Brien and Mingers [20]) that appears in a wide range of real life situations. The first application is in designing of VLSI circuits (Chen [4]; Feo and Khellaf [10]). Also, it can be applied in storing large programs onto paged memory (Kral, [15]), where the subroutines of a program have to be stored onto pages of available memory. In this case, the objective is to maximize data transfer between subroutines on D. Urošević / Variable Neighborhood Search 22 the same page (minimizing in this way .
