论文标题
使用本地分支的非官方套装覆盖问题的启发式
A heuristic for the non-unicost set covering problem using local branching
论文作者
论文摘要
在本文中，我们提出了使用本地分支的非官方覆盖问题的启发式术语。本地分支消除了针对任何特定（零）优化问题定义特定问题搜索社区的需求。它通过将广义的锤距社区纳入问题来做到这一点，这自然会导致适当的社区搜索程序。我们将方法应用于非官方集覆盖问题。对于文献中已广泛考虑的65个测试问题提供了计算结果。我们的结果表明，我们检查的启发式方法比我们检查的其他八个启发式方法中的六个要好，比一个启发式启发式效果稍差，但是只有一个启发式词能超过所有其他启发式。我们认为，此处描述的工作表明，在文献中尚未完全利用使用本地分支的潜力（作为独立的数学家）。
In this paper we present a heuristic for the non-unicost set covering problem using local branching. Local branching eliminates the need to define a problem specific search neighbourhood for any particular (zero-one) optimisation problem. It does this by incorporating a generalised Hamming distance neighbourhood into the problem, and this leads naturally to an appropriate neighbourhood search procedure. We apply our approach to the non-unicost set covering problem. Computational results are presented for 65 test problems that have been widely considered in the literature. Our results indicate that our heuristic is better than six of the eight other heuristics we examined, slightly worse than that of one heuristic, but that there is a single heuristic that out-performs all others. We believe that the work described here illustrates that the potential for using local branching, operating as a stand-alone matheuristic, has not been fully exploited in the literature.
