Description
The minimum cost transportation problem is a special case of the minimum cost maximum flow problem.
Minimum cost transportation problem
Complements of Operations Research
Giovanni Righini
Universit ` a degli Studi di Milano
De?nitions
The minimum cost transportation problem is a special case of the
minimum cost maximum ?ow problem.
We are given:
• a set of origins, O;
• a set of destinations, D;
• an amount of ?ow o
i
to be sent from each origin i ? O;
• an amount of ?ow d
j
to be received by each destination j ? D;
• a transportation network, connecting each origin i ? O with each
destination j ? D at a unit cost c
ij
.
There are no capacities associated with the arcs between O and D.
We assume
i ?O
o
i
=
j ?D
d
j
.
If this does not hold, we add a dummy origin or a dummy destination
where necessary, with zero cost arcs incident in it.
A reformulation
By adding a dummy source s connected to each node i ? O with an
arc of capacity o
i
and a dummy sink t connected to each node j ? D
with an arc of capacity d
j
, we can solve a min cost max ?ow problem
from s to t on the resulting digraph.
This is equivalent to the original problem, because the bottleneck is
the cut separating s (or t) from the rest of the digraph and hence the
max ?ow has value
i ?O
o
i
=
j ?D
d
j
.
A formulation
We use a variable x
ij
(continuous and non-negative) to indicate the
amount of ?ow on each arc (i , j ) ? A = O ×D.
A mathematical model of the problem is:
minimize z =
(i ,j )?A
c
ij
x
ij
s.t.
j ?D
x
ij
= o
i
?i ? O
i ?O
x
ij
= d
j
?j ? D
x
ij
? 0 ?(i , j ) ? A.
It is a linear programming model. Duality theory applies.
The dual problem
P) minimize z =
(i ,j )?A
c
ij
x
ij
s.t.
j ?D
x
ij
= o
i
?i ? O
i ?O
x
ij
= d
j
?j ? D
x
ij
? 0 ?(i , j ) ? A.
D) maximize w =
i ?O
o
i
u
i
+
j ?D
d
j
v
j
s.t. u
i
+ v
j
? c
ij
?(i , j ) ? A
Complementary slackness conditions imply:
x
ij
(c
ij
?(u
i
+ v
j
)) = 0.
Primal-dual algorithm
Begin
Primal initialization;
Dual initialization;
while ?(i , j ) : u
i
+ v
j
> c
ij
do
Update primal solution;
Update dual solution;
end while
End
At each iteration the algorithm keeps a primal-dual pair of solutions
satisfying the CSCs.
The primal solution is feasible; the dual solution is (super-)optimal.
When the optimal dual solution is also feasible, the feasible primal
solution is also optimal.
Primal initialization
Begin Primal Initialization
for i ? O do
R
o
(i ) := o
i
;
end for
for j ? D do
R
d
(j ) := d
j
;
end for
for (i , j ) ? A do
x
ij
:= min{R
o
(i ), R
d
(j )};
R
o
(i ) := R
o
(i ) ?x
ij
;
R
d
(j ) := R
d
(j ) ?x
ij
;
end for
End Primal Initialization
At each step at least one of the residuals R is set to 0. At least in the
last iteration a row residual and a column residual are simultaneously
set to 0, because o and d are balanced.
The number of arcs with non-zero ?ow is at most |O| +|D| ?1.
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
x t1 t2 t3 t4 t5 t6 R
o
s1 0 0 0 0 0 0 30
s2 0 0 0 0 0 0 30
s3 0 0 0 0 0 0 30
R
d
10 12 13 15 20 20 0
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
x t1 t2 t3 t4 t5 t6 R
o
s1 10 0 0 0 0 0 20
s2 0 0 0 0 0 0 30
s3 0 0 0 0 0 0 30
R
d
0 12 13 15 20 20 70
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 0 0 0 0 8
s2 0 0 0 0 0 0 30
s3 0 0 0 0 0 0 30
R
d
0 0 13 15 20 20 214
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 0 0 0 0 30
s3 0 0 0 0 0 0 30
R
d
0 0 5 15 20 20 246
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 0 0 0 25
s3 0 0 0 0 0 0 30
R
d
0 0 0 15 20 20 291
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 15 0 0 10
s3 0 0 0 0 0 0 30
R
d
0 0 0 0 20 20 441
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 15 10 0 0
s3 0 0 0 0 0 0 30
R
d
0 0 0 0 10 20 471
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
10
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 15 10 0 0
s3 0 0 0 0 10 0 20
R
d
0 0 0 0 0 20 651
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
10
20
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 15 10 0 0
s3 0 0 0 0 10 20 0
R
d
0 0 0 0 0 0 651
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Dual update
Exploiting CSCs, a dual solution corresponding to the current primal
solution is obtained by solving a system of linear equations:
u
i
+ v
j
= c
ij
?(i , j ) : x
ij
> 0.
Since the number of basic x variables is |O| +|D| ?1 and the number
of dual variables is |O| +|D|, the system has in?nitely many dual
solutions.
This is consistent with the degeneracy of the primal problem: any
equality constraint can be derived from the others.
Dual update amounts at arbitrarily ?xing a dual variable and solving a
system of linear equations.
This is done both after primal initialization and after each primal
update step.
Visualization of dual update
c t1 t2 t3 t4 t5 t6
s1 7 12 4 15 2 0
s2 1 8 9 10 3 0
s3 6 5 7 2 18 0
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
u
1
+ v
1
= 7
u
1
+ v
2
= 12
u
1
+ v
3
= 4
u
2
+ v
3
= 9
u
2
+ v
4
= 10
u
2
+ v
5
= 3
u
3
+ v
5
= 18
u
3
+ v
6
= 0
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
u
1
= 0
v
1
= 7
v
2
= 12
v
3
= 4
u
2
= 5
v
4
= 5
v
5
= ?2
u
3
= 20
v
6
= ?20
c t1 t2 t3 t4 t5 t6 u
s1 0 0 0 10 4 20 0
s2 -11 -9 0 0 0 15 5
s3 -21 -27 -17 -23 0 0 20
v 7 12 4 5 -2 -20 651
Visualization of dual feasibility test
In our example there are several violated dual constraints: they
correspond to arcs with negative reduced cost.
c t1 t2 t3 t4 t5 t6 u
s1 0 0 0 10 4 20 0
s2 -11 -9 0 0 0 15 5
s3 -21 -27 -17 -23 0 0 20
v 7 12 4 5 -2 -20 651
We can choose for example the minimum reduced cost.
We want to enforce u
3
+v
2
=c
32
to allow x
32
taking positive value.
Primal update
The primal solution is changed by sending ?ow on arc (i , j ),
corresponding to a violated dual constraint.
This implies re-balancing the ?ow on other arcs, in order to maintain
primal feasibility.
Hence a cycle containing (i , j ) is identi?ed, such that all the arcs in
the cycle correspond to active dual constraints.
The ?ow is alternately increased and decreased on the arcs of the
cycle. The bottleneck arc determines the amount of ?ow to be sent
along the cycle.
After the ?ow update, the bottleneck arc has zero ?ow and its
corresponding dual constraint is no longer forced to be active.
Visualization of primal update
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
10
20
x t1 t2 t3 t4 t5 t6
s1 10 12 8 0 0 0
s2 0 0 5 15 10 0
s3 0 0 0 0 10 20
Visualization of primal update
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
10
20
x t1 t2 t3 t4 t5 t6
s1 10 12 8 0 0 0
s2 0 0 5 15 10 0
s3 0 0 0 0 10 20
There is a unique cycle joining s3 with t2
in the ?ow graph corresponding to the
current primal solution.
Flow must be
• increased on (3, 2), (1, 3) and (2, 5);
• decreased on (1, 2), (2, 3) and (3, 5).
? = min{x
12
, x
23
, x
35
} = 5.
Visualization of primal update
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
7
13
15
15
5
20
5
x t1 t2 t3 t4 t5 t6
s1 10 7 13 0 0 0
s2 0 0 0 15 15 0
s3 0 5 0 0 5 20
Now (2, 3) carries no ?ow;
it has been replaced by (3, 2).
The cost variation is
? c
32
= ?(c
32
?c
12
+c
13
?c
23
+c
25
?c
35
) =
5(5?12+4?9+3?18) = 5(?27) = ?135.
doc_470901824.pdf
The minimum cost transportation problem is a special case of the minimum cost maximum flow problem.
Minimum cost transportation problem
Complements of Operations Research
Giovanni Righini
Universit ` a degli Studi di Milano
De?nitions
The minimum cost transportation problem is a special case of the
minimum cost maximum ?ow problem.
We are given:
• a set of origins, O;
• a set of destinations, D;
• an amount of ?ow o
i
to be sent from each origin i ? O;
• an amount of ?ow d
j
to be received by each destination j ? D;
• a transportation network, connecting each origin i ? O with each
destination j ? D at a unit cost c
ij
.
There are no capacities associated with the arcs between O and D.
We assume
i ?O
o
i
=
j ?D
d
j
.
If this does not hold, we add a dummy origin or a dummy destination
where necessary, with zero cost arcs incident in it.
A reformulation
By adding a dummy source s connected to each node i ? O with an
arc of capacity o
i
and a dummy sink t connected to each node j ? D
with an arc of capacity d
j
, we can solve a min cost max ?ow problem
from s to t on the resulting digraph.
This is equivalent to the original problem, because the bottleneck is
the cut separating s (or t) from the rest of the digraph and hence the
max ?ow has value
i ?O
o
i
=
j ?D
d
j
.
A formulation
We use a variable x
ij
(continuous and non-negative) to indicate the
amount of ?ow on each arc (i , j ) ? A = O ×D.
A mathematical model of the problem is:
minimize z =
(i ,j )?A
c
ij
x
ij
s.t.
j ?D
x
ij
= o
i
?i ? O
i ?O
x
ij
= d
j
?j ? D
x
ij
? 0 ?(i , j ) ? A.
It is a linear programming model. Duality theory applies.
The dual problem
P) minimize z =
(i ,j )?A
c
ij
x
ij
s.t.
j ?D
x
ij
= o
i
?i ? O
i ?O
x
ij
= d
j
?j ? D
x
ij
? 0 ?(i , j ) ? A.
D) maximize w =
i ?O
o
i
u
i
+
j ?D
d
j
v
j
s.t. u
i
+ v
j
? c
ij
?(i , j ) ? A
Complementary slackness conditions imply:
x
ij
(c
ij
?(u
i
+ v
j
)) = 0.
Primal-dual algorithm
Begin
Primal initialization;
Dual initialization;
while ?(i , j ) : u
i
+ v
j
> c
ij
do
Update primal solution;
Update dual solution;
end while
End
At each iteration the algorithm keeps a primal-dual pair of solutions
satisfying the CSCs.
The primal solution is feasible; the dual solution is (super-)optimal.
When the optimal dual solution is also feasible, the feasible primal
solution is also optimal.
Primal initialization
Begin Primal Initialization
for i ? O do
R
o
(i ) := o
i
;
end for
for j ? D do
R
d
(j ) := d
j
;
end for
for (i , j ) ? A do
x
ij
:= min{R
o
(i ), R
d
(j )};
R
o
(i ) := R
o
(i ) ?x
ij
;
R
d
(j ) := R
d
(j ) ?x
ij
;
end for
End Primal Initialization
At each step at least one of the residuals R is set to 0. At least in the
last iteration a row residual and a column residual are simultaneously
set to 0, because o and d are balanced.
The number of arcs with non-zero ?ow is at most |O| +|D| ?1.
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
x t1 t2 t3 t4 t5 t6 R
o
s1 0 0 0 0 0 0 30
s2 0 0 0 0 0 0 30
s3 0 0 0 0 0 0 30
R
d
10 12 13 15 20 20 0
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
x t1 t2 t3 t4 t5 t6 R
o
s1 10 0 0 0 0 0 20
s2 0 0 0 0 0 0 30
s3 0 0 0 0 0 0 30
R
d
0 12 13 15 20 20 70
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 0 0 0 0 8
s2 0 0 0 0 0 0 30
s3 0 0 0 0 0 0 30
R
d
0 0 13 15 20 20 214
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 0 0 0 0 30
s3 0 0 0 0 0 0 30
R
d
0 0 5 15 20 20 246
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 0 0 0 25
s3 0 0 0 0 0 0 30
R
d
0 0 0 15 20 20 291
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 15 0 0 10
s3 0 0 0 0 0 0 30
R
d
0 0 0 0 20 20 441
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 15 10 0 0
s3 0 0 0 0 0 0 30
R
d
0 0 0 0 10 20 471
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
10
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 15 10 0 0
s3 0 0 0 0 10 0 20
R
d
0 0 0 0 0 20 651
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Visualization of primal initialization
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
10
20
x t1 t2 t3 t4 t5 t6 R
o
s1 10 12 8 0 0 0 0
s2 0 0 5 15 10 0 0
s3 0 0 0 0 10 20 0
R
d
0 0 0 0 0 0 651
c t1 t2 t3 t4 t5 t6 u
s1 7 12 4 15 2 0 0
s2 1 8 9 10 3 0 0
s3 6 5 7 2 18 0 0
v 0 0 0 0 0 0 0
Dual update
Exploiting CSCs, a dual solution corresponding to the current primal
solution is obtained by solving a system of linear equations:
u
i
+ v
j
= c
ij
?(i , j ) : x
ij
> 0.
Since the number of basic x variables is |O| +|D| ?1 and the number
of dual variables is |O| +|D|, the system has in?nitely many dual
solutions.
This is consistent with the degeneracy of the primal problem: any
equality constraint can be derived from the others.
Dual update amounts at arbitrarily ?xing a dual variable and solving a
system of linear equations.
This is done both after primal initialization and after each primal
update step.
Visualization of dual update
c t1 t2 t3 t4 t5 t6
s1 7 12 4 15 2 0
s2 1 8 9 10 3 0
s3 6 5 7 2 18 0
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
u
1
+ v
1
= 7
u
1
+ v
2
= 12
u
1
+ v
3
= 4
u
2
+ v
3
= 9
u
2
+ v
4
= 10
u
2
+ v
5
= 3
u
3
+ v
5
= 18
u
3
+ v
6
= 0
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
u
1
= 0
v
1
= 7
v
2
= 12
v
3
= 4
u
2
= 5
v
4
= 5
v
5
= ?2
u
3
= 20
v
6
= ?20
c t1 t2 t3 t4 t5 t6 u
s1 0 0 0 10 4 20 0
s2 -11 -9 0 0 0 15 5
s3 -21 -27 -17 -23 0 0 20
v 7 12 4 5 -2 -20 651
Visualization of dual feasibility test
In our example there are several violated dual constraints: they
correspond to arcs with negative reduced cost.
c t1 t2 t3 t4 t5 t6 u
s1 0 0 0 10 4 20 0
s2 -11 -9 0 0 0 15 5
s3 -21 -27 -17 -23 0 0 20
v 7 12 4 5 -2 -20 651
We can choose for example the minimum reduced cost.
We want to enforce u
3
+v
2
=c
32
to allow x
32
taking positive value.
Primal update
The primal solution is changed by sending ?ow on arc (i , j ),
corresponding to a violated dual constraint.
This implies re-balancing the ?ow on other arcs, in order to maintain
primal feasibility.
Hence a cycle containing (i , j ) is identi?ed, such that all the arcs in
the cycle correspond to active dual constraints.
The ?ow is alternately increased and decreased on the arcs of the
cycle. The bottleneck arc determines the amount of ?ow to be sent
along the cycle.
After the ?ow update, the bottleneck arc has zero ?ow and its
corresponding dual constraint is no longer forced to be active.
Visualization of primal update
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
10
20
x t1 t2 t3 t4 t5 t6
s1 10 12 8 0 0 0
s2 0 0 5 15 10 0
s3 0 0 0 0 10 20
Visualization of primal update
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
12
8
5
15
10
10
20
x t1 t2 t3 t4 t5 t6
s1 10 12 8 0 0 0
s2 0 0 5 15 10 0
s3 0 0 0 0 10 20
There is a unique cycle joining s3 with t2
in the ?ow graph corresponding to the
current primal solution.
Flow must be
• increased on (3, 2), (1, 3) and (2, 5);
• decreased on (1, 2), (2, 3) and (3, 5).
? = min{x
12
, x
23
, x
35
} = 5.
Visualization of primal update
s1
s2
s3
t1
t2
t3
t4
t5
t6
10
7
13
15
15
5
20
5
x t1 t2 t3 t4 t5 t6
s1 10 7 13 0 0 0
s2 0 0 0 15 15 0
s3 0 5 0 0 5 20
Now (2, 3) carries no ?ow;
it has been replaced by (3, 2).
The cost variation is
? c
32
= ?(c
32
?c
12
+c
13
?c
23
+c
25
?c
35
) =
5(5?12+4?9+3?18) = 5(?27) = ?135.
doc_470901824.pdf