Min-cost flow problem: Difference between revisions
Jump to navigation
Jump to search
| (11 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Basic definitions == | |||
# [[Basic graph definitions]] | |||
# [[Basic flow definitions]] | |||
== Input == | == Input == | ||
# A [[Basic graph definitions|directed graph]] <math>G=(V,A)</math>. | # A [[Basic graph definitions#Directed and undirected graphs|simple, anti-symmetric directed graph]] <math>G=(V,A)</math>. | ||
# 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>. | ||
| Line 15: | Line 20: | ||
# ''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 capacity 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. | ||
== Negative cost factors == | |||
The case that some arcs have negative cost factors, may be transformed as follows into the above version, in which all cost factors are nonnegative. For each arc <math>a=(v,w)</math> such that <math>c(a)<0</math>: | |||
# Turn <math>a</math>, giving a new arc <math>a'=(w,v)</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>. | |||
# The resulting flow <math>f(a')</math> on <math>a'</math> is transformed back into <math>f(a):=u(a)-f(a')</math>. | |||
Recall that the original graph <math>G</math> is simple, so the resulting graph is simple as well. | |||
== Known Algorithms == | == Known Algorithms == | ||
# [[Negative cycle-canceling]] | # [[Negative cycle-canceling]] | ||
# [[ | # [[Successive shortest paths]] | ||
# [[Successive shortest paths with reduced costs]] | |||
Latest revision as of 14:31, 1 December 2014
Basic definitions
Input
- A simple, anti-symmetric 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 negative cost factors, may be transformed as follows into the above version, in which all cost factors are nonnegative. 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].
Recall that the original graph [math]\displaystyle{ G }[/math] is simple, so the resulting graph is simple as well.