Min-cost flow problem: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
Line 4: | Line 4: | ||
# For each arc <math>a\in A</math>, there are two real numbers: | # For each arc <math>a\in A</math>, there are two real numbers: | ||
## The '''upper bound''' (ak.a. '''capacity) <math>u(a)\geq 0</math>. | ## The '''upper bound''' (ak.a. '''capacity) <math>u(a)\geq 0</math>. | ||
## The (unit) '''cost''' <math>c(a)</math>. | ## The (unit) '''cost''' or '''cost factor''' <math>c(a)\geq 0</math>. | ||
# For each node <math>v\in V</math>, there is a real-valued '''balance''' <math>b(v)</math>. | # For each node <math>v\in V</math>, there is a real-valued '''balance''' <math>b(v)</math>. | ||
Revision as of 17:54, 25 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.