数理計画法を用いた制約充足問題の定式化について検討

情報処理学会

書誌事項

タイトル別名
  • Mathematical Programming Approach to Constraint Satisfaction Problems

この論文をさがす

説明

制約充足問題は組み合わせ問題を対象としたNP完全問題であることが知られている。このような制約充足問題の代表的な解法としては、探索法や局所近似を用いる方法がある、しかしながら、大規模な問題を取り扱う場合には、このような解法を用いて充足解、特に全解を探索することはほとんど不可能である。そこで、われわれは探索による全解を求めるかわりにひとつの解決を求めるアプローチをとることとし、ここでは最適解を求める数理計画法を用いたアプローチについて検討している。本アプローチでは制約充足問題を整数計画法を用いて定式化し、得られた制約式(条件)を解くことにより(最適)解を求める。本稿では、アプローチの概要について説明する。まず、制約充足問題ならびに数理計画法の一種である整数計画法について触れる。次に、整数計画法を用いた制約充足問題の定式化と具体的な問題を用いた定式化の具体例について説明する。最後に、整数計画法の解法ならびに制約充足問題の充足不能性の判定についても論じる。

収録刊行物

  • 全国大会講演論文集

    全国大会講演論文集 第44回 (人工知能及び認知科学), 5-6, 1992-02-24

    情報処理学会

詳細情報 詳細情報について

問題の指摘

ページトップへ