A restart local search algorithm with relaxed configuration checking strategy for the minimum k-dominating set problem

摘要

The minimum k-dominating set (MKDS) problem, an extension of the classical minimum dominating set problem, is a famous combinatorial optimization problem with a wide range of applications in real life. At present, there are only a few heuristic algorithms to solve this problem, research on such methods remains in its nascent stages, which cannot scale up and are time-consuming. Therefore, this paper proposes a novel local search algorithm to solve MKDS problem, which consists of three new ideas. First, to construct the high quality initial solutions, an efficient initial construction method is proposed. Unlike previous methods just based on vertex scores, this method considers both vertex scores and vertex neighbors’ states when selecting a vertex to add into the initial solution. Second, a relaxed configuration checking strategy is designed to avoid the cycling problem in neighborhood search. Thirdly, a vertex selection strategy is presented by combining the vertex score with the relaxed configuration checking strategy to determine which vertex should be added into or removed from the candidate solution. Based on these strategies, the effective local search algorithm namely RLS_RCC is proposed. RLS_RCC algorithm is evaluated against the famous commercial solver CPLEX, the classic algorithm GRASP and the state-of-the-art algorithm VSCC2 on three types of benchmark instances. The experimental results show that RLS_RCC algorithm is very competitive in terms of solution quality and computing time. Specifically, RLS_RCC obtains 40 new upper bounds of 54 general graph instances, 13 new upper bounds of 12 UDG groups, and 32 new upper bounds of 37 DIMACS instances for three k values.