並列分枝限定法による混合整数計画問題解法(組合せ最適化(3))
スポンサーリンク
概要
- 論文の詳細を見る
運転計画問題,施設配置問題,生産計画問題などは,一般に混合整数計画法によって定式化される.混合整数計画法は分枝限定法によって解かれる.分枝限定法は問題の構造を生かした下界値計算,分枝変数選択,部分問題求解手法の工夫,あるいはヒューリステイクスの導入など,計算の効率化に向けた研究が盛んであり,数理モデリング技術の進歩や計算機性能の向上とあいまって,混合整数計画問題の実務レベルへの応用の可能性を拡げている.しかし,本質的に分枝限定法は組みあわせの列挙を伴う数え上げアルゴリズムであるため,しばしば問題規模が大きくなると,計算量が爆発し,現実的な時間内では解を得ることができないという状況が生じる.この状況を改善する一つの方策として古くから提案されているのが,分枝限定法の並列性に着目した並列化である.分枝限定法では列挙された子問題は通常リストに蓄積され,それぞれについて・下界値計算・限定操作・分枝変数の選択と分枝操作なる処理が行われることになるが,リストに蓄積されたすべての部分問題についてこの処理が独立に実行できることに着目すれば並列化が可能である.本稿では,汎用パッケージであるUNOPTを用いた分枝限定法の並列化について,その実装を実験結果を報告する.
- 社団法人日本オペレーションズ・リサーチ学会の論文
- 2001-09-12
著者
関連論文
- 1-B-7 ラグランジュ緩和法を用いた土木構造物の長期修繕計画における予算平準化問題の汎用解法(離散最適化(2))
- GISへの空間的最適化エンジンの組込開発
- 2-D-17 数式表現によらない関数の制約付き最適化(連続最適化)
- 2-E-6 主双対内点法の加速について(線形計画)
- 大規模かつ複雑な非線形システムの最適化-その現状(ここまで使える数理計画法)
- 2-A-7 主双対外点法の超1次収束性とパラメトリック最適化への応用(非線形最適化(2))
- 1-B-12 主双対外点法とそのパラメトリック最適化への応用(数理計画(1))
- 計算グラフと分枝限定法を利用した大域的最適化-2(非線形計画(2))
- 計算グラフと分枝限定法を利用した大域的最適化(線形計画)
- NUOPTを用いた大規模DEAプログラムの開発(DEA(1))
- 並列分枝限定法による混合整数計画問題解法(組合せ最適化(3))
- 大規模混合整数2次計画問題の解法の実装(組合せ最適化(2))
- 数理計画のためのモデリング言語SIMPLE I 概要(数理計画(1))
- 数理科学のためのモデリング言語SIMPLE
- 1-D-9 メタヒューリスティクスアルゴリズムの性質を用いた実務的な0-1整数計画問題の高速な解法(離散アルゴリズム(3))
- 高信頼性CAE解析ソフト開発のためのインテリジェント化・高精度化(自動車産業における数値シミュレーションに必要な設計品質保証体系の理念的研究 報告(3),シミュレーションにおけるSQCの貢献-シミュレーションとSQC研究会の成果をもとに)
- 2-1 拡大計画研究会 第4分科会 中間報告(第3報) : 高信頼性CAEの技術要素:インテリジェント化・高精度化(その1)(2.研究発表会の要旨,(社)日本品質管理学会 第36回年次大会)
- GMPLS波長パス収容計画における一括最適型と逐次最適型の比較評価
- GMPLS波長パス収容計画における一括最適型と逐次最適型の比較評価
- 3-6 CAEの要素技術の融合と発展 : スケジューリング問題へのアプローチ(4.研究発表会の要旨,(社)日本品質管理学会 第80回研究発表会)
- 重み付き制約充足アルゴリズムを用いたGMPLS波長パス収容計画手法(MPλ(Lambda)S,フォトニックネットワーク/制御,光波長変換,スイッチング,PON,一般)
- 1-A-1 メタヒューリスティクスを用いた現実的なスケジューリング問題へのアプローチ(離散最適化(1))
- 4-7 自動車開発設計の高品質保証"Total Intelligence CAE Management Model"の研究 : 拡大計画研究会「シミュレーションとSQC」4分科会中間報告(2)(3. 研究発表会の要旨, (社)日本品質管理学会 第35回年次大会)
- メタヒューリスティクスアルゴリズムのための計算グラフを用いた関数評価の効率的実装(アルゴリズム)
- Bioinformaticsとソフトウエア (符号と暗号の代数的数理)
- 添字付き計算グラフを用いた自動微分の実装(非線形計画法)
- 非線形計画法アルゴリズムの実装と応用(数理計画の理論と実装)
- 1320 数理計画法パッケージ NUOPT による大規模非線形最適化
- 大規模な非線形最適化問題に対する主双対内点法について(線形計画・非線形計画(3))
- 大規模な非線形最適化問題に対する主双対内点法について(数値計算アルゴリズムの研究)
- 大規模非線形最適化パッケージNUOPT2.0の開発 : II.インプリメンテーション(非線形最適化(1))
- 大規模非線形最適化パッケージNUOPT2.0の開発 : I.アルゴリズム(非線形最適化(1))
- 大規模数理計画問題に対する内点法の並列化とアプリケーション(最適化(3))
- 非線形計画法アルゴリズムの実装と応用(数理計画の理論と実装)
- (3)並列分枝限定法の実装(アルゴリズムと最適化)(研究部会報告)
- NUOPTによる数理計画法 : モデリング・ソリューション
- 計画業務の一元化を目指した統合生産計画システム(LP解分析機能)(生産・在庫(1))
- 2K-8 計画業務の一元化を目指した統合生産計画システム : LP解分析機能
- 数理計画のためのモデリング言語SIMPLE II 応用(数理計画(1))
- システムのモデリングのための言語 : SIMPLE(数値計算アルゴリズムの現状と展望II)
- 実務的な意思決定問題への数理計画法を用いたアプローチ(最適化技術の深化と広がり)
- 実務的な意思決定問題への数理計画法を用いたアプローチ
- 2-B-2 ナース・スケジューリングにおける部分問題解空間の把握(スケジューリング(1))
- 1-C-2 LNG基地におけるタンクオペレーション計画導出支援システム(在庫管理)
- 最適化モデリングの実際(現場と理論の対話)
- 1-D-1 取引コストを考慮した最適資産配分問題に対するDFOによるモデル化(特別セッション 金融工学(1))