5Network problems
IB Optimisation
5.2 Minimum-cost flow problem
Let
G
= (
V, E
) be a directed graph. Let the number of vertices be
|V |
=
n
and
let
b ∈ R
n
. For each edge, we assign three numbers: a cost, an lower bound and
a upper bound. We denote these as matrices as C, M , M ∈ R
n×n
.
Each component of the vector
b
i
denotes the amount of flow entering or
leaving each vertex
i ∈ V
. If
b
i
>
0, we call
i ∈ V
a source. For example, if
we have a factory at
b
i
that pro duces stuff,
b
i
will b e positive. This is only the
amount of stuff produced or consumed in the vertex, and not how many things
flow through the vertex.
c
ij
is the cost of transferring one unit of stuff from vertex
i
to vertex
j
(fill
entries with 0 if there is no edge between the vertices), and
m
ij
and
m
ij
denote
the lower and upper bounds on the amount of flow along (
i, j
)
∈ E
respectively.
x ∈ R
n×n
is a minimum-cost flow if it minimizes the cost of transferring stuff,
while satisfying the constraints, i.e. it is an optimal solution to the problem
minimize
X
(i,j)∈E
c
ij
x
ij
subject to
b
i
+
X
j:(j,i)∈E
x
ji
=
X
j:(i,j)∈E
x
ij
for each i ∈ V
m
ij
≤ x
ij
≤ m
ij
for all (i, j) ∈ E.
This problem is a linear program. In theory, we can write it into the general
form Ax = b, where A is a huge matrix given by
a
ij
1 if the kth edge starts at vertex i
−1 if the kth edge ends at vertex i
0 otherwise
However, using this huge matrix to solve this problem by the simplex method is
not very efficient. So we will look for better solutions.
Note that for the system to make sense, we must have
X
i∈V
b
i
= 0,
i.e. the total supply is equal to the total consumption.
To simplify the problem, we can convert it into an e quivalent circulation
problem, where
b
i
= 0 for all
i
. We do this by adding an additional vertex where
we send all the extra
b
i
to. For example, if a vertex has
b
i
=
−
1, then it takes in
more stuff than it gives out. So we can mandate it to send out one extra unit to
the additional vertex. Then b
i
= 0.
An uncapacitated problem is the case where
m
ij
= 0 and
m
ij
=
∞
for all
(
i, j
)
∈ E
. An uncapacitated problem is either unbounded or bounded. If it is
bounded, then it is equivalent to a problem with finite capacities, since we can
add a bound greater than what the optimal solution wants.
We are going to show that this can be reduced to a simpler problem: