Heuristic and Exact Algorithms for the Disjunctively Constrained Knapsack Problem

Abstract

We are concerned with a variation of the knapsack problem (KP), where some items are incompatible with some others. As in ordinary KPs, each item is associated with profit and weight, we have a knapsack of a fixed capacity, and the problem is to determine the set of items to be packed into the knapsack. However, the knapsack is not allowed to include incompatible pairs of items. The knapsack problem with these additional constraints is referred to as the disjunctively constrained knapsack problem (DCKP). We present an algorithm to solve this problem to optimality by combining the Lagrangian relaxation with the pegging test for ordinary KPs. The developed algorithm solves DCKPs with several thousands of items within a reasonable computing time.