A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity

作者：Wang, Yiyuan; Ouyang, Dantong; Zhang, Liming; Yin, Minghao^*

来源：Science China Information Sciences, 2017, 60(6): 062103.

DOI：10.1007/s11432-015-5377-8

• unicost set covering problem
• hyperedge configuration checking
• local search
• weight diversity strategy
• hyperedge selection strategy

The unicost version of well-known set covering problem (SCP) is central to a wide variety of practical applications for which finding an optimal solution quickly is crucial. In this paper, we propose a new local search-based algorithm for the unicost SCP which follows the general framework of the popular stochastic local search with a particular focus on the hyperedge selection strategy and weight diversity strategy. Specifically, a strategy as called hyperedge configuration checking strategy is proposed here to avoid the search trajectory which leads to local optima. Additionally, a new weight diversity strategy is proposed for the diversification of search results, by changing the weight of both covered and uncovered vertices in the current solution. The experimental results show that our algorithm significantly outperforms the state-of-the-art heuristic algorithm by one to two orders of magnitudes on the 85 classical instances. Also, our algorithm improves the current optimal solutions of 11 instances.

• 出版日期2017-6
• 单位东北师范大学; 吉林大学