大型疎線形計画問題に対する Reid の基底更新方法の改善
スポンサーリンク
概要
- 論文の詳細を見る
大型の線形計画問題の基底行列は一般に疎な構造をしており,計算機の記憶容量や処理能力などの制約のもとで正確かつ高速に問題を解くためには,基底更新の際にその疎な性質をいかに保持するかが重要な問題となる.この問題に対して,R.H.Bartels とG.H.Golub は,基底行列を三角分解して保存しておく方法を提案した.その後J.K.Reid により計算時間と計算精度の両方の点で優れた方法へと改良され,標準的な数理計画法コードとして有名なスタンフォード大学の MINOS コードに取り入れられるようになった. Reid の方法(以下, Reid 法と略す)は,基底行列の疎な,性質をできる限り保持するために,基底更新の際に行および列の置換操作を行ってバンプと呼ばれる正方部分行列を縮小し,フィル・インの直接的な原因となる消去をなるべく少なくする効率の良い方法である.本論文では, Reid 法におけるバンプ縮小の基本的性質を明らかにし,その性質を利用してバンプ縮小の効率改善を図った改良 Reid 法を提案する.また,改良 Reid 法と Reid 法の間のバンプ縮小効率の関係を明らかにする.そして, Reid の用いた例題とランダム線形計画問題を用いた数値実験により改良 Reid 法の有効性を検討する.その結果,大型疎線形計画問題に対して改良 Reid 法が Reid 法よりも有効であることが確認された.
- 1991-09-15
著者
関連論文
- 協調フィルタリングに基づく推薦システムにおける格付け寄与度の提案(インタラクション/インタフェース応用,ソフトウェアエージェントとその応用論文)
- ユーザ間・アイテム間協調フィルタリングの適応的な融合手法 : MovieLensでの格付けデータに基づく検証(社会システムと知能)
- 小型自律飛行船シミュレーションの実装及び効果検証
- 5ZA-8 地震災害関連情報の分析に基づく風評被害対策に関する考察(防災と情報,学生セッション,コンピュータと人間社会)
- 2-S-9 新潟中越沖地震における風評被害対策と売上推移(観光とOR(2))
- 2-S-10 メディアの動向を意識した風評被害対策に関する考察(観光とOR(2))
- 2-S-11 自然災害における近隣観光地の風評被害 : モデル、被害度指標、災害ポータル(観光とOR(2))
- N-016 風評被害対策に向けた話題分析に関する基礎研究(教育・人文科学,一般論文)
- 5H-4 風評被害の抑制・防止に向けた地震災害情報の分析(危機管理情報システム,一般セッション,コンピュータと人間社会)
- 待ち行列ネットワークにおける最適成長計画問題とその解法
- エージェントの意思を取り入れた混雑情報の提示とその効果(セッション : 社会システムと知能(群ユーザモデルと知的支援), 「社会システムにおける知能」及び一般)
- エージェントの意思を取り入れた混雑情報の提示とその効果(社会システムと知能(群ユーザモデルと知的支援), 「社会システムにおける知能」及び一般)
- テーマパーク問題における混雑状況の提示とその効果(社会システムにおける知能 : 実環境におけるマルチエージェント社会)
- テーマパーク問題における混雑状況の提示とその効果(社会システムにおける知能(実環境におけるマルチエージェント社会))(「社会システムにおける知能」及び一般)
- 大型疎線形計画問題に対する Reid の基底更新方法の改善
- 数理モデルによるDNAメモリの容量解析
- Iterated Multiple Lake Gameにおける社会的ジレンマに対するプレイヤー群の挙動に関する考察
- X-Economyシステムによる電力市場のモデル化とその実装
- LF-006 セルの入出力観測に基づくセルオートマトンの定量的分析(人工知能・ゲーム)
- ブログによる情報収集と推薦技術を用いた飲食店情報サイトの構築(セッション7:ウェブにおける情報処理)
- ブログによる情報収集と推薦技術を用いた飲食店情報サイトの構築(セッション7:ウェブにおける情報処理,社会システムと知能)
- 集合行為問題におけるタグメカニズムと協調の形成に関する考察
- 郡市医師会におけるテレビ会議システム導入可能性の検討 : 北海道医師会をモデルとした費用効果の試算
- 遺伝子概念学習のための支援ツールに関する検討
- 概念学習に対する遺伝的アルゴリズムの局所探索に関する考察
- 帰納と対話の併用による概念知識ベースの構築
- 遺伝的アルゴリズムを用いた概念学習に関する考察
- 遺伝的アルゴリズムによる選言概念獲得アルゴリズム
- GAによる Neural Network の段階的生成と応用
- Davis-Putnam の手続きにおける分枝変数選択規則の提案
- ユーザ間・アイテム間協調フィルタリングの適応的な融合手法 : 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システムによる実現
- 強化学習を用いた小型飛行船の目標位置への誘導
- エージェントモデルによるユーザ間とアイテム間協調フィルタリングの性能評価
- 利用者主導による主観と客観を考慮した個人向け観光情報推薦システム
- F-007 ブログを用いたWebサービス型情報共有・推薦システム「HARMO」の開発(F分野:人工知能・ゲーム)
- L_057 Weblogによる評価情報収集と推薦システムの開発(L分野:ネットワークコンピューティング)
- FISMによる集団合意形成支援 : 新規事業開発への利用(集団合意形成支援工学)
- AFOによる鬼ごっこ(セッション2 物理)
- 屋内自律飛行船における自己組織的な群飛行(「社会システムにおける知能」および一般)
- 屋内自律飛行船における自己組織的な群飛行(一般,「社会システムにおける知能」および一般)
- 小型自律飛行船の研究プラットホームの実現
- J_050 充電地点へのドッキングを行なう室内バルーンロボットの学習制御(J分野:グラフィクス・画像)
- 室内バルーンロボットにおける自律充電のドッキング制御(エンタテインメントコンピューティング一般(1))
- 2P1-S-059 超音波センサを搭載した室内バルーンロボットにおけるトポロジカルマップの自動生成(飛行ロボット4,生活を支援するロボメカ技術のメガインテグレーション)
- ホバリング制御に基づくエンタテインメントバルーンロボットの開発(エンタテインメントコンピューティング)
- カメラ搭載型バルーンロボットシステムの開発とPD制御による位置制御の実現(応用分野・領域)
- 部分的完全調査モンテカルロ法の推定精度の検証と閾値の自動設定(アルゴリズム理論)
- 個人適応型観光情報収集支援システムのためのユーザモデルの構築(統合オペレーション(1))
- 北海道観光情報ポータルサイトにおけるユーザモデルの構築(統合オペレーション(2))
- 4ZB-5 協調コミュニケーションからの概念地図の自動生成に関する考察(情報/知識共有,一般講演,インタフェース)
- 3B-5 AHPにおける比較支援法(数理モデルとシミュレーション,一般セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- テーマパーク問題における予定情報共有システムの提案と有効性の検証(セッション1:社会システムと強調)
- テーマパーク問題における予定情報共有システムの提案と有効性の検証(セッション1:社会システムと強調,社会システムと知能)
- コージェネレーションの普及が電力市場の価格形成に与える影響に関するマルチエージェント分析
- 電力市場における分散型電源普及の影響に関するマルチエージェント分析(社会システムにおける知能 : エージェントと社会基盤)
- 部分的全調査モンテカルロ法による不確実性を考慮した行動評価関数の設計とTACへの適用(社会システムにおける知能 : マルチエージェントデザイン)
- 電力市場における分散型電源普及の影響に関するマルチエージェント分析(社会システムにおける知能(エージェントと社会基盤))(「社会システムにおける知能」及び一般)
- 部分的全調査モンテカルロ法による不確実性を考慮した行動評価関数の設計とTACへの適用(社会システムにおける知能(マルチエージェントデザイン))(「社会システムにおける知能」及び一般)
- テーマパーク問題の提案と調整アルゴリズムの検討 : ユビキタス環境における群ユーザ支援の実現へ向けて(サービス・サービスイメージ)
- 学習エージェントを導入した人工市場における均衡価格の検証