A threshold search based memetic algorithm for the disjunctively constrained knapsack problem

The disjunctively constrained knapsack problem consists in packing a subset of pairwisely compatible items in a capacity-constrained knapsack such that the total profit of the selected items is maximized while satisfying the knapsack capacity. DCKP has numerous applications and is however computationally challenging (NP-hard). In this work, we present a threshold search based memetic algorithm for solving the DCKP that combines the memetic framework with threshold search to find high quality solutions. Extensive computational assessments on two sets of 6340 benchmark instances in the literature demonstrate that the proposed algorithm is highly competitive compared to the state-of-the-art methods. In particular, we report 24 and 354 improved best-known results (new lower bounds) for Set I (100 instances) and for Set II (6240 instances), respectively. We additionally apply the approach to solve a real-life daily photograph scheduling problem of an earth observation satellite. We analyze the key algorithmic components and shed lights on their roles for the performance of the algorithm.

Automated summary

The paper presents a threshold search based memetic algorithm for solving the DCKP problem, combining the memetic framework with threshold search to find high quality solutions. Extensive computational assessments on benchmark instances demonstrate that the algorithm is highly competitive and effective compared to state-of-the-art methods.