最大流問題とその双対問題

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文では,フローネットワーク最適化問題の1つとして有名な最大流問題に注目する.最大流問題とは,ネットワークにおいて2つの制約,容量制約と流量保存則のもとでフローの値が最大となるフローを見つける問題である.多くの組み合わせ最適化問題は線形計画問題(LP問題)として定式化され,最大流問題についてもLPへの定式化の方法は知られている.一方で,組み合わせ最適化問題において有名な定理,最大フロー・最小カットセット定理はネットワークにおけるフローとカットセットの双対性を表したものだと知られている.我々の研究の目的は,フローとカットセットの双対性をLP問題を通して明らかにすることである.本論文では知られている定式化とは違う新しい最大流問題の定式化を行った.実験結果によると,新しい定式化の双対問題は解として0-1ベクトルが現れ,これは最小カットセットを与えていた.この結果よりこの定式化は我々の意図するものだといえる.しかし,LP問題の双対問題を作ったのにもかかわらず,0-1ベクトルが解として現れた理由についてはまだ分かっておらず,これを今後の課題とする.In the present paper, we focus on the maximum flow problem which is one of the well-known optimization problems on flow-networks. The maximum flow problem is the problem for finding the flow such that the flow value is maximal among the flows subject to the capacity restriction and the flow conservation laws. Many of the combinatorial optimization problems can be formulated as linear programming (LP) problems, and it is known that the maximum flow problem can be formulated as an LP problem. On the other hand, the max-flow min-cutset theorem which is one of the famous results in combinatorial optimization, suggests the duality between flows and cutsets in networks. The purpose of our study is to clarify the duality between flows and cutsets in the maximum flow problem through the LP problem. In the present paper, we give a new formulation of the maximum flow problem as an LP problem which is slightly different from the one in the references. Computational experiments show that the dual of the LP problem computes a binary vector as the optimal solution, which presents the min-cutset. This implies that our formulation in the present paper is adequate for our purpose. However, we cannot make clear the reason why the optimal solution of the dual problem of the maximum flow problem becomes the binary vector, though the dual problem is an LP problem. This remains as a future subject of study.

著者

• 渡邊 芳英

  Department Of Electronics Doshisha University

• 渡邊 芳英

  Department Of Mathematical Sciences Doshisha University

• 渡辺 扇之介

  Graduate School Of Science And Engineering Doshisha University

• 米田 彩香

  Graduate School of Science and Engineering, Doshisha University

• 米田 彩香

  Graduate School Of Science And Engineering Doshisha University

• 渡邊 芳英

  Department of Mathematical Science,Doshisha University

関連論文

• Semi-Discrete発展方程式のbiーHamilton構造
• 整数計画法に基づくRNA間相互作用予測
• 整数計画法に基づくRNA間相互作用予測
• 2元線形符号の最尤復号におけるグレブナー基底を用いた方法 : BCH符号への応用
• トーリックイデアルのグレプナ基底計算アルゴリズム : 数式処理システムAsirへの実装
• AsirによるToric idealのグレブナー基底計算
• Asirによる有限群の不変式環の生成元の計算 (Computer Algebra : Algorithms, Implementations and Applications)
• Asirによる有限群の不変式環の生成元の計算
• 形式的線形化可能な発展方程式の数え挙げ
• 保存則による発展方程式の分類(数式処理の利用)I:形式的線形化可能系(非線型可積分系の研究の現状と展望)
• Recursion opertor[operator], Hereditary operator 及び Schouten bracket の計算について(数式処理と数学研究への応用)
• 最短路問題を用いたネットワークシンプレックス法のMATLABへの実装
• 当世学生試験事情
• 最大流問題とその双対問題
• ネットワークシンプレックス法における巡回を防ぐ方法
• 最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み
• 最短路問題と最長路問題

もっと見る 閉じる

スポンサーリンク