Page 289 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes We can easily avoid this situation, however, if we add a special node r with the supply/demand
value b = –δ. Now we have two options: If δ > 0 (supply dominates) then for each node i ∈ V with
r
b > 0 we add an arc (i, r) with infinite capacity and zero cost; otherwise (demand dominates), for

i
each node i ∈ V with b < 0, we add an arc (r, i) with the same properties. Now we have a new
i
network with Σ b = 0 – and it is easy to prove that this network has the same optimal value
i∈V∪{r} i
as the objective function.
Consider the vertex r as a rubbish or scrap dump. If the shops demand is less than what the
warehouse supplies, then we have to eject the useless goods as rubbish. Otherwise, we take the
missing goods from the dump. This would be considered shady in real life, of course, but for our
purposes it is very convenient. Keep in mind that, in this case, we cannot say what exactly the
“solution” of the corrected (with scrap) problem is. And it is up to the reader how to classify the
emergency uses of the “dump.” For example, we can suggest that goods remain in the warehouses
or some of the shop’s demands remain unsatisfi ed.
Even if we have δ = 0 we are not sure that the edge’s capacities allow us to transfer enough fl ow
from supply vertexes to demand ones. To determine if the network has a feasible flow, we want

to find any transfer way what will satisfy all the problem’s constraints. Of course, this feasible

solution is not necessarily optimal, but if it is absent we cannot solve the problem.
Let us introduce a source node s and a sink node t. For each node i ∈ V with b > 0, we add a
i
source arc (s, i) to G with capacity b and cost 0. For each node i ∈ V with b < 0, we add a sink arc
i
i
(i, t) to G with capacity –b and cost 0.
i
Figure 14.8: Maximum Flow in the Transformed Network. For simplicity we are ignoring the costs
b b
i x ,u ij j
ij
i j
–1
5 1/1 6 1/1
3/3
5/5 1 0
4/7 –4
4/4
3 5 t
s 2/3

4/7 0/3
2
2/2 2/5 2/2
4
2
–2

The new network is called a transformed network. Next, we solve a maximum fl ow problem
from s to t. If the maximum fl ow saturates all the source and sink arcs, then the problem has a
feasible solution; otherwise, it is infeasible. As for why this approach works, we’ll leave its proof
to the reader.

Having found a maximum flow, we can now remove source, sink, and all adjacent arcs and

obtain a feasible fl ow in G. How do we detect whether the flow is optimal or not? Does this

flow minimize costs of the objective function z? We usually verify “optimality conditions” for
the answer to these questions, but let us put them on hold for a moment and discuss some
assumptions.
Now, suppose that we have a network that has a feasible solution. Does it have an optimal

solution? If our network contains the negative cost cycle of infinite capacity then the objective

284 LOVELY PROFESSIONAL UNIVERSITY