足切り横断ポリマトロイドに対するネットワーク算法

概要

論文の詳細を見る
オペレーションズ・リサーチ、また他の工学の諸分野における離散システムを解析するのに(ポリ)マトロイド、劣モジュラ関数的な考え方が有用であり、ここ10年程の間に様々な問題に対して応用されてきた。本論文では、まず、現実問題においてよく現われるマトロイドの多くを含む足切り横断ポリマトロイドを導入し、そして、それに関する組合せ最適化問題に対して、ネットワーク・フローの手法を用いた効率的、統一的な算法を提案する。一般に、ポリマトロイド最適化の統一的問題として独立流れ問題が知られているが、具体的にあるポリマトロイドが与えられたとき、それに関する独立流れ問題を実際に解くには、そのポリマトロイドの飽和関数、従属関数等の基本関数が効率よく計算できることが必要である。本論文では、ここで導入した足切り横断ポリマトロイドの基本関数が、ネットワーク算法により容易に、かっ、効率よく求められることを示す。そして、足切り横断ポリマトロイドの組合せ最適化問題の内greedy型の問題、すなわち、基や最大重み独立ベクトルを求める問題、基本分割を求める問題、及び被覆・詰込問題が取り分け効率よく解けることに着目し、この型の問題について詳細に議論する。足切り横断ホリマトロイドの典型的な、また有用な例としては、横断マトロイドの他に、グラフの閉路マトロイド、及びその合併マトロイド(これらのマトロイドは、電気回路網の基本的諸問題に応用されてきた)、2次元リンク構造に現われるマトロイド等が挙げられる。ここでは、この2つの具体的なマトロイドに関する組合せ最適化問題が本論文で提案するネットワーク・フローの手法により効率よく解けることを示す。さらに、応用の立場から述べると、足切り横断ホリマトロイドは内部自由度を有する離散システム(例えば、上述の2例の他に多面体線画構造等)と密接な関係がある。ここでは、それぞれのシステムに関する諸問題について触れることはしないが、一般に、足切り横断ホリマトロイドに対するネットワーク・フロー的手法を殆とそのまま適用することにより、この種のシステムを効率よく解析することができる(ここでシステムを解析するとは、システムが冗長であるかどうかを判定すること、冗長でない極大な部分システムを求めること等を意味する)。
社団法人日本オペレーションズ・リサーチ学会の論文

足切り横断ポリマトロイドに対するネットワーク算法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク