Algorithms in a Nutshell

(^246) | Chapter 8: Network Flow Algorithms
Minimum Cost Flow
To solve a Minimum Cost Flow problem we need only construct a flow network
graph and ensure that it satisfies the criteria discussed earlier—capacity
constraint, flow conservation, and skew symmetry—as well as two additional
criteria:
Supply satisfaction
For each source vertexsi∈S, the sum off(si,v) for all edges (si,v)∈E(the flow
out ofsi) minus the sum off(u,si) for all edges (u,si)∈E(the flow intosi) must
be less than or equal tosup(si). That is, the supplysup(si) at each source
vertex is a firm upper bound on the net flow from that vertex.
Demand satisfaction
For each sink vertextj∈T, the sum off(u,tj) for all edges (u,tj)∈E(the flow
intotj) minus the sum off(tj,v) for all edges (tj,v)∈E(the flow out oftj) must
be less than or equal todem(tj). That is, thedem(tj) at each target vertex is a
firm upper bound on the net flow into that vertex.
To simplify the algorithmic solution, we further constrain the flow network graph
to have a single source vertex and sink vertex. This can be easily accomplished by
taking an existing flow network graph with any number of source and sink
vertices and adding two new vertices. First, add a new vertex (which we refer to as
s 0 ) to be the source vertex for the flow network graph, and add edges (s 0 ,si) for all
si∈Swhose capacityc(s 0 ,si)=sup(si) and whose costd(s 0 ,si)=0. Second, add a new
vertex (which we often refer to astgt, for target) to be the sink vertex for the flow
network graph, and add edges (tj,tgt) for alltj∈Twhose capacityc(tj,tgt)=dem(tj)
and whose costd(t 0 ,tj)=0. As you can see, adding these vertices and edges does
not increase the cost of the network flow, nor do they reduce or increase the final
computed flow over the network.
The suppliessup(si), demandsdem(tj), and capacitiesc(u,v) are all greater than 0.
The shipping costd(u,v) associated with each edge may be greater than or equal
to zero. When the resulting flow is computed, allf(u,v) values will be greater than
or equal to zero.
We are now ready to present the constructions that allow us to solve each of the
remaining flow network problems listed in Figure 8-1. For each problem we
describe how to reduce the problem to Minimum Cost Flow.
Transshipment
There existsmsupply stationssi, each capable of producingsup(si) units of a
commodity. There arendemand stationstj, each demandingdem(tj) units of the
commodity. There arewwarehouse stationswk, each capable of receiving and
reshipping (known as “transshipping”) a maximummaxkunits of the commodity
at the fixed warehouse processing cost ofwpkper unit. There is a fixed shipping
cost ofd(i,j) for each unit shipping from supply stationsito demand stationstj,a
fixed transshipping cost ofts(i,k) for each unit shipped from supply stationsito
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use