MINIMUM COST FLOWS: NETWORK SIMPLEX ALGORITHM A talk by: Lior Teller 1 A short reminder (its been three weeks..) G=(V,E) is a directed graph Capacity ( )function uij > 0 for every Cost functin cij for every

Balance function b(v) for every we will have a number b(v) > 0 supply b(v) < 0 demand cost, capacity and balance are integers 2 Minimum Cost Flows - Definition Flow is a function on the edges. A feasible flow is a flow that satisfies: Capacity constraint: Non negativity constraint:

Mass balance constraint: The cost of a feasible flow f: The min cost flow problem is: find a maximum feasible flow f, with the minimum cost 3 Introduction Cycle Canceling Successive Shortest Paths Primal-Dual Out of Kilter

Polynomial Algorithms Capacity Scaling Today The Simplex Method 4 Introduction - The Simplex Method A powerful method for: solving linear programming solving constrained optimization problems Minimum cost flow problems define a special class of linear programs

Network flow problems have considerable special structure When implementation does not exploit underlying network structure not a competitive solution procedure for solving minimum cost flow problems. Interpreting the concepts of the simplex method appropriately as network operations, we can produce an algorithm that is very efficient Our goal: developing a network-based implementation of the simplex method 5 x We wont describe the simplex method for general linear programming problems and then show how to adapt the method for minimum cost flow problems. We will develop the network simplex method directly in the context

of network flow problems as a particular type of augmenting cycle algorithm. No need for any background in linear programming Building more directly on concepts we have developed already 6 Algorithm Outline The central concept - spanning tree solutions, obtained by fixing the flow of every arc not in a spanning tree either at zero or at the arc's flow capacity. From this we retrieve uniquely the flow on all the arcs in the spanning tree Minimum cost flow problem has at least one optimal spanning tree solution We move from one solution to another to find an optimal spanning tree solution

At each step introducing one new non-tree arc into the spanning tree in place of one tree arc. This method is known as the network simplex algorithm: Spanning trees correspond to the so-called basic feasible solutions of linear programming The movement from one spanning tree solution to another corresponds to a so-called pivot operation of the general simplex method 7 Cycle free and spanning tree solutions For any feasible solution X: Arc (i, j) is a free arc if 0 < xij < uij

