Kernel based tabu search for the Set-union Knapsack Problem

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.

Automated summary

The algorithm introduced in this study aims to solve the Set-union Knapsack Problem efficiently through its original kernel-based search components and an effective local search procedure. Extensive computational assessments demonstrate its high performance on benchmark instances. Providing access to the algorithm's code aims to facilitate its practical use.