最大利得部分木問題に対する近似解法および厳密解法(<特集>マルチメディアネットワークシステム)

スポンサーリンク

概要

• 論文の詳細を見る

• 連結無向グラフにおいて, 1点が根として指定されているとする.また, 各枝にはコスト, 各点には利得が与えられ, さらに総コスト上限が定められているとする.このとき, 最大利得部分木問題とは, 根を含む連結部分木で, 枝のコストの和が総コスト上限以下で, 点の利得の和が最大となるものを求める問題である.本論文の目的は, この問題に対して近似解法および分枝限定法による厳密解法を構築し, 計算実験によりそれら有効性を検証することである.特に分枝限定法による厳密解法の構築にあたっては, 数理計画による定式化を行って線形緩和を利用したアプローチと, 元の問題を部分木の点や枝の数を制限した問題に分割するアプローチの2つを試みた.計算機実験の結果, 元の問題を分割するアプローチの方が有効であることが分かった.

• 一般社団法人情報処理学会の論文
• 2001-02-15

著者

• 片岡 靖詞

  防衛大学校情報工学科

• 森戸 晋

  早稲田大学創造理工学部

• 森戸 晋

  早稲田大学・理工学部・工業経営学科

• 森戸 晋

  早稲田大学 創造理工学部

• 星崎 康広

  富士写真フィルム株式会社生産技術部

• 森戸 晋

  早稲田大学

関連論文

