Simulated annealing with stochastic local search for minimum dominating set problem

In this paper, we propose a new method based on simulated annealing (SA) to solve the minimum dominating set problem. To deal with the considered problem, a stochastic local search (SLS) method is built first to find local solutions next to given solutions. Then, a simulated annealing algorithm is invoked to enhance the SLS method with the ability of escaping from local solutions. Moreover, three trial solution generation mechanisms are used to improve iterate solutions. The experimental results have shown the promising performance of the proposed SA-based method in comparison with some other meta-heuristics in terms of solution qualities and computational costs.