Local Search Algorithms For Combinatorial Optimization Problems

The connected vertex cover problem and the k-plex problem are two important problems of combinatorial optimization.These two problems have important applications in areas such as network security,large scale integrated circuits,wireless network design,and social network.A good performance algorithm can not only improve the efficiency and accuracy of solving these two problems,but also improve the operational efficiency,reduce the time and labor costs,save resources and improve the product profit margins in the real industries.In this paper,three local search algorithms are designed to solve the connected vertex cover problem and the k-plex problem respectively.The GRASP-CVC algorithm and EWGRASP-CVC algorithm are used to solve the connected vertex cover problem.In these two algorithms,we use greedy strategy to construct the initial feasible solution of the problem simply and quickly.Meanwhile,in order to avoid the cycling search problem of the local search algorithm,configuration checking strategy and edge-weighted strategy with forgetting mechanism are applied to the algorithms.For the k-plex problem,we designed a PLS algorithm to solve it.The PLS algorithm is mainly composed of three sub-phases,each sub-phase searching for the solution space of the problem according to different strategies.The PLS algorithm can not only handle the instances of different features,but also ensure that the algorithm can find the largest possible solution space and improve the ability of the algorithm to jump out of the local optimum by switching among the three sub-phases.In order to verify the effectiveness and efficiency of the algorithms we designed,we compare the existing algorithms with the algorithms proposed in this paper.The experimental results on a large number of classical instances show that the proposed algorithms can solve the connected vertex cover and k-plex problem quickly and efficiently,and shows great superiority over the existing methods.