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: