数理計画法を用いた制約充足問題の定式化について検討
スポンサーリンク
概要
- 論文の詳細を見る
制約充足問題は組み合わせ問題を対象としたNP完全問題であることが知られている。このような制約充足問題の代表的な解法としては、探索法や局所近似を用いる方法がある、しかしながら、大規模な問題を取り扱う場合には、このような解法を用いて充足解、特に全解を探索することはほとんど不可能である。そこで、われわれは探索による全解を求めるかわりにひとつの解決を求めるアプローチをとることとし、ここでは最適解を求める数理計画法を用いたアプローチについて検討している。本アプローチでは制約充足問題を整数計画法を用いて定式化し、得られた制約式(条件)を解くことにより(最適)解を求める。本稿では、アプローチの概要について説明する。まず、制約充足問題ならびに数理計画法の一種である整数計画法について触れる。次に、整数計画法を用いた制約充足問題の定式化と具体的な問題を用いた定式化の具体例について説明する。最後に、整数計画法の解法ならびに制約充足問題の充足不能性の判定についても論じる。
- 1992-02-24
著者
関連論文
- ブール代数を用いた制約充足問題の定式化と解法についての検討
- ブール代数を用いた制約充足問題の定式化とその解法について
- 数理計画法を用いた制約充足問題の定式化について検討
- 4Y-7 イントラネット応用電力系統監視制御システム : システム概要とそのメリット(情報システムの構築(1),一般講演,コンピュータと人間社会)
- GHCプログラムの検証と性能評価
- 制約論理型言語を用いたプランニングの記述
- 並列プログラムの動作評価に関する一検討
- モデル生成型定理証明器を用いたアブダクションの計算における効率化手法
- モデル生成に基づく並列アブダクション
- Constraint Programming Languages; Their Specification and Generation, Wm Leler, Addison-Wesley, 1988 (制約論理プログラミング)
- グラフ理論による制約解析および手順生成
- 代数制約の構造情報を用いた幾何定理証明の効率化手法の検討 : グレブナ基底による方法への適用
- 制約処理パターンを用いたオブジェクト思考ソフトウェア開発