A reactive local search-based algorithm for the disjunctively constrained knapsack problem

In this paper, we propose a reactive local search-based algorithm for the disjunctively constrained knapsack problem (DCKP). DCKP is a variant of the standard knapsack problem, an NP-hard combinatorial optimization problem, with special disjunctive constraints. A disjunctive constraint is a couple of items for which only one item is packed. The proposed algorithm is based upon a reactive local search, where an explicit check for the repetition of configurations is added to the search process. Initially, two complementary greedy procedures are applied in order to construct a starting solution. Second, a degrading procedure is introduced in order (i) to escape to local optima and (ii) to introduce a diversification in the search space. Finally, a memory list is added in order to forbid the repetition of configurations. The performance of two versions of the algorithm has been evaluated on several problem instances and compared to the results obtained by running the Cplex solver. Encouraging results have been obtained.