Kernel based tabu search for the Set-union Knapsack Problem

Abstract Given a set of profitable items where each item is a set of weighted elements, the Set-union Knapsack Problem is to pack a subset of items into a capacity constrained knapsack to maximize the total profit of the selected items. This problem appears in many practical applications; however, it is computationally challenging. To advance the state-of-the-art for solving this relevant problem, we introduce a competitive heuristic algorithm, which features original kernel-based search components and an effective local search procedure. Extensive computational assessments on 60 benchmark instances demonstrate the high performance of the algorithm. We show different analyses to get insights into the influences of its algorithmic components. We make the code of the algorithm publicly available to facilitate its use in practice.