大型疎線形計画問題に対するReidのバンプ縮小方法の基本的性質
スポンサーリンク
概要
- 論文の詳細を見る
大型の線形計画問題の基底行列は一般に疎な構造をしており,計算機の記憶容量や処理能力などの制約のもとで正確かつ高速に問題を解くためには,基底更新の際にその疎な性質をいかに保持するかが重要な問題となる.この問題に対して,1969年にR.H.BartelsとG.H.Golubは,基底行列を三角分解して保存しておく方法を提案した.その方法は,基底の逆行列を積形式にして保存する方法と比較すると,元問題の疎な性質を十分生かすことが可能で,計算時間や記憶容量の点で優れたものである.R.H.BartelsとG.H.Golubの発表以来,多くの研究者によりこの方法の改良が行われてきた.その中でJ.K.Reidによる改良は,計算時間および計算精度の両方の点で優れたものであり,標準的な数理計画法コードとして有名なスタンフォード大学のMIN0Sコードにも取り入れられている.Reidの方法(以下,Reid法と略す)は,基底行列の疎な性質をできる限り保持するために,基底更新の際に行および列の置換操作を行って基底行列中のバンプと呼ばれる正方部分行列を縮小し,フィル・インの直接的な原因となる消去をなるべく少なくする効率の良い方法である.本論文では,Reid法における行および列の置換操作によるバンプ縮小の基本的性質を明らかにする。
- 1990-09-04
著者
関連論文
- 協調フィルタリングに基づく推薦システムにおける格付け寄与度の提案(インタラクション/インタフェース応用,ソフトウェアエージェントとその応用論文)
- ユーザ間・アイテム間協調フィルタリングの適応的な融合手法 : MovieLensでの格付けデータに基づく検証(社会システムと知能)
- 小型自律飛行船シミュレーションの実装及び効果検証
- 5ZA-8 地震災害関連情報の分析に基づく風評被害対策に関する考察(防災と情報,学生セッション,コンピュータと人間社会)
- 2-S-9 新潟中越沖地震における風評被害対策と売上推移(観光とOR(2))
- 2-S-10 メディアの動向を意識した風評被害対策に関する考察(観光とOR(2))
- 2-S-11 自然災害における近隣観光地の風評被害 : モデル、被害度指標、災害ポータル(観光とOR(2))
- N-016 風評被害対策に向けた話題分析に関する基礎研究(教育・人文科学,一般論文)
- 5H-4 風評被害の抑制・防止に向けた地震災害情報の分析(危機管理情報システム,一般セッション,コンピュータと人間社会)
- 待ち行列ネットワークにおける最適成長計画問題とその解法
- エージェントの意思を取り入れた混雑情報の提示とその効果(セッション : 社会システムと知能(群ユーザモデルと知的支援), 「社会システムにおける知能」及び一般)
- エージェントの意思を取り入れた混雑情報の提示とその効果(社会システムと知能(群ユーザモデルと知的支援), 「社会システムにおける知能」及び一般)
- テーマパーク問題における混雑状況の提示とその効果(社会システムにおける知能 : 実環境におけるマルチエージェント社会)
- テーマパーク問題における混雑状況の提示とその効果(社会システムにおける知能(実環境におけるマルチエージェント社会))(「社会システムにおける知能」及び一般)
- 大型疎線形計画問題に対する Reid の基底更新方法の改善
- 大型疎線形計画問題に対するReidのバンプ縮小方法の基本的性質
- 数理モデルによるDNAメモリの容量解析
- Iterated Multiple Lake Gameにおける社会的ジレンマに対するプレイヤー群の挙動に関する考察
- X-Economyシステムによる電力市場のモデル化とその実装
- LF-006 セルの入出力観測に基づくセルオートマトンの定量的分析(人工知能・ゲーム)
- ブログによる情報収集と推薦技術を用いた飲食店情報サイトの構築(セッション7:ウェブにおける情報処理)
- ブログによる情報収集と推薦技術を用いた飲食店情報サイトの構築(セッション7:ウェブにおける情報処理,社会システムと知能)
- 集合行為問題におけるタグメカニズムと協調の形成に関する考察
- 郡市医師会におけるテレビ会議システム導入可能性の検討 : 北海道医師会をモデルとした費用効果の試算
- 遺伝子概念学習のための支援ツールに関する検討
- 概念学習に対する遺伝的アルゴリズムの局所探索に関する考察
- 帰納と対話の併用による概念知識ベースの構築
- 遺伝的アルゴリズムを用いた概念学習に関する考察
- 遺伝的アルゴリズムによる選言概念獲得アルゴリズム
- GAによる Neural Network の段階的生成と応用
- ユーザ間・アイテム間協調フィルタリングの適応的な融合手法 : MovieLensでの格付けデータに基づく検証(社会システムと知能)
- X-Economyシステムによる電力市場のモデル化とその実装
- 抗原抗体反応のモデル化と挙動に関する基礎研究
- 抗原抗体反応の細胞モデルに関する基礎研究
- 時間制約付き飛行プランに基づく小型自律飛行船制御
- 待ち行列ネットワークにおける最適成長計画問題とその解法
- 待ち行列ネットワークにおける待ち時間を最小化する構造設計(ネットワーク品質・制御)
- 待ち行列ネットワークにおけるリンク張り替えによる構造最適化(セッション9:ネットワークと知能)
- 成長する待ち行列ネットワークにおけるトポロジー生成規則の最適性(ネットワークが創発する知能)
- 2-F-1 待ち行列ネットワークの複雑ネットワーク理論を用いた最適設計(情報・通信)
- リンクコストを考慮しない待ち行列ネットワークの最適設計(セッション1: ネットワーク)
- リンクコストを考慮しない待ち行列ネットワークの最適設計(ネットワーク, 「社会システムにおける知能」及び一般)
- 待ち行列ネットワークにおけるリンク張り替えによる構造最適化(セッション9:ネットワークと知能,社会システムと知能)
- アートツーリズムを支援するコミュニティWebの構築(セッション : 一般(知識処理), 「社会システムにおける知能」及び一般)
- アートツーリズムを支援するコミュニティ Web の構築(一般(知識処理), 「社会システムにおける知能」及び一般)
- 組織評価における能力成熟度モデルの適用 : 観光関係部局の調査結果について(社会・人間系の情報システム)
- BSC戦略マップ構造モデリングに基づく観光戦略策定の検討(社会システムにおける知能 : 社会システムのモデル化)
- BSC戦略マップ構造モデリングに基づく観光戦略策定の検討(社会システムにおける知能(社会システムのモデル化))(「社会システムにおける知能」及び一般)
- 北海道観光に関する情報収集とニーズ調査 : WWWを利用した情報提供の現状(データマイニング)
- 観光情報に関する概念形成セッションの提案と考察(統合オペレーション(4))
- 北海道「遊」産業情報におけるWebマイニング(統合オペレーション(3))
- 観光情報に関する概念形成のためのWWW文書の可視化方法の検討
- 観光情報に関する概念形成のためのWWW文書の可視化方法の検討
- 参加者の匿名性を考慮したCPUリソースオークションシステムの提案(セッション : 社会システムと知能(複雑系とオークション), 「社会システムにおける知能」及び一般)
- 参加者の匿名性を考慮したCPUリソースオークションシステムの提案(社会システムと知能(複雑系とオークション), 「社会システムにおける知能」及び一般)
- キーワード地図構造モデリングによるグループ学習支援システムの構築
- 推薦と格付けの相互作用に基づく推薦アルゴリズムの性能評価
- 郡市医師会情報化実態指標の構築
- ファジィ構造モデリングにおける階層グラフを用いた構造化法
- FISM/fuzzyによるレパートリー : グリッドを用いたファジィ構造モデリング
- 最適系列分割問題への遺伝的アルゴリズムの適用 : 個体の形質遺伝に関する考察
- 2T05 ゲノム情報処理におけるコピーパターンの抽出と解析
- 2T03 同時双方向探索によるアミノ酸配列の多重アラインメント
- 推移的矛盾を利用したファジィ構造モデリング
- 遺伝情報の統合処理支援モジュールの構築
- 認知構造を利用した画像検索システム
- 総合成績を考慮したクラス編成法に関する一考察
- 配送計画,問題における近傍解の考察
- 順序尺度に基づく階層分析法
- 国際貿易リーグ : マルチエージェント経済における標準問題(1) : 概念とX-Economyシステムによる実現
- 国際貿易リーグ : マルチエージェント経済における標準問題(1) : 概念とX-Economyシステムによる実現
- 強化学習を用いた小型飛行船の目標位置への誘導
- エージェントモデルによるユーザ間とアイテム間協調フィルタリングの性能評価
- 命題論理充足可能性問題に対する定量的アプローチと記号的アプローチの比較
- 変数上下限制約付き全整数計画問題に対する陰的列挙法の効率改善について
- 有理数演算による小数法の実現と数値実験
- 代理制約式を用いた陰的列挙法の効率化に関する数値実験
- 擬似乱数を用いたランダム電信信号の発生方法とその評価
- Walker法に準拠した指数乱数を用いた指数型ランダム信号の発生
- パソコン用LPソフト「LP-Calculator」 : 昭和62年度日本OR学会・事例研究奨励賞・ソフトウェア部門受賞作品
- β節充足可能性問題の解法についての考察
- 部分例示に基づく定理自動証明
- β節集合に対するDavis-Putnamの手続きの一般化
- 部分例示手法に基づく充足可能性判定手続き
- 部分例示手法に基づいた定理自動証明手続き
- IEMSATアルゴリズムの実験的評価
- 陰的列挙法に基づくβ SATアルゴリズム
- 命題論理におけるβ節充足可能性問題とその解法
- 陰的列挙法に基づく SAT アルゴリズム
- 部分例示手法に基づいた述語論理式の充足可能性判定手続き
- SATに対する陰的列挙法とDavis-Putnamの方法の関係について
- FISM/KJの理論的枠組み(モデリング)
- 命題論理充足可能性問題に対する定量的アプローチ(AIとOR)
- 充足可能性問題に対するJeroslowの手法の拡張
- 充足可能性問題の0-1整数計画問題への定式化と計算効率
- 論理推論に対する定量的方法 : 枠組と適用可能性
- 単体法の並列処理に関する基礎的検討
- 大型疎線形計画問題の基底の三角分解更新に対する改良Reid法の提案(LP単体法)
- 有理数演算によるゴモリーの小数法の基礎的検討
- 帯行列を係数行列とする連立一次方程式を誤差なく計算する場合のLU分解について