最小矛盾の概念を用いた混合 0-1 整数計画問題の近似解法
スポンサーリンク
概要
- 論文の詳細を見る
混合0-1整数計画問題は, 長くオペレーションズリサーチの分野で研究されてきた重要な問題であるが, 一般にNP-completeであり厳密に解くことは難しい. 本論文では, 混合0-1整数計画間題に対する新しい近似解法を提案する. 本手法では, 0-1変数に対して近傍探索を行い, 連続変数に対しては, シンプレックス法を用いて最適化を行う. 近似探索の特長は最小矛盾の概念を用いる点である. 最小矛盾は, 制約違反を引き起こすような最小の仮説の集合である. 最小矛盾を用いることによって, 近傍探索を効率良く実行でき, また局所最適の間題も生じない. 本手法を典型的な混合0-1整数計画問題である多品種生産計画間題に適用し, 分技限定法や従来のヒューリスティクス手法と比較し, 本手法の有効性を示した.
- 一般社団法人情報処理学会の論文
- 1994-12-15
著者
関連論文
- 業務の可視化を行うBPM基盤の試作(業務分析・仕様記述)
- 仮定に基づく組み合わせ最適化手法
- 生産計画問題におけるスケジューリング方式
- 制約充足問題における制約緩和法を用いた最適化
- スケジューリング問題における探索方式
- 企業モデルに基づく分散協調作業支援システムの試作
- 分散共同開発支援環境の開発(3) : ツール統合
- 分散共同開発支援環境の開発(2) : アーキテクチャ
- 分散共同開発支援環境の開発(1) : 概要
- SOAの現状と展望
- 時間概念の表現とデフォルト推論
- 最小矛盾の概念を用いた混合0-1整数計画問題の近似解法
- 交渉による多目的計画問題の解法
- クリティカルパスの保存によるジョブショップスケジューリングの近似解法
- 最小矛盾の概念を用いた混合0-1整数計画問題の近似解法 (「数理計画法と人工知能技術の融合」)
- CAIA-92
- 最小矛盾の概念を用いた混合 0-1 整数計画問題の近似解法