The maximum flow problem and its dual

DOI IR Web Site Open Access

Bibliographic Information

Other Title
  • 最大流問題とその双対問題
  • サイダイリュウ モンダイ ト ソノ ソウツイ モンダイ

Search this article

Description

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.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top