The Network Simplex Algorithm

The Network Simplex Algorithm 1 Calculating A Spanning Tree Flow 1 1 -6 2 1 2 4 3 7 3 A tree with supplies and demands. (Assume that all other arcs have a flow of 0) 6 -4 5 3 What is the flow in arc (4,3)? See the animation. 2 What would happen if the flows in nontree arcs were not 0? 1 1 -6 2 7 3 3 1 3 Suppose that nontree arcs had a nonzero flow. How would this change the computations? 6 -4 2 1 4 5 2 3 3 What would happen if the flows in non-tree arcs were not 0? 1 1 Adjust the supplies/demands. -6 2 3 1 3 6 -4 2 2 0 1 4 5 2 3 4 7 3 6 They will be interpreted as excesses and deficits. The compute flows as in the previous method; e.g., what is the flow in (4,3)? 4 What would happen if the flow were negative? If the direction of (4,3) were reversed, the flow in (3,4) would be negative. 1 1 4 3 -6 2 6 1 -2 2 4 7 4 3 6 -4 3 5 3 3 A spanning tree flow is guaranteed to satisfy the supply/demand constraints. It may violate an upper or lower bound. A spanning tree flow is called feasible if it satisfies its upper and lower bound. Otherwise, it is infeasible. 5 Basic Flows A basis structure consists of a spanning tree T, a set L of arcs, and a set U of arcs, such that T ∪ L ∪ U = A. For each (i,j) ∈ L, xij = 0. For each (i,j) ∈ U, xij = uij. The arc flows in T are selected so that each node satisfies its supply/demand constraint. The basis structure is feasible if the arc flows also satisfy the upper and lower bounds. It is possible for a basis structure to be infeasible. In fact, this is normally the case in the dual simplex algorithm. 6 Another way of calculating flows in arcs Case 1. If (i,j) is not in the tree, then xij = 0. 1 1 -6 2 1 2 4 3 7 3 6 -4 The total supply in subset S = (3,4,5) of nodes is 6. How can one satisfy the supply/demand constraints for S? 5 3 7 Another way of calculating flows in arcs 1 1 -6 2 7 3 1 2 4 3 6 -4 5 3 Deleting an arc (i,j) of T splits the nodes into two subsets, S and N-S. To compute the flow in (i,j), compute ∑j∈S b(j). 8 Another way of calculating flows in arcs, general case Case 2. If (i,j) is not in the tree, then xij = 0 or uij Deleting an arc (i,j) of T splits the nodes into two subsets, S -6 2 7 and N-S. 3 Let f(S, N-S) denote the 3 flow across the cutset (S, 1 3 6 -4 N-S) from the non-tree arcs. 1 To compute the flow 4 5 3 in (i,j), compute 2 1 1 2 ∑j∈S b(j) - f(S, N-S). 9 Calculating Simplex Multipliers for a Spanning Tree To calculate node potentials, 0 1 5 -6 2 3 -2 4 7 -4 3 1. Let πi = 0; 6 2. Choose other multipliers so that for each arc (i,j) in the tree cij - πi + πj = 0. 1 5 See the animation. What is the node potential for node 2? 10 An alternative approach for calculating simplex multipliers 0 1 5 -6 2 -4 3 3 -2 4 7 6 1 5 Let πi be the cost of the path from node i to node 1 (the root node) in T. If (j,k) is backward, then use cost -cjk. What is the simplex multiplier for node 4? What is the simplex multiplier for node 6? 11 Optimality Conditions (again) Optimality Conditions for Spanning Tree Solutions: The following are conditions under which x is an optimal solution for the minimum cost flow problem and π is optimal for the dual problem: 1. The basic flow x is feasible 1 2. π is the vector of simplex multipliers. 0 3. For each non-tree arc (i,j) 2 a. if cπij > 0, then xij = 0 0 0 3 6 b. if cπij < 0, then xij = uij What is the flow on arc (5,6) if arc (5,6) satisfies the optimality conditions? 0 0 4 5 0 7 -4 12 Violating Arcs (T, L, U) : x: p: cπij a spanning tree structure. basic feasible flow simplex multipliers. reduced costs A non-tree arc is a violating arc and eligible for entering the basis if i. ii. cπij < 0 and xij = 0 or cπij > 0 and xij = uij. 13 The Network Simplex Pivot 1. Choose a violating non-tree arc. If no such arc exists, then the solution x is optimal. 2. Add (i,j) to T creating a unique cycle C. Send a maximum flow around C while maintaining feasibility. Suppose the exiting arc is (p,q). 3. Update the multipliers so that the reduced costs of all tree arcs are 0 after the pivot. T-(p,q) partitions into two subtrees, T1 and T2 with the root node in T1. Let d = |cπij|. If i Î T1, then add |cπij| to each node v Î T2. If i ∈ T2, then subtract d from each node in T2. 14 The Steps for the network simplex 1. Select the entering arc. Key data structure: maintain the simplex multipliers O(1) step to determine if (i,j) is violating. 2. Determine the basic cycle C. Determine the flow around the basic cycle. Send the flow. 3. Determine the subtree T2 obtained upon deleting the exiting arc from the current spanning tree. Update all multipliers in T2. Fact: Lots of computational work was done in trying to figure out how to do steps 2 and 3 efficiently. For many choices of data structures, the running time to be proportional to |C| + |T2|, and the major concern is the "proportion" or the "constant term." 15 Data Structures for the Network Simplex Algorithm 1. Hang the tree from a root node. 2. For each node, store pred(i), the parent of i in the tree. 3. For each node i store the depth(i), the number of arcs on the path from i to the root. 4. For each node i, store a pointer to the next node on the depth first search ordering of T. This data structure is called the thread. 16 A spanning tree, as part of a spanning tree solution 1 4 5 7 3 6 2 Node 1 is the root node. The tree “hangs” from the root node. 17 The Depth of Nodes, and Predecessors 1 0 1 2 4 5 3 1 6 2 Pred(2) = 5, 3 7 2 3 Pred(3) = 1, etc. 18 The Thread 1 4 5 7 3 6 2 The thread is obtained by performing a depth first search of the tree. Each node points to the next one on the dfs. 19 Finding the Cycle procedure IDENTIFY CYCLE; begin set i : = k and j : = l; while i ≠ j do begin if depth(i) > depth(j) then i : = pred(i) else if depth(j) > depth(i) then j : = pred(j) else i : = pred(i) and j : = pred(j); end; set w : = i; end; Running time is O(|C|) 20 Updating the Multipliers Suppose: (i,j) is pivoted in and that (p,q) is pivoted out. Suppose that T2 consists of node p plus the descendents of p in the tree. Use the thread to trace out T2. Stop when depth(CurrentNode) ≤ depth(p). Running time = O( | T2| ). Updating the data structures. O( |C| + | T2| ). 21 Some Remaining Issues How can we avoid cycling in the simplex method? (Or what do we do if the amount of flow sent around a cycle is 0). What is the worst case performance of the simplex method? What are some good heuristics to speed up performance in practice? 22 Summary 1. Network simplex is extremely fast in practice. 2. Relying on network data structures, rather than matrix algebra, causes the speedups. It leads to simple rules for selecting the entering and exiting variables. 3. Running time per pivot : (i) arcs scanned to identify an entering arc (ii) arcs scanned of the basic cycle (iii) nodes of the subtree 4. A good pivot rule can dramatically reduce running time in practice. 23