Abstract: The minimum weighted dominating set problem is one of NP-hard combinatorial optimization problems, and has lots of applications. In this paper, an efficient iterated tabu search algorithm is proposed to solve the minimum weighted dominating set problem. It adopts a random greedy construction algorithm to generate initial solutions, and uses a fast tabu local search algorithm to find local minimizers. In order to escape from the current local minimizer, the proposed algorithm presents a random perturbation and a repair strategy to search new solution regions. The experiments are done on a number of large scale benchmarks with 800 to 1, 000 vertices from the literature. Numerical results and comparisons with several heuristic methods indicate that the proposed algorithm is efficient.

Key words: dominating set, tabu search, combinatorial optimization

摘要： 最小赋权支配集是一个NP困难的组合优化问题，有着广泛的应用背景。提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法。该算法采用随机贪心构造算法构造初始解，并利用快速的局部禁忌搜索算法寻找局部最优解，通过随机扰动和修复策略来搜索新的区域，以期跳出当前的局部最优解。用顶点数为800到1 000的大规模标准测试例子测试提出的算法。数值实验结果和与现存的启发式算法比较结果表明了算法是有效的。

关键词: 支配集, 禁忌搜索, 组合优化