[2N4-OS-17a] AIと制約プログラミング (1)

[2N4-OS-17a-03] 推移関係を表すSAT節の削減

〇越村 三幸¹、廖 暁鵑²、渡部 恵海¹、櫻井 祐子³、横尾 真¹ (1. 九州大学、2. 中国・成都理工大学、3. 産業技術総合研究所)

キーワード：提携構造形成問題、MaxSAT

推移関係は、様々な場面で現れる重要な関係である。推移関係を含む節をSATソルバーを利用して解く場合、推移関係もSAT節に符号化する必要がある。通常の符号化では、問題の規模が大きくなるにつれて、その数は膨大になる。本論文は、このSAT節の削減を目標とする。グラフの頂点間の到達可能性を例に、この推移関係に通常とは異なる解釈を与える。そして、その解釈に基づく節の削減手法を提案する。そして、MC-netsによる提携構造形成問題に提案手法を適用し、削減効果を確認する。