[2M4-OS-11b] AIと制約プログラミング

[2M4-OS-11b-04] 外部性が存在する提携構造形成問題のためのMaxSAT符号化の改良

木下 春斗¹、〇櫻井 祐子¹、越村 三幸²、横尾 真² (1. 名古屋工業大学、2. 九州大学)

キーワード：協力ゲーム、提携構造形成問題、MaxSAT

提携構造形成問題は、提携値の和が最大化されるようにエージェントの提携を決定する問題であり、様々なアルゴリズムが提案されている。我々は、提携間に外部性が存在する提携構造形成問題に対して、従来提案されているMaxSAT符号化よりも効率的に求解可能にするための改良を提案する。計算機実験により、従来手法と比較してCPU計算時間の削減が可能になることを示す。