10 network flows

nullChapter 10 Shortest Paths and Discrete Dynamic ProgrammingChapter 10 Shortest Paths and Discrete Dynamic ProgrammingSection 1 Graphs, Networks, and Flows Section 2 Cycle Directions for Network Flow Search Section 3 Rudimentary Cycle Directions Search Algorithms for Network Flows Section 4 Integrality of Optimal Network Flows Section 5 Transportation and Assignment Models Section 6 Other Single-Commodity Network Flow Models Section 7 Network Simplex Algorithm for Optimal Flows Section 8 Cycle Canceling Algorithms for Optimal Flows Section 9 Multicommodity and Gain/Loss Flows*Tianping Shuai School of Science, BUPT10.1 Graphs, Networks, and Flows10.1 Graphs, Networks, and Flows*Digraphs, Nodes, and ArcsD=(V,A)V={nodes/vertices of the network} A={arcs of the network}Example 10.1 Optimal Ovens (OOI)OOI makes home toaster ovens at plants in Wisconsin and Alabama. Completed ovens are shipped by rail to one of OOI’s two warehouses in Memphis and Pittsburgh, and then distributed to customer facilities in Fresno, Peoria, and Newark. The two warehouses can also transfer small quantities of ovens between themselves, using company trucks. Our task is to plan OOI’s distribution of new model E27 ovens over the next month. Each plant can ship up to 1000 units during this period, and none are presently stored at warehouses. Frenso, Peoria, and Newark customers require 450,500, and 610 ovens, respectively. Transfers between the warehouses are limited to 25 ovens, but no cost is charged. Unit costs (in dollars) of other possible are detailed in the following tables. OOI Example NetworkOOI Example Network*nullOOI Example*Minimum cost flow modelsMinimum cost flow models*Definition 1. Decision variables xi,j in network flow models reflect the amount of flow in arcs (i,j).Letting ci,j denote the unit cost of flow on arc (i,j), the total cost to be minimized is implyConstraints: flows must be nonnegative to make sense. and capacities/ upper bounds uij may apply.(10.1).Fact 2. Main constraints of network flow problems enforce balance (or conservation) of flow at nodes.nullMore precisely, we want*(total flow in)- (total flow out) = specified net demand at every node. In symbols,(10.2) where bk denotes the specified net demand (required flow inbalance) at node k.Definition 10.3. The minimum cost network flow model for a digraph on nodes kV with net demands bk, and arcs (i,j) A with capacity ui,j and unit cost ci,j isSources, Sinks, and Transshipment NodesSources, Sinks, and Transshipment NodesSink or demand nodes: such as the customer sites in OOI model Source or supple nodes: such as the OOI plants create flow Transshipment nodes: such as OOI warehouses merely pass along flow. *Fact 10.4 Net demand bk is positive at sink (demand) nodes, negative at source (supply) nodes, and zero at transshipment nodes. nullOOI example Model*(10.3)null*null*Total Supply=Total DemandTotal Supply=Total DemandLemma 10.5. If total supply is less than total demand in a given network flow problem, the problem is infeasible. If total supply exceeds total demand, a new sink node should be added to consume excess demand via zero-cost arcs from all source.*Node 8 in Figure 10.2 was added because total supply=1000+1000> 450+500+610=total demand Node-arc incidence matrices and matrix standard formMin cx s.t. Ax=b (10.4) 0xunullDefinition 10.6 Node-arc incidence matrices represent both the flow balance requirements and the graph structure of a network flow model with a row for every node and a column for every arc. The only nonzero entries in each column are a 1 in the row for the node the corresponding arc leaves and a +1 in the row for the node the arc enters *10.2 Cycle directions for network flow search10.2 Cycle directions for network flow search*Definition 10.7 A chain is a sequence of arcs connecting two nodes. Each arc has exactly one node in common with its predecessor in the sequence, and no node is visited more than once.Chains, Paths, Cycle, and DicyclesDefinition 10.8 A cycle is a chain with the same beginning and ending node.Definition 10.9 Paths are chains that transmit all arcs in the forward direction. Definition 10.10 Dicycles are cycles that have all arcs oriented in the same direction. Figure 10.4 chains and cycles of the OOI network Figure 10.4 chains and cycles of the OOI network *Figure 10.4 chains and cycles of the OOI network Figure 10.4 chains and cycles of the OOI network *Cycle directionCycle directionForward : with direction, Reverse: against direction.*Definition 10.11 : A cycle direction of a minimum cost network flow model increases flow on forward arcs and decreases flow on reverse arcs of a cycle in the given digraph; that isnull*Maintaining Flow Balance with Cycle DirectionsMaintaining Flow Balance with Cycle Directions*Lemma 10.12: Adjusting a feasible flow along a cycle direction of a network flow model leaves flow balance constraints satisfied.Figure 10.5 possible ways a cycle can visit a node(a) forward-forward(b) forward-reverse(c) reverse-forward(d) reverse-reverseFeasible cycle directionsFeasible cycle directions*Definition 10.13 A cycle direction x is a feasible direction at current solution x iff xi,j >0 on all reverse arcs of the cycle, and xi,j < ui,j on all forward arcs.null*Improving cycle directionImproving cycle directionThe simple +1,-1, 0 coefficient structure of cycle directions make this test easy to apply:*Feasible cycle directions aid a search for an optimal flow only if they improve the objective function. By principle 3.18, this will be true if cx<0 for minimizing model. null*Lemma 10.14 A cycle direction improves for a minimum cost network flow model if the difference of total forward arc cost and total reverse arc cost < 0Cycle 2-4-7-3-2 of Fig. 10.7 is a both feasible and improving direction. (total forward) – (total reverse)= (7+5)-(17+4)=-9 < 0Step size with cycle direction Lemma 10.15 Steps from feasible flow x in cycle direction x retain feasibility for step sizes up to =min{+,}, wherenullReturn to cycle 2-4-7-3-2 of Fig. 10.7 and the flow x(0) of Fig. 10.6 Thus ,610 is the largest step we can take in that cycle direction without losing feasibility.Sufficiency of cycle directionsTheorem 10.16 A feasible flow in a minimum cost network flow problem is (globally) optimal if and only if it admits no improving feasible cycle direction.nullTheorem 10.17 Every direction x satisfying Ax=0 for node-arc incidence matrix A of a minimum cost network flow model can be decomposed into a weighted sum of cycle directions. Furthermore, ifx is feasible and improving, at least one of the cycle directions will also be feasible and improving.null*null10.3 Rudimentary Cycle Direction Search Algorithms for Network Flows10.3 Rudimentary Cycle Direction Search Algorithms for Network FlowsRudimentary cycle direction search of the OOI example*null*null*null*null*nullnullDefinition 10.18 An artificial network model and starting point for computing initial feasible solutions in minimum cost network flow problems can be constructed by (1) assigning 0 flow to all arcs of the original model, (2) introducing an artificial node, (3) creating artificial arcs from each supply node k (bk<0) to the artificial node with flow equal to the specified supply |bk|, and (4) adding artificial arcs from the artificial node to each demand node k (bk>0) with flow equal to the required demand |bk|.Finding starting feasible solutionsArtificial network flow modelnull*Network flows versus LPAlthough nay minimum cost network flow problem can be solved by the general-purpose linear programming methods of Chapter 5 and 6, implementations of cycle direction search algorithm 10A usually prove much more efficient.*Network flows versus LP10.4 Integrality of Optimal Network Flows10.4 Integrality of Optimal Network Flows*When optimal network flows must be integer?Integrality propertyLemma 10.20 If a minimum cost network flow model with integer constraint data (supplies, demands, and capacities) has any optimal solution, it has an integer optimal solution.Total unimodularity of node-arc incidence matricesLemma 10.21 The constraint matrix A of a LP is totally unimodular if each square submatrix has determinant +1, 0, or -1.Lemma 10.22 Node-arc incidence matrices of network flow models are totally unimodular.