Network Optimization - The Network Simplex Algorithm

Optimization Methods Network Optimization 1 Network Optimization 1.1 Why do we care? Networks and associated optimization problems constitute reoccurring structures in many real-world applications. The network structure often leads to additional insight and improved understanding. Given integer data, the standard models have integer optimal solutions. The network structure also enables us to design more ecient algorithms. Slide 1 1.2 A Comparison 1.2.1 Running Times Algorithm Standard Simplex Network Simplex Ratio Running Time (sec) 334.59 7.37 2.2 % # Iterations 42759 23306 54 % Slide 2 Average over 5 random instances with 10 000 nodes and 25 000 arcs each. 2 Outline 2.1 Today's Lecture � � � � The Simplex Algorithm: A Reminder The Network Simplex: A Combinatorial View The Network Simplex: An Animated View The Network Simplex: An Algebraic View Slide 3 3 The Simplex Algorithm 3.1 A Reminder 3.1.1 The Problem Slide 4 min s:t: cx Ax = b x � 0 0 1 4 The Simplex Algorithm 4.1 A Reminder 4.1.1 The Algorithm 1. Start with basis B = AB : : : AB m ] and BFS x. 2. Compute cj = cj ; cB B Aj . (1) ( Slide 5 ) ;1 0 If cj  0 x optimal stop. Select j such that cj < 0. xB(i) = xB(`) . 3. Compute u = B 1 Aj .  = 1 i min u` m ui >0 ui 4. Form a new basis by replacing AB(`) with Aj . 5. yj =  yB(i) = xB(i) ;  ui .  ;     5 The Network Simplex Algorithm 5.1 The Problem 5.1.1 Combinatorially Determine a least cost shipment of a commodity through a network in order to satisfy demands at certain nodes from available supplies at other nodes. Arcs have costs associated with them. 5.1.2 Algebraically Slide 7 Network G = (N A). Arc costs c : A ! Z . Node balances b : N ! Z . min s.t. X j:(i j) A ( X cij xij ijX A xij ; 2 Slide 6 )2 j:(j i) A 2 xji = bi for all i 2 N xij  0 for all (i j ) 2 A 5.2 Tree Solutions 5.2.1 Denition A tree is a graph that is connected and has no cycles. A spanning tree of a graph G is a subgraph that is a tree and contains all nodes of G. A
ow x forms a tree solution with a spanning tree of the network if every non-tree arc has
ow 0. 2 Slide 8 5.2.2 Computing the Flow Slide 9 5.2.3 Trees vs. Tree Flows � � Every tree ow has a corresponding tree (and perhaps more than one). Given a tree, we obtain a unique tree ow associated with it. 5.2.4 BFS Property Theorem 1 If the objective function is bounded from below, a min-cost ow problem Slide 10 Slide 11 always has an optimal tree solution. 5.2.5 Optimality Condition Theorem 2 A (feasible) tree T is optimal if, for some choice of node potentials pi , (a) cij = cij ; pi + pj = 0 for all (i j ) 2 T , (b) cij = cij ; pi + pj  0 for all (i j ) 2 A n T . Proof: P P min (i j) A cij xij is equivalent to min (i j) A cij xij . P P min (i j) A cij xij is equivalent to min (i j) A T cij xij . For any solution x, xij
xij for all (i j ) 2 A n T . 2 2 2 2  3 n Slide 12 5.2.6 Computing Node Potentials 5.2.7 Updating the Tree Slide 13 Slide 14 5.3 Overview of the Algorithm 1. Determine an initial feasible tree T . Compute ow x and node potentials p associated with T . 2. Calculate cij = cij ; pi + pj for (i j ) 26 T . If c  0, x optimal stop. Select (i j ) with cij < 0. 3. Add (i j ) to T creating a unique cycle C . Send a maximum ow around C while maintaining feasibility. Suppose the exiting arc is (k `). 4. T := (T n (k `))  (i j ). Slide 15 6 Min-Cost Flow 6.1 Integrality Our reasoning has two important and far-reaching implications: There always exists an integer optimal ow (if node balances bi are integer). 4 Slide 16 There always exist optimal integer node potentials (if arc costs cij are integer). 7 The Network Simplex Algorithm 7.1 An Animation 7.2 The Algebraic View � � � � Slide 17 Bases and trees. Dual variables and node potentials. Changing bases and updating trees. Optimality testing. 7.2.1 Bases vs. Trees The constraint matrix A of the min-cost ow problem is the node-arc incidence matrix of the underlying network. 1 2 3 4 5 6 7 Slide 18 Slide 19 (1 2) (2 6) (3 2) (4 3) (4 5) (5 3) (5 6) (6 7) (7 1) +1 0 0 0 0 0 0 0 ;1 ;1 +1 ;1 0 0 0 0 0 0 0 ;1 0 0 0 0 0 +1 ;1 0 0 0 +1 +1 0 0 0 0 0 0 0 0 ;1 +1 +1 0 0 0 ;1 0 0 0 0 ;1 +1 0 0 0 0 0 0 0 0 ;1 +1 The rows of A are linearly dependent. Let B be the submatrix corresponding to the tree 1 2 3 4 5 6 7 (1 2) (2 6) (3 2) (4 3) (5 3) (7 1) +1 0 0 0 0 ;1 ;1 +1 ;1 0 0 0 0 0 0 +1 ;1 ;1 0 0 0 +1 0 0 0 0 0 0 +1 0 0 ;1 0 0 0 0 0 0 0 0 0 +1 5 Slide 20 Slide 21 Let B be the submatrix corresponding to the tree 4 5 6 7 3 2 1 (1 2) (2 6) (3 2) (4 3) (5 3) (7 1) 0 0 0 +1 0 0 0 0 0 0 +1 0 0 ;1 0 0 0 0 0 0 0 0 0 +1 0 0 +1 ;1 ;1 0 ;1 +1 ;1 0 0 0 +1 0 0 0 0 ;1 Permuting Rows Let B be the submatrix corresponding to the tree 4 5 6 7 3 2 1 Slide 22 (4 3) (5 3) (2 6) (7 1) (3 2) (1 2) +1 0 0 0 0 0 0 +1 0 0 0 0 0 0 ;1 0 0 0 0 0 0 +1 0 0 ;1 ;1 0 0 +1 0 0 0 +1 0 ;1 ;1 0 0 0 ;1 0 +1 Permuting Columns Slide 23 Corollary 1 (a) The matrix A has rank n ; 1. (b) Every tree solution is a basic solution. Theorem 3 Every tree denes a basis and, conversely, every basis denies a tree. Suppose the graph dened by a basis contains a cycle 1 ; 2 ; 3 ; 4 ; 5 ; 6: 6 Slide 24 1 2 3 4 5 6 (1 2) (2 3) (4 3) (5 4) (5 6) (1 6) +1 0 0 0 0 +1 ;1 +1 0 0 0 0 0 ;1 ;1 0 0 0 0 0 +1 ;1 0 0 0 0 0 +1 +1 0 0 0 0 0 ;1 ;1 7.2.2 Dual Variables vs. Node Potentials Remember, the simplex algorithm computes the dual variables p as the solution to p B = cB . 0 +1 0 0 0 0 0 1 B 0 +1 0 0 0 0 C B C B 0 0 ;1 0 0 0 C C (p4 p5 p6 p7 p3 p2 ) B B 0 0 0 +1 0 0 C B @ ;1 ;1 0 0 +1 0 CA 0 0 +1 0 ;1 ;1 0 0 Slide 25 = (c43 c53 c26 c71 c32 c12 ) Hence, p2 = ;c12 , p3 = c32 + p2 , p7 = c71 , . .. 7.2.3 Optimality Testing Remember, the simplex algorithm computes the reduced costs c as cij = cij ; p Aij . 0 1 2 3 4 5 6 7 Slide 26 (1 2) (2 6) (3 2) (4 3) (4 5) (5 3) (5 6) (6 7) (7 1) +1 0 0 0 0 0 0 0 ;1 ;1 +1 ;1 0 0 0 0 0 0 0 0 +1 ;1 0 ;1 0 0 0 0 0 0 +1 +1 0 0 0 0 0 0 0 0 ;1 +1 +1 0 0 0 ;1 +1 0 0 ;1 0 0 0 0 0 0 0 0 0 0 ;1 +1 Therefore, cij = cij ; pi + pj . 7.3 Summary The network simplex algorithm is extremely fast in practice. Relying on network data structures, rather than matrix algebra, causes the speedups. It leads to simple rules for selecting the entering and exiting variables. Running time per pivot: { arcs scanned to identify an entering arc, { arcs scanned of the basic cycle, 7 Slide 27 { nodes of the subtree. A good pivot rule can dramatically reduce running time in practice. 8