Probability Learning based Tabu Search for the Budgeted Maximum Coverage
  Problem
  Knapsack problems are classic models that can formulate a wide range of
applications. In this work, we deal with the Budgeted Maximum Coverage Problem
(BMCP), which is a generalized 0-1 knapsack problem. Given a set of items with
nonnegative weights and a set of elements with nonnegative profits, where each
item is composed of a subset of elements, BMCP aims to pack a subset of items
in a capacity-constrained knapsack such that the total weight of the selected
items does not exceed the knapsack capacity, and the total profit of the
associated elements is maximized. Note that each element is counted once even
if it is covered multiple times. BMCP is closely related to the Set-Union
Knapsack Problem (SUKP) that is well studied in recent years. As the
counterpart problem of SUKP, however, BMCP was introduced early in 1999 but
since then it has been rarely studied, especially there is no practical
algorithm proposed. By combining the reinforcement learning technique to the
local search procedure, we propose a probability learning based tabu search
(PLTS) algorithm for addressing this NP-hard problem. The proposed algorithm
iterates through two distinct phases, namely a tabu search phase and a
probability learning based perturbation phase. As there is no benchmark
instances proposed in the literature, we generate 30 benchmark instances with
varied properties. Experimental results demonstrate that our PLTS algorithm
significantly outperforms the general CPLEX solver for solving the challenging
BMCP in terms of the solution quality.
