多層一般化相互割当問題の定式化とその解法

摘要

本論文では，一般化相互割当問題（GMAP)の従来の定式化と過制約な状況を扱う定式化の齟齬を解消する新しい問題として多層一般化相互割当問題（MLGMAP)を提案する.MLGMAPは，割り当てられない財の数を最小化した上で，効用最大，若しくはコスト最小となる財の割当てを求める問題である.また，MLGMAPを解く手法として2段階最適化手法とペナルティコスト最適化手法を提案し，それぞれに対して既存のプロトコルであるDisLRP-DAとDisLRP-IBFを適用した.提案手法を実験的に評価した結果，ペナルティコスト最適化手法におけるDisLRP-DAが最も有効であるか，ペナルティコストの設定によって，割り当てられない財の数を最小化できる問題例の数と得られる実行可能解の質にトレードオフの関係があることが分かった.