大型疎線形計画問題に対するReidの基底更新方法の改善

• Item type: Journal(1)
• 公開日: 1991-09-15
• タイトル: 大型疎線形計画問題に対するReidの基底更新方法の改善
• タイトル / 言語: en
• タイトル: On Improvement of Reid's Basis Updating Method for Large Sparse Linear Programming Problems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 基礎
• 著者所属: 北海道大学工学部情報工学科
• 著者所属: 北海道大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Imformation Engineering, Faculty of Engineering, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Department of Imformation Engineering, Faculty of Engineering, Hokkaido University
• 著者名: 大柳, 俊夫; 大内, 東
• 著者名(英): Toshio, Ohyanagi; Azuma, Ohuchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 大型の線形計画問題の基底行列は一般に疎な構造をしており 計算機の記憶容量や処理能力などの制約のもとで正確かつ高速に問題を解くためには 基底更新の際にその疎な性質をいかに保持するかが重要な問題となるこの問題に対して RHBartels とGHGolub は 基底行列を三角分解して保存しておく方法を提案したその後JKReid により計算時間と計算精度の両方の点で優れた方法へと改良され 標準的な数理計画法コードとして有名なスタンフォード大学の MINOS コードに取り入れられるようになった Reid の方法(以下 Reid 法と略す)は 基底行列の疎な 性質をできる限り保持するために 基底更新の際に行および列の置換操作を行ってバンプと呼ばれる正方部分行列を縮小し フィル・インの直接的な原因となる消去をなるべく少なくする効率の良い方法である本論文では Reid 法におけるバンプ縮小の基本的性質を明らかにし その性質を利用してバンプ縮小の効率改善を図った改良 Reid 法を提案するまた 改良 Reid 法と Reid 法の間のバンプ縮小効率の関係を明らかにするそして Reid の用いた例題とランダム線形計画問題を用いた数値実験により改良 Reid 法の有効性を検討するその結果 大型疎線形計画問題に対して改良 Reid 法が Reid 法よりも有効であることが確認された
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 32, 号 9, p. 1057-1064, 発行日 1991-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764