Page 288 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 14: Network Flows

Figure: 14.7: An example of the transportation network. In this we have 2supply vertexes (with Notes
supply values 5 and 2), 3 demand vertexes (with demand values 1, 4 and 2), and 1 transshipment
node. Each edge has two numbers, capacity and cost, divided by comma

b b
i
u ,c ij j
ij
i j
–1
5 1, 8 6
3, 4
1
0
7, 5 –4
3 5
3, 1

7, 2 3, 1
2
5, 2
4
2
–2

Representing the flow on arc (i, j) ∈ E by x , we can obtain the optimization model for the
ij
minimum cost fl ow problem:
∑ cx
Minimize z(x) = ij ij
(, ) E
∈
ij
subject to
∑ x – ∑ x
ij ij = b for all i ∈ V,
{:( , ) j ∈ } E {:( , ) i ∈ } E i
j j
j i
0 ≤ x ≤ u for all (i, j) ∈ E.
ij ij

The first constraint states that the total outflow of a node minus the total inflow of the node must

be equal to mass balance (supply/demand value) of this node. This is known as the mass balance
constraints. Next, the fl ow bound constraints model physical capacities or restrictions imposed

on the flow’s range. As you can see, this optimization model describes a typical relationship
between warehouses and shops, for example, in a case where we have only one kind of product.
We need to satisfy the demand of each shop by transferring goods from the subset of warehouses,
while minimizing the expenses on transportation.
This problem could be solved using simplex-method, but in this article we concentrate on some

other ideas related to network flow theory. Before we move on to the three basic algorithms used

to solve the minimum cost flow problem, let’s review the necessary theoretical base.
Finding a Solution
When does the minimum cost flow problem have a feasible (though not necessarily optimal)

solution? How do we determine whether it is possible to translate the goods or not?
If δ = Σ b ≠ 0 then the problem has no solution, because either the supply or the demand
def
i∈V i
dominates in the network and the mass balance constraints come into play.

LOVELY PROFESSIONAL UNIVERSITY 283