Nenad Mladenovic
Nenad Mladenovic
LAMIH, University of Valenciennes, France
Skewed general VNS for the maximally diverse grouping and clique partitioning problems on the network
LAMIH, University of Valenciennes, France
Skewed general VNS for the maximally diverse grouping and clique partitioning problems on the network
joint work with J. Brimberg and D. Urosevic
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. We develop new variant of variable neighbourhood search based heuristic for solving the problem. Based on extensive computational experience, it appears that our new heuristic outperforms the current state of the art heuristic. Moreover, the best know solutions have been improved on 531 out of 540 test instances from the literature. Then we show that the Clique partitioning problem (CPP) can be reformulated in an equivalent form as the Maximally Diverse Grouping Problem. We then modify a skewed general variable neighbourhood search heuristic (SGVNS) that was first developed to solve the MDGP. Similarly as with the MDGP, significant improvements over the state of the art are obtained when SGVNS is tested on large scale instances. This further confirms the usefulness of a combined approach of diversification afforded with skewed VNS and intensification afforded with the local search in general VNS. Finally, we show that CPP may be used to identify communities on social network instances. The results are compared with 'ratio/cut' and modularity criteria.
Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!
To be used only for spelling or punctuation mistakes.