情報処理学会 第81回全国大会講演要旨

本稿では，MC-netsのルール集合で記述された提携形ゲームの利得分配問題に対し，代表的な解概念の一つである最小コアを求める新しいアルゴリズムを提案する．この問題に対して，従来，単一制約生成法に基づくアルゴリズムが提案されており，そこでは，最大不満の最小値の下界を与える利得ベクトルを求める線形計画問題と，その利得ベクトルに対して最大不満をもつ1つの提携とその不満の値である上界を求める01整数計画問題が，それらの上下界値が一致するまで繰り返し解かれる．本稿では，この繰り返しにおける下界計算をより効果的に行う複数制約生成法を提案し，単一制約生成法に基づく従来アルゴリズムと比較する．