Arc (i, j) is a restricted arc if xij = 0 or xij = uij Note that we can both increase and decrease flow on a free arc. In a restricted arc we can only increase or decrease the flow. 8 Cycle Free Solution: A solution X is a cycle free solution if the network contains no cycle composed only of free arcs. Note: in a cycle free solution, we can augment flow on any augmenting cycle in only a single direction (some arc in any cycle will restrict us from either increasing or decreasing that arc's flow).

Spanning Tree Solution A feasible solution X and an associated spanning tree of the network is a spanning tree solution if every non tree arc is a restricted arc. Note: in a spanning tree solution, the tree arcs can be free or restricted 9 Next we establish a fundamental result of network flows: Minimum cost flow problems always have optimal cycle free and spanning tree solutions. The network simplex algorithm will exploit this result by restricting its search for an optimal solution to only spanning tree solutions First we will see some required background for this (a small reminder)

10 Reminder: negative cycles First assume that all arcs are un capacitated The network shown in the figure contains positive flow around a cycle. We define the orientation of the cycle as the same as that of arc (4, 5). Let us augment units of flow along the cycle in the direction of its orientation. Increases flow on forward arcs by units and decreases the flow on backward arcs by units. The per unit incremental cost for this flow change is the sum of the costs of

forward arcs minus the sum of the costs of backward arcs: Per unit change in cost = 2 + 1 + 3 - 4 - 3 = - 1. 11 Augmenting flow in the cycle decreases the cost We set as large as possible while keeping all arc flows non negative We must satisfy the inequalities: 3 - 0 and 4 - 0 We set = 3 Some arc in the cycle has a flow at value zero The objective function value is strictly less than the initial solution 12

We can extend this observation in several ways: a positive per unit change in cost () means we set as small as possible If = 0, we are indifferent to all solutions in the interval If we impose upper bounds on the flow the range of flow that preserves feasibility an interval 13 (Cycle Free Property). If the objective function of a minimum cost flow problem is bounded from below over the feasible region, the

problem always has an optimal cycle free solution. Proof: (With respect to a given flow x): Arc (i, j) is a free arc if 0 < xij < uij or restricted arc if xij = 0 or xij = uij Solution x has the cycle free property - contains no cycles entirely consisting of free arcs. If a solution x contains a cycle (i.e. it is not cycle free) calculate the cycle cost If the cycle cost is negative we send flow around the cycle in the direction of traversal If it is positive send flow around the cycle in the opposite direction In either of these cases we make as large as possible Cycle must be eliminating If the cycle cost is 0 we can remove the cycle by increasing the flow in either direction Applying this argument repeatedly removes all cycles from the solution. 14

(Spanning Tree Property) If the objective function of a minimum cost flow problem is bounded from below over the feasible region, the problem always has an optimal spanning tree solution. Proof: (This is an extension of the cycle free property): Let S be the set of free arcs If the free arcs connect all the nodes of G, then the solution is connected and acyclic (from the cycle free property) thus forming a spanning tree Otherwise, we add to S some restricted arcs until S connects all the nodes. The set S now forms a spanning tree of G, and the feasible

solution x form which S is derived is referred to as a spanning tree solution. 15 A spanning tree solution partitions the arc set A into three subsets: T - the arcs in the spanning tree L - the non-tree arcs whose flow is zero U - the non-tree arcs whose flow is the arcs flow capacities We refer to the triplet (T, L, U) as a spanning tree structure. we can associate a spanning tree structure with a spanning tree solution 16

Also possible: spanning tree structure spanning tree solution We can also obtain a unique spanning tree solution corresponding to a given spanning tree structure (T, L, U): set xij = 0 for all arcs (i, j) L set xij = uij for all arcs (i, j) U Determine the flow values for arcs in T we will see how later 17 A Spanning tree can be: Non-degenerate: every arc in a spanning tree solution is a free arc Degenerate (): otherwise

A spanning tree structure as feasible if its associated spanning tree solution is a feasible solution of the minimum cost flow problem. A spanning tree structure as optimal if its associated spanning tree solution is an optimal solution of the minimum cost flow problem. 18 The optimality condition : 19

Proof: Let X* be the solution associated with the spanning tree structure (T, L, U). Some set of node potentials together with the spanning tree structure (T, L, U), satisfies (11.1). Need to show X* is an optimal solution of the min cost flow problem. As we have already seen in class, minimizing is equivalent to minimizing 20 Proof (continued): This is equavilent to minimizing:

By the definition of solution X*: for all for all The expression implies that the objective function value of the solution X will be greater than or equal to x*. 21 Maintaining a spanning tree structure Algorithm moves from one feasible spanning to another (pivot operation)

Stops when the spanning tree structure satisfies the optimality condition At each iteration, the algorithm adds one arc to the spanning tree in place of one of its current arcs. The entering arc is a non-tree arc violating its optimality condition. The algorithm adds this arc to the spanning tree, creating a negative cycle It sends the maximum possible flow in this cycle Drops an arc whose flow has reached its lower or upper bound We need a data structure to support this.. 22 Spanning tree data structure Predecessor index: Each node i has

a unique path from the root. The index pred(i) stores predecessor of i on this path. the Depth index: The index depth(i) stores the number of arcs on the path from the root to i. Thread index: defines a traversal of a tree. set to be the node in the depth-first search encountered just

after the node itself. Provide a convenient means for visiting all descendants of a node. 23 Computing node potentials the network simplex algorithm moves from one spanning tree to the next maintaining =0 for every arc (i, j) in the current spanning tree. We wish to calculate note potentials for this purpose: Adding a constant to all node potential does not alter reduced costs Therefore, one node potential can be arbitrary we set (1) = 0

Using we can calculate all other node potentials by using the thread indices (example?) 24 Computing flows Every spanning tree structure (T, L, U) defines a unique flow x xij = 0 for all arcs (i, j) L xij = uij for all arcs (i, j) U To ease our discussion, for the moment let us first consider the uncapacitated version of

the minimum cost flow problem Deleting a tree arc (i,j) from the spanning tree decomposes the tree into two subtrees Let T1 be the subtree containing node i and let T2 be the subtree containing node j The cumulative balance of nodes in T1 must be equal to that of T2 In the spanning tree, arc (i, j) is the only arc that connects the subtree T1 to T2 must units of flow 25 Working up from the leaves it is possible to calculate all arc flows (wont go into details.. Need some intuition?) For the capacitated version of the problem, we add this initialization:

(wont go into details.. Need some intuition?) 26 Network Simple Algorithm The network simplex algorithm maintains a feasible spanning tree structure at each iteration and successively transforms it into an improved spanning tree structure until it becomes optimal. 27 Obtaining an Initial Spanning

Tree Structure Solve the maximum flow problem feasible solution Construct an initial spanning tree structure by converting this solution into a spanning tree solution 28 Optimality Testing and the Entering Arc To determine weather a spanning tree structure is optimal we check:

If the spanning tree structure satisfies the conditions it is optimal we terminate Else, the algorithm selects a non-tree violating arc to enter the tree: 29 Pivot Rules For any eligible arc (i, j) we refer to IcijI as its violation. The network simplex algorithm can select any eligible arc to enter the tree and still would terminate finitely (with some provisions for dealing with degeneracy) Pivot rules for selecting entering arcs:

Dantzig's pivot rule First eligible arc pivot rule Candidate list pivot rule 30 Dantzig's pivot rule At each iteration - select an arc with the maximum violation to enter the tree. Motivation - the arc with the maximum violation causes the maximum decrease in the objective function per unit change in the value of flow on the selected arc maximum decrease per pivot The algorithm performs fewer iterations than other choices for the pivot rule. However, The algorithm must consider every non tree

very time consuming. the algorithm is not attractive. 31 First eligible arc pivot rule Scan the arc list sequentially and select the first eligible arc to enter the tree In a popular version of this rule, we examine the arc list in a wraparound fashion Quickly identifies the entering arc the algorithm generally performs more iterations than it would with other pivot rules because each pivot operation produces a relatively

small decrease in the objective function value 32 Candidate list pivot rule Selects the entering arc using a two-phase procedure consisting of major iterations and minor iterations: major iteration: construct a candidate list of eligible arcs. o Examine arcs emanating from a node and add eligible arcs to the candidate list. o We repeat this process for next nodes until the list has reached max size or we have examined all the nodes. o Next major iteration begins with the node of the previous major iteration and examines nodes in wraparound minor iterations: in each iteration selects an eligible arc from the candidate list with the maximum violation o Scans arcs in candidate list and selects maximum violation arc to enter the tree o Removes arcs that are no longer eligible from candidate list (due to changes in the node potentials)

o Once the candidate list becomes empty or a reached limit on the number of minor iterations per major iteration we rebuild the candidate list by performing another major iteration 33 Candidate list pivot rule (continued) By setting the: maximum allowable size of the candidate list number of minor iterations per major iteration we can obtain numerous different pivot rules. Example:

- Dantzig's pivot rule: number of minor iterations per major iteration = 1 - First eligible arc pivot rule: maximum allowable size of the candidate list = 1 34 Leaving Arc Suppose (k, l) is the entering arc Creates exactly one pivot cycle W Orientation of the cycle: Same as that of (k, l) if (k, I) L opposite the orientation of (k, l) if (k, I) U

Let and denote the sets of forward arcs and backward arcs in the pivot cycle Maximum flow change on an arc (i, j) W: We can augment flow along W feasibly 35 We refer to any arc (i, j) W that defines as a blocking arc We then augment units of flow and select an arc (p, q) with pq = A pivot iteration is non-degenerate if > 0 and is degenerate if = O A degenerate iteration occurs only if T is a degenerate spanning tree. Observe: two arcs tie while determining the value of

the next spanning tree will be degenerate. 36 Identifying the pivot cycle P(i) denotes the unique path from any node i to the root node Pivot cycle consists of the arcs {(k, I)} U P(k) U P(l) - (P(k) P(l)) Find first common ancestor if k and l in O(n) using pred and depth (example?) Note: is the net decrease in the cost per unit flow sent around the pivot cycle W (example? Remember that and (1) = 0 imply is the cost from the root

to u) 37 Updating the Tree When leaving arc (p, q) is determined for a given entering arc (k, I), we updates the tree structure If the leaving arc is the same as the entering arc, (when = pq =upq), the tree does not change. the arc (k, I) merely moves from the set L to the set U, or vice versa. Else, the algorithm must perform more extensive changes. The arc (p, q) becomes a non-tree arc at its lower or upper bound, depending on

whether (in the updated flow) X pq = 0 or X pq = u pq Adding arc (k, I) to the current spanning tree and deleting arc (p, q) creates a new spanning tree the node potentials also change 38 Updating node potentials Deleting (p, q) from the previous tree partitions the set of nodes into two sub-trees TI containing the root node T2 not containing the root node. This sub-tree hangs from node p or node q

The arc (k, I) has one endpoint in TI and the other in T2 The conditions (1) = 0 and Cij - (i) + (j) = 0 imply: Node potentials in TI remain unchanged If l T2 the node potentials in T2 decrease by (homework) If k T2 the node potentials in T2 increase by (which is negative) Using thread and depth indices we update the node potentials quickly 39

Termination Algorithm moves from one feasible spanning tree solution to another Stops when the spanning tree structure satisfies the optimality condition If each pivot operation is non-degenerate, the algorithm terminates finitely: Recall is the net decrease in the cost per unit flow sent around the pivot cycle W. After a non-degenerate pivot the cost of the new spanning tree structure is * units less Every spanning tree structure has a unique associated cost The network simplex algorithm will encounter any spanning tree structure at most once The network has a finite number of spanning tree structures The algorithm will terminate finitely.

Degenerate pivots, pose a difficulty: The algorithm might not terminate finitely 40 Strongly feasible spanning trees A poor choice of entering and leaving arcs leads to cycling (i.e., an infinite repetitive sequence of degenerate pivots) Degeneracy is both a theoretical and practical issue We will maintaining a special type of spanning tree, a strongly feasible spanning tree We will show the network simplex algorithm terminates finitely 41

Terminology and definitions The tree arcs are either: upward pointing (toward the root) downward pointing (away from the root) Strongly feasible spanning tree: 1. A spanning tree T is strongly feasible if every tree arc with zero flow is upward pointing and every tree arc whose flow equals its capacity is downward pointing 2. A spanning tree T is strongly feasible if we can send a positive amount of flow from any node to the root along the tree path without violating any flow bound 42

We wish implement the network simplex algorithm so that it always maintains a strongly feasible spanning tree must first find an initial strongly feasible spanning tree We append to the problem an artificial node, with index n + 1 referred to as the root, and an artificial arc for each node of the original problem. Each artificial arc will have lower bound zero, upper bound infinity, and a high cost C For each node i V, we add the arc (i, r) and assign flow xir = b(i) if b(i) > 0, and arc (r, i) with flow xir = -b(i) otherwise satisfies all supply and demand constraints Strongly feasible 43

Note that a non-degenerate spanning tree is always strongly feasible A degenerate spanning tree might or might not be strongly feasible Algorithm creates a degenerate spanning tree from a non-degenerate spanning tree whenever two or more arcs are qualified as leaving arcs and we drop only one of these Therefore, the algorithm needs to select the leaving arc carefully so that the next spanning tree is strongly feasible. 44 Leaving Arc Rule: select the leaving arc as the

last blocking arc encountered in traversing the pivot cycle W along its orientation starting at the apex w. We show that the leaving arc rule guarantees that in the next spanning tree every node in the cycle W can send a positive amount of flow to the root node. 45 Property: Each node in the segment W2 can send a positive amount of flow to the root in the next spanning tree

Arc (p, q) is the last blocking arc in W No arc in W2 is blocking Every node in this segment can send a positive amount of flow to the root via node w (the apex) along the orientation of W2 46 Property: Each node in the segment W1 can send a positive amount of flow to the root in the next spanning tree We prove this observation by considering two cases: 1. If the previous pivot was a non-degenerate pivot, the pivot augmented a positive amount of flow along the arcs in W1. After the augmentation, every node in W1 can send a positive

amount of flow back to the root opposite to the orientation of W1 via the apex node w (each node can send at least units to the apex and then at least some of this flow to the root since the previous spanning tree was strongly feasible) 2. If the previous pivot was a degenerate pivot, W1 must be contained in the segment of W between node w and node k because the property of strong feasibility implies that every node on the path from node I to node w can send a positive amount of flow to the root before the pivot, and thus no arc on this path can be a blocking arc in a degenerate pivot. Now observe that before the pivot, every node in W1 could send a positive amount of flow to the root, and since the pivot does not change flow values, every node in W1 must be able to send a positive amount of flow to the root after the pivot as well. 47

We next show that in the next spanning tree, nodes not belonging to the cycle W can also send a positive amount of flow to the root In the previous spanning tree (before the augmentation), every node j could send a positive amount of flow to the root and if the tree path from node j does not pass through the cycle W, the same path is available to carry a positive amount of flow in the next spanning tree If the tree path from node j does pass through the cycle W, the segment of this tree path to the cycle W is available to carry a positive amount of flow in the next spanning tree and once a positive amount of flow reaches the cycle W, then, as shown earlier, we can send it (or some of it) to the root node This completes the proof that the next spanning tree is strongly feasible. 48

We now establish the correctness of the network simplex algorithm: We have previously shown that each non-degenerate pivot strictly decreases the objective function value The number of non-degenerate pivots is finite The algorithm can, however, also perform degenerate pivots We will show that the number of successive degenerate pivots between any two non-degenerate pivots is finitely bounded. 49 Suppose that arc (k, l) enters the spanning tree at its lower bound and in doing so it defines a degenerate pivot

In this case, the leaving arc belongs to the tree path from node k to the apex w Just as seen before, node k lies in the tree for which the potentials of all nodes change by an amount . Since < 0, this degenerate pivot strictly decreases the sum of all node potentials Since no node potential can fall below n*C, the number of successive degenerate pivots is finite. 50 If the entering arc (k, l) is at its upper bound, we define the orientation of the cycle Was opposite to the orientation of arc (k, I) The criteria for selecting the leaving arc remains unchanged

In this case node I is contained in the subtree for which the potentials of all the nodes decrease by the amount > 0 The pivot again decreases the sum of the node potentials And this sums up our proof! 51