Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem

Given a set of items, each with a profit and a weight and a conflict graph describing incompatibilities between items, the Disjunctively Constrained Knapsack Problem is to select the maximum profit set of compatible items while satisfying the knapsack capacity constraint. We develop a probabilistic tabu search heuristic with multiple neighborhood structures. The proposed algorithm is evaluated on a total of [Formula: see text] benchmark instances from the literature up to [Formula: see text] items. Computational results disclose that the proposed tabu search method outperforms recent state‐of‐the‐art approaches. In particular, our approach is able to reach [Formula: see text] best known solutions and discover [Formula: see text] new best known solutions out of [Formula: see text] benchmark instances.