A first level scatter search for disjunctively constrained knapsack problems

In this paper we propose a version of the scatter search (SS) for tackling disjunctively constrained knapsack problems (DCKP). The DCKP is a special single constraint knapsack problem which contains specific additional constraints representing an independent set problem. The proposed approach applies the first level of SS using both the starting phase and the evolutionary one. Both phases are simulated using the five principal components of the scatter search, applied to an equivalent DCKP model re-enforced with two types of valid inequalities. The proposed algorithm is analyzed computationally on a set of problem instances of the literature which cannot be solved to proven optimality in a reasonable time. The obtained results are compared to the results provided by the Cplex solver; encouraging results have been obtained (19 new solution values out of 25 are obtained).