Variable Neighborhood Search with Dynamic Exploration for the Set Union Knapsack Problem

In the set-union knapsack problem (SUKP), we are given a set of elements, each with a positive weight, and a set of items, each with a positive profit and a corresponding set of associated elements. An item is included in the knapsack only if all its associated elements are included. The SUKP is to select the items to be included in the knapsack such that the total profit of the selected items is maximized and the capacity of the knapsack is not exceeded. We propose a variable neighborhood search to solve the SUKP and show, on a set of benchmark instances from the literature, that this method is competitive with the state-of-the-art heuristics for the problem. In addition, we focus on simplicity of the proposed algorithm while providing competitive results, thus showing that less may yield more.