Minimum-cost flow problem

Minimum-cost flow problem

The minimum-cost flow problem is finding the cheapest possible way of sending a certain amount of flow through a flow network.

Contents

Definition

Given a flow network \,G(V,E) with source s \in V and sink t \in V, where edge (u,v) \in E has capacity \,c(u,v), flow \,f(u,v) and cost \,a(u,v). The cost of sending this flow is f(u,v) \cdot a(u,v). You are required to send an amount of flow \,d from s to t.

The definition of the problem is to minimize the total cost of the flow:

\sum_{u,v \in V} a(u,v) \cdot f(u,v)

with the constraints

Capacity constraints: \,f(u,v) \le c(u,v)
Skew symmetry: \,f(u,v) = - f(v,u)
Flow conservation: \,\sum_{w \in V} f(u,w) = 0\text{ for all }u \neq s, t
Required flow: \,\sum_{w \in V} f(s,w) = d\text{ and }\sum_{w \in V} f(w,t) = d

Relation to other problems

A variation of this problem is to find a flow which is maximum, but has the lowest cost among the maximums. This could be called a minimum-cost maximum-flow problem. This is useful for finding minimum cost maximum matchings.

With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, you can do a binary search on d.

A related problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. You do this by setting the lower bound on all edges to zero, and then make an extra edge from the sink t to the source s, with capacity c(t,s) = d and lower bound l(t,s) = d, forcing the total flow from s to t to also be d.

The problem can be specialized into two other problems:

Solutions

The minimum cost flow problem can be solved by linear programming, since we optimize a linear function, and all constraints are linear.

Apart from that, many combinatorial algorithms exist, for a comprehensive survey, see [1]. Some of them are generalizations of maximum flow algorithms, others use entirely different approaches.

Well-known fundamental algorithms (they have many variations):

  • Cycle canceling: a general primal method.[2]
  • Minimum mean cycle canceling: a simple strongly polynomial algorithm.[3]
  • Successive shortest path and capacity scaling: dual methods, which can be viewed as the generalizations of the Ford–Fulkerson algorithm.[4]
  • Cost scaling: a primal-dual approach, which can be viewed as the generalization of the push-relabel algorithm.[5]
  • Network simplex: a specialized version of the linear programming simplex method.

See also

References

  1. ^ Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc.. ISBN 0-13-617549-X. 
  2. ^ Morton Klein (1967). "A primal method for minimal cost flows with applications to the assignment and transportation problems". Management Science 14: 205–220. 
  3. ^ Andrew V. Goldberg and Robert E. Tarjan (1989). "Finding minimum-cost circulations by canceling negative cycles". Journal of the ACM 36 (4): 873–886. 
  4. ^ Jack Edmonds and Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM 19 (2): 248–264. 
  5. ^ Andrew V. Goldberg and Robert E. Tarjan (1990). "Finding minimum-cost circulations by successive approximation". Math. Oper. Res. 15 (3): 430–466. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Minimum cost flow problem — The minimum cost flow problem is finding the cheapest possible way of sending a certain amount of flow through a flow network. Definition Given a flow network ,G(V,E) with source s in V and sink t in V, where edge (u,v) in E has capacity ,c(u,v) …   Wikipedia

  • Multi-commodity flow problem — The multi commodity flow problem is a network flow problem with multiple commodities (or goods) flowing through the network, with different source and sink nodes. Contents 1 Definition 2 Relation to other problems 3 Usage 4 …   Wikipedia

  • Maximum flow problem — An example of a flow network with a maximum flow. The source is s, and the sink t. The numbers denote flow and capacity. In optimization theory, the maximum flow problem is to find a feasible flow through a single source, single sink flow network …   Wikipedia

  • Flow network — In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a… …   Wikipedia

  • Circulation problem — The circulation problem and its variants is a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink (i.e. there are no special… …   Wikipedia

  • Assignment problem — The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph. In its most… …   Wikipedia

  • Closure problem — A Closure problem is a problem in graph theory for finding a set of vertices in a directed graph such that there are no edges from the set to the rest of the graph. More specifically, the minimum closure problem asks for a set of this type with… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Shortest path problem — A graph with 6 vertices and 7 edges In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. An example is… …   Wikipedia

  • Graphe (mathématiques) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”