Title: 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.
Publication Year: 2002
Publication Date: 2002-09-15
Language: en
Type: article
Access and Citation
Cited By Count: 76
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot