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

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