2021-06-25T14:31:00Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000114862017-01-12T15:00:00Z00581:00664:00668
Heuristic and Exact Algorithms for the Disjunctively Constrained Knapsack ProblemHeuristic and Exact Algorithms for the Disjunctively Constrained Knapsack Problemeng論文http://id.nii.ac.jp/1001/00011486/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=11486&item_no=1&attribute_id=1&file_no=1Copyright (c) 2002 by the Information Processing Society of Japan計算科学と数値シミュレーションの理論と実践Department of Computer Science The National Defense AcademyDepartment of Computer Science The National Defense AcademyDepartment of Computer Science The National Defense AcademyTakeo, YamadaSeiji, KataokaKohtaro, WatanabeWe 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情報処理学会論文誌439286428702002-09-151882-77642009-06-29