 Iterated maxima search for the maximally diverse grouping problemXiangjing Lai and Jin-Kao Hao European Journal of Operational Research, 2016, vol. 254, issue 3, 780-800 Abstract: 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. Keywords: Graph grouping and clustering problems; Iterated search; Heuristics (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:254:y:2016:i:3:p:780-800 DOI: 10.1016/j.ejor.2016.05.018 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.