有理数演算によるゴモリーの小数法の基礎的検討
スポンサーリンク
概要
- 論文の詳細を見る
全整数計画問題 (IP問題) の解法である Gomory の小数法は,カットと呼ばれる制約式を有限個加えて最適解を得ることを保証した方法である.しかし,この方法を浮動小数点演算を用いてインプリメントした場合,最適解が得られないことが頻繁に起こることが知られており,この方法の有効性については多くの研究者が否定的な意見である.最適解が得られない理由は,桁落ちや丸め誤差と考えられているが,そのことを明らかにした報告は見当らないまた,桁落ちや丸め誤差を排除し,理論どおりにインプリメントした場合の小数法の振舞いについても明らかにされていない.桁落ちと丸め誤差を排除する演算としては有理数演算がある.この演算は,計算機の性能の制約から今まではほとんど用いられていなかったが,最近の計算機の急速な進歩により次第に利用可能となりつつある.本論文は,有理数演算を用いて小数法をインプリメントし,(1)桁落ちと丸め誤差を排除した場合の小数法の振舞い,(2)浮動小数点演算を用いた場合に生じる桁落ちと丸め誤差の結果への影響,(3)カットの生成・除去方法の違いによる小数法の効率の違い,を調べたものである.その結果,小数法に特有の性質と浮動小数点演算による桁落ちと丸め誤差の影響を明らかにした.また,カット生成・除去方法の検討を行い,有効と考えられる除去方法を示した.
- 一般社団法人情報処理学会の論文
- 1990-05-15
著者
関連論文
- 協調フィルタリングに基づく推薦システムにおける格付け寄与度の提案(インタラクション/インタフェース応用,ソフトウェアエージェントとその応用論文)
- ユーザ間・アイテム間協調フィルタリングの適応的な融合手法 : 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分解について