3M-3
排他制約付きナップサック問題に対する解法
○山崎洋祐（名大），Riccardo Schiavoni（University of Bologna），Manuel Iori（University of Modena and Reggio Emilia），柳浦睦憲（名大），Silvano Martello（University of Bologna）
ナップサック問題は情報科学の分野における基礎的な問題で,
これまでに多くの研究がある．
また，ナップサック問題に制約を加えた問題も多数存在する．
本研究ではそのひとつである排他制的付きナップサック問題を対象とする．
これは，同時に選択できないアイテムに関する制約(排他制約)と
容量制約を満たすようにいくつかのアイテムを選択するとき，
選択したアイテムの価値の合計を最大化する問題である．
この問題に対し，クリークを用いた上界値計算法を提案する．
本計算法により，大規模な問題例や辺密度の高い問題例に対して
高速に上界値を計算できることを計算実験により確認した．
また，この上界値計算により得られた情報を用いた解法の提案も行う．