5Network problems

IB Optimisation



5.3 The transportation problem
The transportation problem is a special case of the minimum-flow problem,
where the graph is a bipartite graph. In other words, we can split the vertices
into two halves
A, B
, where all edges flow from a vertex in
A
to a vertex in
B
.
We call the vertices of A the suppliers and the vertices of B the consumers.
In this case, we can write the problem as
minimize
n
X
i=1
m
X
j=1
c
ij
x
ij
subject to
m
X
j=1
x
ij
= s
i
for i = 1, · · · , n
n
X
i=1
x
ij
= d
j
for j = 1, · · · , m
x 0
This
s
i
is the supply of each supplier, and
d
i
is the demand of each supplier. We
have s R
n
, d R
m
satisfying s, d 0,
P
s
i
=
P
d
j
.
Finally, we have c R
n×m
representing the cost of transferal.
We now show that every (bounded) minimum cost-flow problem can be
reduced to the transportation problem.
Theorem.
Every minimum cost-flow problem with finite capacities or non-
negative costs has an equivalent transportation problem.
Proof.
Consider a minimum-cost flow problem on network (
V, E
). It is wlog to
assume that
m
ij
= 0 for all (
i, j
)
E
. Otherwise, set
m
ij
to 0,
m
ij
to
m
ij
m
ij
,
b
i
to
b
i
m
ij
,
b
j
to
b
j
+
m
ij
,
x
ij
to
x
ij
m
ij
. Intuitively, we just secretly ship
the minimum amount without letting the network know.
Moreover, we can assume that all capacities are finite: if some edge has
infinite capacity but non-negative cost, then setting the capacity to a large
enough number, for example
P
iV
|b
i
|
does not affect the optimal solutions.
This is since cost is non-negative, and the optimal solution will not want shipping
loops. So we will have at most
P
|b
i
| shipments.
We will construct an instance of the transportation problem as follows:
For every i V , add a consumer with demand
P
k:(i,k)E
m
ik
b
i
.
For every (
i, j
)
E
, add a supplier with supply
m
ij
, an edge to consumer
i
with cost c
(ij,i)
= 0 and an edge to consumer j with cost c
(ij,j)
= c
ij
.
ij
i
j
0
c
ij
m
ij
P
k:(i,k)E
m
ik
b
i
P
k:(j,k)E
m
jk
b
j
The idea is that if the capacity of the edge (
i, j
) is, say, 5, in the original network,
and we want to transport 3 along this edge, then in the new network, we send 3
units from ij to j, and 2 units to i.
The tricky part of the proof is to show that we have the same constraints in
both graphs.
For any flow
x
in the original network, the corresponding flow on (
ij, j
) is
x
ij
and the flow on (ij, i) is m
ij
x
ij
. The total flow into i is then
X
k:(i,k)E
(m
ik
x
ik
) +
X
k:(k,i)E
x
ki
This satisfies the constraints of the new network if and only if
X
k:(i,k)E
(m
ik
x
ik
) +
X
k:(k,i)E
x
ki
=
X
k:(i,k)E
m
ik
b
i
,
which is true if and only if
b
i
+
X
k:(k,i)E
x
ki
X
k:(i,k)E
x
ik
= 0,
which is exactly the constraint for the node
i
in the original minimal-cost flow
problem. So done.
To solve the transportation problem, it is convenient to have two sets of
Lagrange multipliers, one for the supplier constraints and one for the consumer
constraint. Then the Lagrangian of the transportation problem can be written
as
L(x, λ, µ) =
m
X
i=1
n
X
j=1
c
ij
x
ij
+
n
X
i=1
λ
i
s
i
m
X
j=1
x
ij
n
X
j=1
µ
j
d
j
n
X
j=1
x
ij
.
Note that we use different signs for the Lagrange multipliers for the suppliers
and the consumers, so that our ultimate optimality condition will look nicer.
This is equivalent to
L(x, λ, µ) =
n
X
i=1
n
X
j=1
(c
ij
λ
i
+ µ
j
)x
ij
+
n
X
i=1
λ
i
s
i
m
X
j=1
µ
j
d
j
.
Since
x
0, the Lagrangian has a finite minimum iff
c
ij
λ
i
+
µ
j
0 for all
i, j. So this is our dual feasibility condition.
At an optimum, complementary slackness entails that
(c
ij
λ
i
+ µ
j
)x
ij
= 0
for all i, j.
In this case, we have a tableau as follows:
µ
1
µ
2
µ
3
µ
4
λ
1
µ
1
λ
1
µ
2
λ
1
µ
3
λ
1
µ
4
λ
1
x
11
c
11
x
12
c
12
x
13
c
13
x
14
c
14
s
1
λ
2
µ
1
λ
2
µ
2
λ
2
µ
3
λ
2
µ
4
λ
2
x
21
c
21
x
22
c
22
x
23
c
23
x
24
c
24
s
1
λ
3
µ
1
λ
3
µ
2
λ
3
µ
3
λ
3
µ
4
λ
3
x
31
c
31
x
32
c
32
x
33
c
33
x
34
c
34
s
1
d
1
d
2
d
3
d
4
We have a row for each supplier and a column for each consumer.
Example.
Suppose we have three suppliers with supplies 8
,
10 and 9; and four
consumers with demands 6, 5, 8, 8.
It is easy to create an initial feasible solution - we just start from the first
consumer and first supplier, and supply as much as we can until one side runs
out of stuff.
We first fill our tableau with our feasible solution.
6 5 2 3 4 6 8
2 3 7 7 4 1 10
5 6 1 2 8 4 9
6 5 8 8
8 = s
1
10 = s
2
9 = s
3
d
1
= 6
d
2
= 5
d
3
= 8
d
4
= 8
6
2
3
7
1
8
We see that our basic feasible solution corresponds to a spanning tree. In general,
if we have
n
suppliers and
m
consumers, then we have
n
+
m
vertices, and hence
n
+
m
1 edges. So we have
n
+
m
1 dual constraints. So we can arbitrarily
choose one Lagrange multiplier, and the other Lagrange multipliers will follow.
We choose λ
1
= 0. Since we require
(c
ij
λ
i
+ µ
i
)x
ij
= 0,
for edges in the spanning tree,
x
ij
6
= 0. So
c
ij
λ
i
+
µ
i
= 0. Hence we must
have
µ
1
=
5. We can fill in the values of the other Lagrange multipliers as
follows, and obtain
-5 -3 0 -2
0 6 5 2 3 4 6
4 2 3 7 7 4 1
2 5 6 1 2 8 4
We can fill in the values of λ
i
µ
i
:
-5 -3 0 -2
0 2
0 6 5 2 3 4 6
9 6
4 2 3 7 7 4 1
7 5
2 5 6 1 2 8 4
The dual feasibility condition is
λ
i
µ
i
c
ij
If it is satisfied everywhere, we have optimality. Otherwise, will have to do
something.
What we do is we add an edge, say from the second supplier to the first
consumer. Then we have created a cycle. We keep increasing the flow on the
new edge. This causes the values on other edges to change by flow conservation.
So we keep doing this until some other edge reaches zero.
If we increase flow by, say, δ, we have
6 δ 5 2 + δ 3 4 6
δ 2 3 δ 7 7 4 1
5 6 1 2 8 4
8 = s
1
10 = s
2
9 = s
3
d
1
= 6
d
2
= 5
d
3
= 8
d
4
= 8
6 δ
2 + δ
3 δ
7
1
8
δ
The maximum value of δ we can take is 3. So we end up with
3 5 5 3 4 6
3 2 7 7 4 1
5 6 1 2 8 4
We re-compute the Lagrange multipliers to obtain
-5 -3 -7 -9
7 9
0 3 5 5 3 4 6
0 6
-3 3 2 7 7 4 1
0 -2
-5 5 6 1 2 8 4
We see a violation at the bottom right. So we do it again:
3 5 5 3 4 6
3 2 7 7 δ 4 δ 1
5 6 1 + δ 2 8 δ 4
The maximum possible value of δ is 7. So we have
3 5 5 3 4 6
3 2 7 4 7 1
5 6 8 2 1 4
Calculating the Lagrange multipliers gives
-5 -3 -2 -4
2 4
0 3 5 5 3 4 6
0 -1
-3 3 2 7 4 7 1
5 3
0 5 6 8 2 1 4
No more violations. Finally. So this is the optimal solution.