  We address the Budgeted Maximum Coverage Problem (BMCP), which is a natural
and more practical extension of the standard 0-1 knapsack problem and the set
cover problem. Given m elements with nonnegative weights, n subsets of elements
with nonnegative costs, and a total budget, BMCP aims to select some subsets
such that the total cost of selected subsets does not exceed the budget, and
the total weight of associated elements is maximized. In this paper, we propose
a variable depth local search algorithm (VDLS) for the BMCP. VDLS first
generates an initial solution by a greedy algorithm, then iteratively improves
the solution through a partial depth-first search method, that can improve the
solution by simultaneously changing the states (selected or not) of multiple
subsets. Such method allows VDLS to explore the solution space widely and
deeply, and to yield high-quality solutions. We further propose a neighbour
structure to boost the algorithm performance, that is, both subsets have a
neighbour relation if they have at least one common associated element. By
applying the neighbour structure, VDLS can adjust the selected subsets while
losing as few covered elements as possible. Since the existing BMCP benchmarks
only have simple structures and small scales, we design 60 new instances with
relatively large scales and complex structures to enrich the diversity of the
BMCP instances. Experimental results on 30 public instances and 60 new
instances we designed demonstrate that VDLS significantly outperforms the
existing heuristic and the general CPLEX exact solver, for the BMCP.
