Adaptive neighborhood reduction-based memetic algorithm for the set-union knapsack problem

The set-union knapsack problem (SUKP) is an important NP-hard variant of the knapsack problem, where each item has a profit and is composed of multiple weighted elements. The SUKP aims to select a subset of items that maximizes the total profit while ensuring the union of their associated elements satisfies the capacity constraint. The SUKP is a challenging combinatorial optimization problem that has been widely studied for its theoretical value and practical relevance. In this work, we present a population-based memetic framework specifically designed for solving the SUKP. The proposed approach integrates an adaptive neighborhood reduction based memetic search, which strengthens intensification by embedding a dynamic profit-to-weight ratio scoring method into a solution-based tabu search. To ensure diversification, a diversity-driven greedy crossover operator and an adaptive population updating rule are developed. The algorithm requires no manual parameter tuning and remains effective across instances of widely varying sizes. Computational results on 132 commonly used benchmark instances demonstrate that our method is both competitive and robust compared with state-of-the-art algorithms. The algorithm is further applied to the SUKP-related budgeted maximum coverage problem, confirming its efficiency and generality. We also provide additional analysis on the influences of several key components of the algorithm.