  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 analyze the key algorithmic components and
shed lights on their roles for the performance of the algorithm. The code of
our algorithm will be made publicly available.
