Abstract: The Budgeted Maximum Coverage Problem(BMCP)(aka the knapsack maximum coverage problem) is a natural and more practical extension of the standard 0-1 knapsack problem and the set cover problem,and is also highly related to the set-union knapsack problem. Give n elements with non-negative profits, a set of m items, each item is a subset of the set of elements and each of them has a non-negative cost, and given a budget, BMCP aims to select some subsets such that the total cost of selected subsets does not exceed the budget, and the total profits of covered elements is maximized. It has a broad range of applications in real life, such as project allocation, financial decisions, worker employment, software installation packages, service operation providers, etc.BMCP, as an NP-complete problem highly related to SUKP, is difficult to solve, and relatively few studies have been conducted on the heuristic or meta-heuristic aspects of the standard BMCP. Therefore, it is of great importance to study this problem.
In this paper, we propose a more efficient heuristic algorithm for solving the BMCP and improve the relative stability of the solutions in the existing literature, providing more options for solving such problems. We propose an effective restricted neighborhood structure based tabu search algorithm (ERNSBTS) for the BMCP. The algorithm mainly consists of three parts: dynamic initialization, limiting the neighborhood structure based on relative empty rate and relative gain rate, and re-initializing dynamic random disturbance. First, since the tabu search has a strong dependence on the initial solution, it is proposed to construct the residual profit and residual value density to generate the initial solution. Then, a counter G is introduced to record the times of element coverage under the current solution, and two strategies are designed to expect the most promising subset to restrict the neighborhood structure. After that, greed is combined with heuristic ideas to design a perturbation procedure to take into account convex combinations of global and local to increase the diversity of initial solutions. In ERNSBTS, the relative empty rate, relative gain rate and dynamic random disturbance re-initialization ensure the convergence and diversity of the algorithm search.
In the computational experiments, the optimal combination of parameters in ERNSBTS is firstly determined using an orthogonal experimental approach. Secondly, to evaluate the effectiveness of the algorithm, we perform computations on 30 benchmark instances of the BMCP, and compare the results with the approximation algorithm, the probability learning based tabu search algorithm (PLTS) and the variable depth local search algorithm(VDLS). Finally, the ablation of the initialization method is investigated. The results show the high competitiveness of the proposed ERNSBTS algorithm in terms of solution quality, computational efficiency and robustness.
In further studies, we will find that there are many similar problems that are not much different from the budgeted maximum coverage problem, and the frameworks such as relative empty rate and relative gain rate proposed in this paper can be used to solve similar problems. The Set-Union Knapsack Problem (SUKP) is an example.

Key words: budget maximum coverage problem, relative empty rate, relative gain rate, effectivelyrestrict neighborhood structure, tabu search

摘要： 针对预算最大覆盖问题,设计出一种基于有效限制邻域结构的禁忌搜索算法(Effectively Restricted Neighborhood Structure Based Tabu Search, ERNSBTS)对其求解。该算法主要由动态初始化、基于策略限制邻域结构和动态随机扰动重新初始化三部分组成。首先,提出构建剩余利润和剩余价值密度来生成好的初始解。然后,引入计数器G来记录当前解下元素覆盖次数,设计相对置空率和相对增益率两种策略来得到最有期望子集来限制邻域结构。最后,设计扰动程序,将贪婪与启发式思想相结合,考虑全局和局部的凸组合,以增加初始解的多样性。在数值实验中,分析了ERNSBTS算法参数设置,同时将其与近似算法、PLTS和VDLS算法的结果进行比较分析,证实了ERNSBTS算法在求解质量、计算效率和鲁棒性方面的高竞争力。

关键词: 大覆盖问题, 相对置空率, 相对增益率, 有效限制邻域结构, 禁忌搜索