http://swrc.ontoware.org/ontology#Article
Heuristic and Exact Algorithms for the Disjunctively Constrained Knapsack Problem
en
論文
Department of Computer Science The National Defense Academy
Department of Computer Science The National Defense Academy
Department of Computer Science The National Defense Academy
Takeo Yamada
Seiji Kataoka
Kohtaro Watanabe
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. The knapsack problem with such an additional set of constraints is referred to as the disjunctively constrained knapsack problem (DCKP). We present a heuristic method as well as an implicit enumeration algorithm and an interval reduction method to solve DCKPs to optimality. Combining these we are able to solve DCKPs with up to 1 000 items.
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. The knapsack problem with such an additional set of constraints is referred to as the disjunctively constrained knapsack problem (DCKP). We present a heuristic method as well as an implicit enumeration algorithm and an interval reduction method to solve DCKPs to optimality. Combining these, we are able to solve DCKPs with up to 1,000 items.
AN00116647
情報処理学会論文誌
43
9
2864-2870
2002-09-15
1882-7764