论文标题
有效而有效的本地搜索设定工会背包问题和预算的最大覆盖率问题
Efficient and Effective Local Search for the Set-Union Knapsack Problem and Budgeted Maximum Coverage Problem
论文作者
论文摘要
设定工会背包问题（SUKP）和预算的最大覆盖范围问题（BMCP）是流行背包问题的两个密切相关的变体问题。给定一组加权元素和一组具有非负值的项目，其中每个项目涵盖了几个不同的元素，这两个问题都旨在找到最大化目标函数的项目的子集，同时满足背包容量（预算）约束。我们提出了这两个问题的一种称为E2L的高效局部搜索算法。据我们所知，这是第一次为他们俩提出了算法。 E2LS通过应用拟议的新型操作员添加$^*$来穿越精致的搜索区域来权衡搜索区域和搜索效率。这种权衡的机制使E2L可以广泛，快速地探索解决方案空间。 Tabu搜索方法还应用于E2LS，以帮助算法从本地Optima逃脱。总共168个公共实例的广泛实验表明，SUKP和BMCP的拟议算法表现出色。
The Set-Union Knapsack Problem (SUKP) and Budgeted Maximum Coverage Problem (BMCP) are two closely related variant problems of the popular knapsack problem. Given a set of weighted elements and a set of items with nonnegative values, where each item covers several distinct elements, these two problems both aim to find a subset of items that maximizes an objective function while satisfying a knapsack capacity (budget) constraint. We propose an efficient and effective local search algorithm called E2LS for these two problems. To our knowledge, this is the first time that an algorithm has been proposed for both of them. E2LS trade-offs the search region and search efficiency by applying a proposed novel operator ADD$^*$ to traverse the refined search region. Such a trade-off mechanism allows E2LS to explore the solution space widely and quickly. The tabu search method is also applied in E2LS to help the algorithm escape from local optima. Extensive experiments on a total of 168 public instances with various scales demonstrate the excellent performance of the proposed algorithm for both the SUKP and BMCP.
