Solving the maximally diverse grouping problem by skewed general variable neighborhood search

Jack Brimberg (1, 2) , Nenad Mladenovic (3) , Dragan Urošević (4)

1 Royal Military College of Canada
2 GERAD - Groupe d’études et de recherche en analyse des décisions
3 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201
4 SANU - Mathematical Institute of the Serbian Academy of Sciences and Arts

The maximally diverse grouping problem 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. In this paper we develop a new variant of variable neighborhood search for solving the problem. The extensive computational results show that our new heuristic significantly outperforms the current state of the art. Moreover, the best known solutions have been improved on 531 out of 540 test instances from the literature.

Domaines: Informatique [cs]

Jack Brimberg, Nenad Mladenovic, Dragan Urošević. Solving the maximally diverse grouping problem by skewed general variable neighborhood search. Information Sciences, 2015, 295, pp.650-675. ⟨10.1016/j.ins.2014.10.043⟩. ⟨hal-03401528⟩