Min-cost flow problem: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
Line 22: | Line 22: | ||
# Set <math>u(a'):=u(a)</math> and <math>c(a'):=c(a)</math>. | # Set <math>u(a'):=u(a)</math> and <math>c(a'):=c(a)</math>. | ||
# Decrease <math>b(v)</math> by <math>u(a)</math> and increase <math>b(w)</math> by <math>u(a)</math>. | # Decrease <math>b(v)</math> by <math>u(a)</math> and increase <math>b(w)</math> by <math>u(a)</math>. | ||
# The resulting flow <math>f(a')</math> on <math>a'</math> is transformed back into <math>f(a):=u(a)-f(a')</math>. | |||
== Known Algorithms == | == Known Algorithms == |
Revision as of 14:52, 26 October 2014
Input
- A directed graph [math]\displaystyle{ G=(V,A) }[/math].
- For each arc [math]\displaystyle{ a\in A }[/math], there are two real numbers:
- The upper bound (ak.a. capacity) [math]\displaystyle{ u(a)\geq 0 }[/math].
- The (unit) cost or cost factor [math]\displaystyle{ c(a)\geq 0 }[/math].
- 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:
- Capacity constraints: [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
- 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].
- 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.
Negative cost factors
The case that some arcs have negativ cost factors, may be transformed as follows into the above version with nonnegative cost factors. For each arc [math]\displaystyle{ a=(v,w) }[/math] such that [math]\displaystyle{ c(a)\lt 0 }[/math]:
- Turn [math]\displaystyle{ a }[/math], giving a new arc [math]\displaystyle{ a'=(w,v) }[/math].
- Set [math]\displaystyle{ u(a'):=u(a) }[/math] and [math]\displaystyle{ c(a'):=c(a) }[/math].
- Decrease [math]\displaystyle{ b(v) }[/math] by [math]\displaystyle{ u(a) }[/math] and increase [math]\displaystyle{ b(w) }[/math] by [math]\displaystyle{ u(a) }[/math].
- The resulting flow [math]\displaystyle{ f(a') }[/math] on [math]\displaystyle{ a' }[/math] is transformed back into [math]\displaystyle{ f(a):=u(a)-f(a') }[/math].