期刊
SCIENCE CHINA-INFORMATION SCIENCES
卷 60, 期 6, 页码 -出版社
SCIENCE PRESS
DOI: 10.1007/s11432-015-5377-8
关键词
unicost set covering problem; hyperedge configuration checking; local search; weight diversity strategy; hyperedge selection strategy
资金
- National Natural Science Foundation of China [61272208, 61370156, 61402196, 61503074, 61672261]
- Natural Science Foundation of Zhejiang Province [LY16F020004]
- Program for New Century Excellent Talents in University [NCET-13-0724]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据