A restart local search algorithm with Tabu method for the minimum weighted connected dominating set problem

Ruizhi Li, Yupan Wang, Huan Liu, Ruiting Li, Shuli Hu and Minghao Yin

Journal of the Operational Research Society, 2022, vol. 73, issue 9, 2090-2103

Abstract: The minimum weighted connected dominating set problem is a significant NP-hard problem with wide applications, and is an extension of the classical minimum dominating set problem. In order to solve this problem, we present a restart local search algorithm with tabu method (RLS_ Tabu). In our RLS_ Tabu algorithm, we firstly involve the random restart initialization method to jump out of the local optimum. Meanwhile, RLS_ Tabu algorithm also applies tabu method in neighborhood search procedure to mitigate the cycling problem. Secondly, we present two strategies in neighborhood search procedure for removing vertices properly, which one is greedy and random strategy, and another one is multiple deletion strategy. The two strategies are crucial to improve the solution quality. Thirdly, the solution connected vertex is important to guarantee the feasibility of solutions. Therefore, we maintain the solution connected vertex set during the neighborhood search, and select the vertex to be added from this set. Finally, in order to intensify the solution, RLS_ Tabu utilizes the pruning function to delete redundant vertices in the candidate solution. In experimental section, we will compare our algorithm with the other six algorithms on three types of benchmarks. Experimental results indicate that our algorithm significantly outperforms the comparative algorithms on most benchmark instances.

Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2021.1952117 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:73:y:2022:i:9:p:2090-2103

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2021.1952117

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().