ハイパーグラフニューラルネットワークによりMUS列挙を加速
arXiv cs.AI / 2026/4/13
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、CSPにおける最小充足不能部分集合（MUSes）を探索する際の指数的な爆発、特に充足可能性（satisfiability）判定が高コストである場合に焦点を当てる。
- 制約を頂点として表し、これまでに見つかったMUSをハイパーエッジとして扱うことで、段階的に構築されるハイパーグラフに基づいた、ドメイン非依存のMUS列挙戦略を提案する。
- ハイパーグラフニューラルネットワーク（HGNN）に基づくエージェントを強化学習で訓練し、MUSに到達するまでに必要な充足可能性判定（satisfiability checks）の回数を減らすような行動を決定させる。
- 実験により、本手法が従来手法と同じ充足可能性判定の予算内で、より多くのMUSを列挙できることが示される。
- 本研究は、変数—制約の明示的な構造に依存する先行するMLアプローチの限界を乗り越え、従来のBoolean SAT設定にとどまらない点を位置づけている。
