Min-cost flow problem: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 13: Line 13:
A '''min-cost flow''' <math>f</math>, that is, a real number <math>f(a)</math> for each arc <math>a\in A</math> such that:
A '''min-cost flow''' <math>f</math>, that is, a real number <math>f(a)</math> for each arc <math>a\in A</math> such that:
# ''Capacity constraints'': <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# ''Capacity constraints'': <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# ''Flow conservation condition'': For each node <math>v\in V</math>, it is <math>\sum_{w:(v,w)\in A}f(v,w)-\sum_{w;(w,v)\in A}f(w,v)=b(v)</math>.
# ''Flow conservation condition'': For each node <math>v\in V</math>, it is <math>\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)=b(v)</math>.
# ''Optimality'': The cost of <math>f</math>, <math>c(f):=\sum_{a\in A}c(a)\cdot f(a)</math>, is minimum among all flows that satisfy the capacits constraints and the flow conservation condition.
# ''Optimality'': The cost of <math>f</math>, <math>c(f):=\sum_{a\in A}c(a)\cdot f(a)</math>, is minimum among all flows that satisfy the capacity constraints and the flow conservation condition.

Revision as of 14:31, 21 October 2014

Input

  1. A directed graph [math]\displaystyle{ G=(V,A) }[/math].
  2. For each arc [math]\displaystyle{ a\in A }[/math], there are two real numbers:
    1. The upper bound (ak.a. capacity) [math]\displaystyle{ u(a)\geq 0 }[/math].
    2. The (unit) cost [math]\displaystyle{ c(a) }[/math].
  3. For each node [math]\displaystyle{ v\in V }[/math], there is a real-valued balance [math]\displaystyle{ b(v) }[/math].

Prerequisite for feasibility: [math]\displaystyle{ \sum_{v\in V}b(v)=0 }[/math].

Output

A min-cost flow [math]\displaystyle{ f }[/math], that is, a real number [math]\displaystyle{ f(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math] such that:

  1. Capacity constraints: [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
  2. Flow conservation condition: For each node [math]\displaystyle{ v\in V }[/math], it is [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)=b(v) }[/math].
  3. Optimality: The cost of [math]\displaystyle{ f }[/math], [math]\displaystyle{ c(f):=\sum_{a\in A}c(a)\cdot f(a) }[/math], is minimum among all flows that satisfy the capacity constraints and the flow conservation condition.