10networkflows.ppt

TP SHUAI * Definition 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 (bk0) 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 (bk0) with flow equal to the required demand |bk|. Finding starting feasible solutions Artificial network flow model * Although 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 LP 10.4 Integrality of Optimal Network Flows * When optimal network flows must be integer? Integrality property Lemma 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 matrices Lemma 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. * * * Princeton University ? COS 226 ? Algorithms and Data Structures ? Spring 2003 ? http://www.Princeton.EDU/~cs226 Chapter 10 Shortest Paths and Discrete Dynamic Programming Section 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