An efficient local search heuristic with row weighting for the unicost set covering problem
An efficient local search heuristic with row weighting for the unicost set covering problem
复制标题
DOI：
10.1016/j.ejor.2015.05.038
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
Chao Gao;Xin Yao;T. Weise;Jinlong Li
中科院分区：
文献类型：
--
作者：
Chao Gao;Xin Yao;T. Weise;Jinlong Li
摘要集合覆盖问题（SCP）是NP难问题。我们提出了一个新的行加权局部搜索（RWLS）算法解决单一成本的SCP，即，USCPs的所有集的成本是相同的。RWLS是一种启发式算法，在其局部搜索框架中有三个主要组成部分：（1）加权方案，它更新未覆盖元素的权重以防止收敛到局部最优值，（2）禁忌策略，以避免搜索过程中可能的循环，以及（3）时间戳方法，以在优先级设置时打破联系。RWLS已经评估了大量的问题实例从OR库，并与其他方法相比。它能够找到所有最好的已知的解决方案（BKS），并改善其中的14个，虽然在几个实例中需要更高的计算工作量。RWLS在组合OR库实例上特别有效，并且可以显著改进最困难实例CYC11的最佳已知解决方案。RWLS在概念上很简单，没有依赖于实例的参数，这使得它成为一个实用且易于使用的USCP求解器。
Abstract The Set Covering Problem (SCP) is NP-hard. We propose a new Row Weighting Local Search (RWLS) algorithm for solving the unicost variant of the SCP, ie, USCPs where the costs of all sets are identical. RWLS is a heuristic algorithm that has three major components united in its local search framework:(1) a weighting scheme, which updates the weights of uncovered elements to prevent convergence to local optima,(2) tabu strategies to avoid possible cycles during the search, and (3) a timestamp method to break ties when prioritizing sets. RWLS has been evaluated on a large number of problem instances from the OR-Library and compared with other approaches. It is able to find all the best known solutions (BKS) and improve 14 of them, although requiring a higher computational effort on several instances. RWLS is especially effective on the combinatorial OR-Library instances and can improve the best known solution to the hardest instance CYC11 considerably. RWLS is conceptually simple and has no instance-dependent parameters, which makes it a practical and easy-to-use USCP solver.