Iterated maxima search for the maximally diverse grouping problem

作者：Lai Xiangjing; Hao Jin Kao^*

来源：European Journal of Operational Research, 2016, 254(3): 780-800.

DOI：10.1016/j.ejor.2016.05.018

• Graph grouping and clustering problems
• Iterated search
• Heuristics

The maximally diverse grouping problem (MDGP) is to partition the vertices of an edge-weighted and undirected complete graph into m groups such that the total weight of the groups is maximized subject to some group size constraints. MDGP is a NP-hard combinatorial problem with a number of relevant applications. In this paper, we present an innovative heuristic algorithm called iterated maxima search (IMS) algorithm for solving MDGP. The proposed approach employs a maxima search procedure that integrates organically an efficient local optimization method and a weak perturbation operator to reinforce the intensification of the search and a strong perturbation operator to diversify the search. Extensive experiments on five sets of 500 MDGP benchmark instances of the literature show that IMS competes favorably with the state-of-the-art algorithms. We provide additional experiments to shed light on the rationality of the proposed algorithm and investigate the role of the key ingredients.

• 出版日期2016-11-1