• 機関車の基地内留置計画に対する整数計画アプローチ
• 1-B-8 割当問題のミニマックス最適化(組合せ最適化(2))
• 鉄道における乗務員運用計画の集合被覆問題に対する Wedelin の解法の適用
• ナップサック制約付き最大全域木問題の一解法(組合せ(1))
• 最小全域木を全列挙するアルゴリズム(グラフ・ネットワーク(2))
• 単純リコースを有する整数確率計画問題の Dynamic Slope Scaling Procedure を用いた解法
• 1-B-4 最小経路費用木問題の厳密解法(離散最適化(1))
• 1-E-1 固定費を含む確率計画問題の解法(数理モデル)
• 2-F-8 リコース関数に固定費を含む確率計画問題(数理計画(2))
• 2-B-8 数理計画法を用いた機関車の基地内留置計画の最適化(交通(2))
• 多目的ナップサック問題のマックスミン最適化(不確実性の下での意思決定と数理モデル)
• 1-B-7 2目的マックスミンナップサック問題の厳密解法(組合せ最適化(2))
• 2目的ナップサック問題のマックスミン最適化(多目的最適化)
• 一般化ナップサック共有問題の厳密解法
• 排他制約付きナップサック問題の近似解法と厳密解法(組合せ)
• 負コスト枝を含む有向グラフにおける最短単純路問題(グラフ・ネットワーク(3))
• 2-C-2 確率計画法による予防的・緊急的在庫転送併用方策の定式化(在庫管理)
• 1-S-1 鉄道乗務員交番作成に対するCapraraのラグランジュ緩和アプローチ : 日本の鉄道への適用可能性の検討(鉄道とOR)
• 2-E-5 Location-Routing Problemに対するLagrange緩和と列生成法の併用アプローチ(離散最適化(2))
• 分散を考慮した2段階確率計画問題
• 分散を考慮した2段階確率計画問題
• 二段階数理計画アプローチによる鉄道車両運用計画の策定
• 2-B-7 ダイヤ乱れ時の機関車運用計画修正問題に対する列生成アプローチ(交通(2))
• 鉄道乗務員スケジューリング問題に対する解法とその評価
• 2-B-9 分散を考慮した確率計画問題(大域的最適化)
• 2-E-12 列車ダイヤ遅延時の乗務員スケジュール修正問題(スケジューリング(2))
• 2-E-11 数理計画による鉄道車両運用計画の策定(スケジューリング(2))
• 2-D-11 乗務員運用計画問題に対する便乗削減の定式化と解法(輸送・交通(3))
• 2-B-1 乗務員運用計画問題の列生成子問題に対するPull型ラベリング解法と性能評価(数理計画(2))
• モデルが見えるとき(モデリング-最適化モデリング-)
• 乗務員運用計画の集合被覆問題に対するWedelin解法の適用(タイムテーブリング)
• 二段階数理計画アプローチによる鉄道車両運用計画の策定
• 可変バックオーダ比率をもつ確率的な部分バックオーダシステムに関する研究
• 1-E-8 勝ち抜きトーナメント表の作成(スポーツスケジューリング)
• 最小拘束問題の分枝限定法アルゴリズム
• 多段階ロットサイズ問題に対する妥当な不等式と強い定式化(組合せ理論)
• 定期的輸送調整によるレンタル製品在庫管理のモデル分析(流通・物流)
• 段取りを費用を考慮したカッティング計画問題(生産・スケジューリング)
• Clusteringによるグラフ分割問題へのメタ解法(グラフ・ネットワーク(2))
• Experimental analysis of a semidefinite programming approach to the graph partitioning problem
• Fast Implementation and Experiments of n Queens' Problem
• Parameter Optimization of the Tabu Search for the Maximum Clique Problem
• An Approximate Algorithm for the Maximum Stable Set Problem
• グラフ分割問題に対するTabu Searchの数値実験(グラフ・ネットワーク(2))
• 最小κ-部分木問題のNP困難性・貪欲的下界値算法・近似解法(グラフ・ネットワーク(2))
• ミニマックス全域森問題のいくつかの拡張(グラフ・ネットワーク(2))
• ミニマックス完全森問題の厳密解法(グラフ・ネットワーク(2))
• 最小k-部分木問題におけるいくつかの妥当不等式とその効果(グラフ・ネットワーク(2))
• ミニマックス完全森問題に対する近似解法(グラフ・ネットワーク(4))
• 鉄道の乗務員運用計画作成問題に対する列生成法の適用
• 新郵便処理システムのシミュレーション分析(公共システムとOR)
• 最大利得部分木問題に対する近似解法および厳密解法(マルチメディアネットワークシステム)
• 安定結婚の全列挙アルゴリズム(組合せ最適化(2))
• ナップサック共有問題の近似・厳密解法(組合わせ最適化(1))
• スコア・オリエンテ-リング問題に対するいくつかの近似解法とタブ-・サ-チ--中溝高好教授に捧ぐ
• Max-Minナップサック問題の近似解法(組合せ最適化(4))
• 最小通過流問題の諸性質と最適路の明示法(グラフ・ネットワーク(4))
• 多目的線型計画問題における有効端点の全列挙法(意思決定)
• 最小通過流問題の諸性質と最小費用流問題との関係(グラフ・ネットワーク(2))
• 有向グラフにおけるある資源配分問題について(組合せ最適化)
• ジョブショップ・システムにおける費用最小化問題について(グラフ・ネットワーク(2))
• Identifiability of a Simultaneous Equations Model of Economy : A Structural View
• 環状コンピュータ・ネットワークの一最適構成法(グラフ)
• 再帰型端点列挙法 : 理論(数理計画)
• 固定費付き複数ナップサック問題 : 分枝費用法によるアプローチ(組合せ最適化)
• 固定費付き複数ナップサック問題の上界値(整数計画)
• ラグランジュ緩和を用いた最小根付きκ-部分木問題の最適解法(数理計画(3))
• 最小根付きk-部分木問題に対するラグランジュ緩和を用いた貪欲的下界値算法の改善(グラフネットワーク(1))
• 1-D-1 最小経路費用木問題の分枝限定法(離散・組合せ最適化(1))
• 2-D-20 最小経路費用木問題の下界値(離散最適化)
• 2-F-9 Pruferリストに基づく木構造列挙の汎用的アルゴリズム(4) : 最小経路費用木問題への適用(グラフ(1))
• 1-D-10 Pruferリストに基づく木構造列挙の汎用的アルゴリズム(3) : 次数制限付き最小木問題への適用:実験編(離散アルゴリズム(3))
• 2-E-4 Pruferリストに基づく木構造列挙のアルゴリズム(2) : 次数制限付き最小木問題への適用(組合せ最適化と応用(3))
• 2-C-1 Pruferリストに基づく木構造列挙の汎用的アルゴリズム(グラフ・ネットワーク)
• 2-C-5 次数制限付き輸送問題のリスト表現を用いた分枝限定法(グラフ・ネットワーク(1))
• 2-A-2 次数制限付き輸送問題(離散最適化(3))
• 平成16年春季研究発表会ルポ(情報の窓)
• 第51回シンポジウムルポ(情報の窓)
• 0-1複数ナップサック問題に対する列生成法を用いた上界値(組合せ最適化ほか)
• 進行方向片側のみサービス可能な巡回路問題(2) : 基本タイセット行列を用いた表現(グラフ・スケジューリング)
• 進行方向片側のみサービス可能な巡回路問題(グラフ・ネットワーク(2))
• 最小拘束問題の分枝限定法 : これまでの課題の解決策(組合せ最適化(3))
• 最小拘束問題の下界値改善と分枝限定法(組合せ)
• 最小拘束問題の下界値算法(組合せ最適化)
• 最小拘束問題の動的計画法アルゴリズム(組み合わせ最適化(1))
• 最小滞在時間問題(2) : 分枝限定法の適用と3教員緩和(組合せ最適化(2))
• 最小滞在時間問題(1) : 定式化および制約の改善(組合せ最適化(2))
• 最小k部分木問題に対する分枝限定法の適用(グラフ・ネットワーク(1))
• 部分巡回路型の問題に対する有向部分1-木緩和と下界値上昇法(組合せ最適化(4))
• 1つの連結成分を持つ最小有向部分木問題II(グラフ理論)
• 非対称TSPにおける最小有向1-木を用いた下界値上昇法(組合せ)
• 一つの連結成分を持つ最小重み有向部分木問題(数理計画)
• 単一制約付最大集荷問題のアルゴリズム
• 2-I-9 動的計画法による多次元ナップサック問題の近似解法と変数縮小(離散最適化(4))
• 2-A-10 動的計画法による多次元ナップサック問題の近似解法(離散最適化(3))
• 動的計画法を用いた多次元ナップサック問題の変数縮小法 (不確実・不確定環境下における数理的意思決定とその周辺)
• 2-C-8 動的ネットワークフロー問題の分離構造(連続最適化(1))
• 1-B-10 ボトルネック型複数ナップサック割当問題の上下界値の評価(離散最適化(3))
• 1-B-9 複数ナップサック-割当問題の2重分枝価格法(離散最適化(3))
• 2-F-9 列生成法および分枝価格法の退化実態とその対策(最適化(1))

もっと見る 閉じる

スポンサーリンク