A 3-flip neighborhood local search for the set covering problem
A 3-flip neighborhood local search for the set covering problem
复制标题
DOI：
10.1016/j.ejor.2004.10.018
复制
发表时间：
2006-07
期刊：
影响因子：
--
通讯作者：
M. Yagiura;Masahiro Kishida;T. Ibaraki
中科院分区：
文献类型：
--
作者：
M. Yagiura;Masahiro Kishida;T. Ibaraki
集合覆盖问题（SCP）要求从n个给定子集中寻找一个最小代价子集族，它们共同覆盖整个基集。在本文中，我们提出了一个局部搜索算法的SCP，它有以下三个特点。(1)使用3-翻转邻域，这是通过交换最多三个子集从当前解可获得的解的集合。由于3-flip邻域的大小是O（n3），如果简单地实现，邻域搜索变得昂贵。为了克服这一点，我们提出了一个有效的实现，减少了候选人在附近的数量，而不牺牲解决方案的质量。(2)我们允许搜索访问的不可行区域，并纳入战略振荡技术实现的惩罚权重的自适应控制。(3)通过使用拉格朗日松弛的信息的问题的大小减少被纳入，这是必不可少的解决非常大的情况。根据计算比较基准实例与其他现有的启发式算法的SCP，我们的算法执行相当有效的各种类型的问题，特别是非常大规模的情况下。
The set covering problem (SCP) calls for a minimum cost family of subsets from n given subsets, which together covers the entire ground set. In this paper, we propose a local search algorithm for SCP, which has the following three characteristics. (1) The use of 3-flip neighborhood, which is the set of solutions obtainable from the current solution by exchanging at most three subsets. As the size of 3-flip neighborhood is O(n3), the neighborhood search becomes expensive if implemented naively. To overcome this, we propose an efficient implementation that reduces the number of candidates in the neighborhood without sacrificing the solution quality. (2) We allow the search to visit the infeasible region, and incorporate the strategic oscillation technique realized by adaptive control of penalty weights. (3) The size reduction of the problem by using the information from the Lagrangian relaxation is incorporated, which is indispensable for solving very large instances. According to computational comparisons on benchmark instances with other existing heuristic algorithms for SCP, our algorithm performs quite effectively for various types of problems, especially for very large-scale instances.