有理数演算による小数法の実現と数値実験
スポンサーリンク
概要
- 論文の詳細を見る
一般に,線形計画問題(LP問題)の変数すべてに整数条件を加えたものを全整数計画問題(ILP問題)といい,この問題の解法の一つにR.Gomoryによる小数法がある.この方法は,まずILP問題の変数の整数条件を除いたLP緩和問題を解き,つぎにその解をもとにすべての変数が整数になるまでカットと呼ばれる新しい制約を加えながら繰返しLP問題を解くもので,(1)最適解を得るまでは実行可能解が1つも求まらない (2)一般に,最適解を得るまでに多くのカットを必要とし,浮動小数点演算では丸め誤差が蓄積され,いくらカットを加えても最適解が得られないことや,間違った解が得られることがしばしば起るという特徴がある.そのため,この方法の汎用のアルゴリズムとしての実用性に関しては否定的な意見が大多数で,特に(2)の特徴のため,現在までこの方法に関する厳密かつ詳細な数値実験の報告はほとんど見当らない.本稿は,小数法を有理数演算を使って実現し,この方法の有効性を厳密に調べるために行った数値実験について述べるものである.今回の実験は,種々の問題に対してカットの生成方法や除去方法を変え,最適解を得るまでに加えたカット数を調べたものである.
- 一般社団法人情報処理学会の論文
- 1989-03-15
著者
関連論文
- 大型疎線形計画問題に対する Reid の基底更新方法の改善
- 大型疎線形計画問題に対するReidのバンプ縮小方法の基本的性質
- ゴール群に基づく並列論理型言語の情報資源管理方式
- LISP上のGHC コンパイラ
- 外部磁場に斜め伝播するプラズマ波 : プラズマ物理
- 計算機言語の構造解析と複雑度評価
- 可到達行列モデルのスケルトン行列更新アルゴリズム
- 可到達行列モデルの修正理論とアルゴリズム
- ISMにおける一般化完全推論行列の理論
- メンテナンス時間を考慮したエネルギ-評価による最適炉停止制御
- マルコフ連鎖による1段階ループ型自動生産システム機械部の特性解析
- マルコフ連鎖による1段階トランスファ型自動生産システムの解析--2機械並列システム
- マルコフ連鎖によるトランスファ型自動生産システムの解析--1段階2機械モデル
- 弱連結成分抽出によるグラフ理論的クラスター分析アルゴリズムの検討
- データ処理のためのミニコンピュータのプログラミング
- 3a-R-8 プラズマ物理実験のためのデータ処理装置
- 上下限変数制約付き凸計画問題に対する座標軸成分毎最小化法の収束証明
- 自動推論によるディジタル回路故障診断
- 最小平均メディアン基準に従ったサイクル・グラフ上の施設配置問題
- 待ち台数と待ち回数を制限したPRTにおける車両待ち時間
- 命題論理充足可能性問題に対する定量的アプローチと記号的アプローチの比較
- 知識構造モデリング法の構成と具象化ルール
- スイッチング回路における互換グラフの決定問題とアルゴリズム
- 置換ネットワ-ク上の互換操作について
- Automated Reasoningに基づくシステム問題へのアプロ-チ (産業分野におけるエキスパ-トシステム)
- 2項関係理論による知識獲得ツ-ルとしての階層構造分析法の構成 (産業分野におけるエキスパ-トシステム)
- d互換ブロックからなる置換ネットワークとその互換アルゴリズムについて
- 個別軌道システムのネットワーク・シミュレータ
- ISMにおける推論構造と推論アルゴリズム
- ISMの推移的結合における完全推論行列の考察
- ISMにおける推移的具象化の一般化
- 0-1整数計画問題に関する教育用プログラミング計画
- ネットワーク計画問題プログラミングのための拡張ソフトウェア・ツールについて
- ネットワーク問題プログラミングを支援するソフトウェア・ツール(ORの計算環境)
- B&Bによる最適系列分割問題における改善と拡張
- Branch-and-Bound法によるグラフの最適系列分割問題(グラフ・ネットワーク)
- グラフの最適系列分割アルゴリムの改善
- 変数上下限制約付き全整数計画問題に対する陰的列挙法の効率改善について
- 有理数演算による小数法の実現と数値実験
- ファジ-ISMの具象化フェ-ズにおける相互関連行列の効率的生成アルゴリズム
- 知識構造モデリング法のPrologによる設計と試作
- 代理制約式を用いた陰的列挙法の効率化に関する数値実験
- 擬似乱数を用いたランダム電信信号の発生方法とその評価
- Walker法に準拠した指数乱数を用いた指数型ランダム信号の発生
- 超計量行列に対する一考察
- パソコン用LPソフト「LP-Calculator」 : 昭和62年度日本OR学会・事例研究奨励賞・ソフトウェア部門受賞作品
- FISM/KJの理論的枠組み(モデリング)
- 命題論理充足可能性問題に対する定量的アプローチ(AIとOR)
- 充足可能性問題に対するJeroslowの手法の拡張
- 充足可能性問題の0-1整数計画問題への定式化と計算効率
- 論理推論に対する定量的方法 : 枠組と適用可能性
- 単体法の並列処理に関する基礎的検討
- 28a-Y2-14 円柱プラズマの周りのフォース・フリー磁場の安定性
- 擬順序関係の含意を求める効率的アルゴリズム
- 2次費用関数のHitchcock型輸送問題の解法
- 2次目的関数の最適配分問題の考察とそのアルゴリズム
- 最小停止時間, 出力制約及び起動費を考慮した生産・在庫システムの一考察と揚水発電所を含む電力系統への一応用
- 表面電流円柱状プラズマに対するForce-Free磁場の安定化効果-2-
- 格子グラフに関するいくつかのロケ-ション問題
- 3a-J-13 フォース・フリー磁場円柱ピンチ・プラズマの安定性解析II
- 5a-G-7 Force-Free 磁場閉じ込めトロイダル・プラズマの安定性
- 大型疎線形計画問題の基底の三角分解更新に対する改良Reid法の提案(LP単体法)
- 有理数演算によるゴモリーの小数法の基礎的検討
- 帯行列を係数行列とする連立一次方程式を誤差なく計算する場合のLU分解について
- 11a-DF-7 フォース・フリー磁場円柱ピンチ・プラズマの安定性解析
- 30a-SB-26 flattened非円形トロイダルプラズマの壁安定化
- 4a-NW-11 Sharp-Boundryトロイダルプラズマのスフェロマクパラメータに対する安定性
- 30a-Z-8 Wangerin関数を用いた非円形MHDトロイダルプラズマの安定性解析
- 12p-K-3 Force Free-Fieldによるトロイダル・プラズマの平衡
- 5p-E-2 トロイダル・プラズマの平衡磁場(III)
- 5a-E-13 トロイダル・シェルによるプラズマの安定
- 4p-J-1 トーラス・プラズマの平衡磁場
- 12a-R-11 トーラス・プラズマの平衡磁場
- 遠心力を考慮した準交換形不安定性と準ヘリカル不安定性の成長率
- 7a-S-1 Surface-Preserving Instabilitiesに対する安定条件
- 7a-J-12 高ベータ・プラズマの安定性III
- 14p-F-6 変分法による円柱プラズマの近似解
- 11p-R-6 高ベータ・プラズマの安定性 II
- 5p-C-3 高ベータ・プラズマの安定性
- 5a-KU-12 B_zに弱い空間分布のあるLinear Bennett Pinchの安定条件
- 25a-B-12 トロイダル磁場の計算
- 3p-J-10 Sharp PinchとDiffuse Pinchとの安定条件の比較
- 外部重力ポテンシャルを考慮した準ヘリカル不安定性の安定条件と成長率
- 外部重力ポテンシャルのあるピッチー定磁場における準交換形不安定の安定条件
- 外部磁場に斜め伝播するプラズマ波
- Power Transform Methodによる非線型一次元電子プラズマ波動の数値的研究
- 非線型定常プラズマ波
- A Equilibrium Magnetic Field for a Toroidal Plasma
- 磁場中プラズマの横波