[4F1-OS-8a] AIと制約プログラミング(1/2)

[4F1-OS-8a-04] R-MaxSAT : 敵対者が存在する MaxSAT

山下 魁人¹、〇菅原 知也¹、越村 三幸¹、横尾 真¹ (1. 九州大学)

キーワード：MaxSAT、クリーク分割問題、頑健な解

本論文では，Robust MaxSAT (R-MaxSAT) の一般化である，Robust weighted Partial MaxSAT (R-PMaxSAT) を提案する．
R-PMaxSAT における意思決定者は，充足する節の重みの和を最大化する割当を探索することを目的とする．
一方で，R-PMaxSAT における敵対者は，意思決定者が決定した割当に対して，定数個以下のブール変数の割当を変更可能である．
そのため，意思決定者が決定した割当は，敵対者による攻撃に対して頑健な必要がある．
この問題の決定問題版は Sigma2P 完全であると証明されている．
また，R-PMaxSAT は，敵対者が存在する場合の Clique Partitioning Problem (CPP) である robust CPP を表現できるため，多くの現実的なモデルに応用可能である．
本論文では，SAT ソルバー，QBF ソルバーをサブルーチンとして利用し，R-PMaxSAT の最適解を与える 2 種類のアルゴリズムを提案する．
計算機実験において，提案したアルゴリズムを利用することで，現実的な時間の下で最適解を導出可能であることを示した．