A threshold search based memetic algorithm for the disjunctively constrained knapsack problem
This work addresses a computationally difficult problem with applications in resource allocation, but it is incremental as it builds on existing memetic and threshold search methods.
The paper tackles the disjunctively constrained knapsack problem, an NP-hard optimization challenge, by proposing a threshold search based memetic algorithm, which achieved 24 and 354 improved best-known results on benchmark sets of 100 and 6240 instances, respectively.
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.