ナップサック問題(knapsack problem) は情報科学の分野における基礎的な問題で, これまでに多 くの研究がある．また，ナップサック問題に制約を加えた問題も多数存在する．本論文ではその ひとつである排他制的付きナップサック問題(disjunctively constrained knapsack problem) を対 象とする．これは，同時に選択できないアイテムに関する制約(排他制約) と容量制約を満たすよ うにいくつかのアイテムを選択するとき，選択したアイテムの価値の合計を最大化する問題であ る．これに対し，クリークを用いた上界値計算法を提案する．本計算法により大規模な問題例や 辺密度の高い問題例に対して高速に上界値を計算できることを計算実験により確認した．
Efficient computation of upper bounds for the disjunctively constrained knapsack problem / Y., Yamasaki; R., Schiavoni; Iori, Manuel; M., Yagiura; S., Martello. - In: SUURI KAISEKI KENKYUUJO KOUKYUUROKU. - ISSN 1880-2818. - STAMPA. - 1726:(2011), pp. 139-154.
Efficient computation of upper bounds for the disjunctively constrained knapsack problem
IORI, MANUEL;
2011
Abstract
ナップサック問題(knapsack problem) は情報科学の分野における基礎的な問題で, これまでに多 くの研究がある．また，ナップサック問題に制約を加えた問題も多数存在する．本論文ではその ひとつである排他制的付きナップサック問題(disjunctively constrained knapsack problem) を対 象とする．これは，同時に選択できないアイテムに関する制約(排他制約) と容量制約を満たすよ うにいくつかのアイテムを選択するとき，選択したアイテムの価値の合計を最大化する問題であ る．これに対し，クリークを用いた上界値計算法を提案する．本計算法により大規模な問題例や 辺密度の高い問題例に対して高速に上界値を計算できることを計算実験により確認した．
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
