A novel two-model local search algorithm with a self-adaptive parameter for clique partitioning problem

Given a complete edge-weighted undirected graph G(V, E, W), clique partitioning problem (CPP) aims to cluster all vertices into an unknown number of disjoint groups and the objective is to maximize the sum of the edge weights of the induced subgraphs. CPP is an NP-hard combinatorial optimization problem with many real-world applications. In this paper, we propose a novel two-model local search algorithm with a self-adaptive parameter (TMLS_\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\_$$\end{document}SA) to solve CPP. First, a simple solution is presented, that is, one vertex per group is used. Then, we present a two-model local search that is used to improve the solution which comprises a move operator model and an exchange operator model. In the local search phase, a gain function is used to guide the search toward a possible best solution, and a lock mechanism is also applied to prevent the local search from immediately returning to visited solutions. Finally, we execute a perturbation procedure to increase the diversity. The perturbation strength is updated self-adaptively according to the solutions obtained. Our algorithm TMLS_\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\_$$\end{document}SA is compared with several representative algorithms, and the experimental results show that TMLS_\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\_$$\end{document}SA is superior to competitors on almost all test instances with respect to the solution quality.