NETWORK OPTIMIZATION MODELS:THE NETWORK SIMPLEX METHOD

THE NETWORK SIMPLEX METHOD

The network simplex method is a highly streamlined version of the simplex method for solving minimum cost flow problems. As such, it goes through the same basic steps at each iteration—finding the entering basic variable, determining the leaving basic variable, and solving for the new BF solution—in order to move from the current BF solution to a better adjacent one. However, it executes these steps in ways that exploit the special net- work structure of the problem without ever needing a simplex tableau.

You may note some similarities between the network simplex method and the transportation simplex method presented in Sec. 9.2. In fact, both are streamlined versions of the simplex method that provide alternative algorithms for solving transportation problems in similar ways. The network simplex method extends these ideas to solving other types of minimum cost flow problems as well.

In this section, we provide a somewhat abbreviated description of the network simplex method that focuses just on the main concepts. We omit certain details needed for a full computer implementation, including how to construct an initial BF solution and how to perform certain calculations (such as for finding the entering basic variable) in the most efficient manner. These details are provided in various more specialized textbooks such as Selected Reference 1.

Incorporating the Upper Bound Technique

The first concept is to incorporate the upper bound technique described in Sec. 8.3 to deal efficiently with the arc capacity constraints xij ::: uij. Thus, rather than these constraints being treated as functional constraints, they are handled just as nonnegativity constraints are. Therefore, they are considered only when the leaving basic variable is determined. In particular, as the entering basic variable is increased from zero, the leaving basic variable is the first basic variable that reaches either its lower bound (0) or its upper bound (uij). A nonbasic variable at its upper bound xij = uij is replaced with xij = uij - yij, so yij = 0 becomes the nonbasic variable. See Sec. 8.3 for further details.

In our current context, yij has an interesting network interpretation. Whenever yij be- comes a basic variable with a strictly positive value (::: uij), this value can be thought of as flow from node j to node i (so in the “wrong” direction through arc i --- j) that, in ac- tuality, is canceling that amount of the previously assigned flow (xij = uij) from node i to node j. Thus, when xij = uij is replaced with xij = uij - yij, we also replace the real arc i --- j with the reverse arc j --- i, where this new arc has arc capacity uij (the maximum amount of the xij = uij flow that can be canceled) and unit cost - cij (since each unit of flow canceled saves cij). To reflect the flow of xij = uij through the deleted arc, we shift this amount of net flow generated from node i to node j by decreasing bi by uij and increasing bj by uij. Later, if yij becomes the leaving basic variable by reaching its upper bound, then yij = uij is replaced with yij = uij - xij with xij = 0 as the new

nonbasic variable, so the above process would be reversed (replace arc j --- i by arc i --- j, etc.) to the original configuration.

To illustrate this process, consider the minimum cost flow problem shown in Fig. 10.12. While the network simplex method is generating a sequence of BF solutions, suppose that xAB has become the leaving basic variable for some iteration by reaching its up- per bound of 10. Consequently, xAB = 10 is replaced with xAB = 10 - yAB, so yAB = 0 becomes the new nonbasic variable. At the same time, we replace arc A --- B with arc B --- A (with yAB as its flow quantity), and we assign this new arc a capacity of 10 and a unit cost of -2. To take xAB = 10 into account, we also decrease bA from 50 to 40 and increase bB from 40 to 50. The resulting adjusted network is shown in Fig. 10.16.

We shall soon illustrate the entire network simplex method with this same example, start- ing with yAB = 0 (xAB = 10) as a nonbasic variable and so using Fig. 10.16. A later iteration will show xCE reaching its upper bound of 80 and so being replaced with xCE = 80 - yCE, and so on, and then the next iteration has yAB reaching its upper bound of 10. You will see that all these operations are performed directly on the network, so we will not need to use the xij or yij labels for arc flows or even to keep track of which arcs are real arcs and which are reverse arcs (except when we record the final solution). Using the upper bound technique leaves the node constraints (flow out minus flow in = bi) as the only functional constraints. Minimum cost flow problems tend to have far more arcs than nodes, so the resulting num- ber of functional constraints generally is only a small fraction of what it would have been if the arc capacity constraints had been included. The computation time for the simplex method goes up relatively rapidly with the number of functional constraints, but only slowly with the number of variables (or the number of bounding constraints on these variables). Therefore, incorporating the upper bound technique here tends to provide a tremendous saving in computation time.

However, this technique is not needed for uncapacitated minimum cost flow problems (including all but the last special case considered in the preceding section), where there are no arc capacity constraints.

Correspondence between BF Solutions and Feasible Spanning Trees

The most important concept underlying the network simplex method is its network representation of BF solutions. Recall from Sec. 10.6 that with n nodes, every BF solution has (n - 1) basic variables, where each basic variable xij represents the flow through arc i --- j. These (n - 1) arcs are referred to as basic arcs. (Similarly, the arcs corre- sponding to the nonbasic variables xij = 0 or yij = 0 are called nonbasic arcs.)

A key property of basic arcs is that they never form undirected cycles. (This property prevents the resulting solution from being a weighted average of another pair of feasible solutions, which would violate one of the general properties of BF solutions.) However, any set of n - 1 arcs that contains no undirected cycles forms a spanning tree. Therefore, any complete set of n - 1 basic arcs forms a spanning tree.

Thus, BF solutions can be obtained by “solving” spanning trees, as summarized below. A spanning tree solution is obtained as follows:

1. For the arcs not in the spanning tree (the nonbasic arcs), set the corresponding vari- ables (xij or yij) equal to zero.

2. For the arcs that are in the spanning tree (the basic arcs), solve for the corresponding

variables (xij or yij) in the system of linear equations provided by the node constraints.

(The network simplex method actually solves for the new BF solution from the current one much more efficiently, without solving this system of equations from scratch.) Note that this solution process does not consider either the nonnegativity constraints or the arc capacity constraints for the basic variables, so the resulting spanning tree solution may or may not be feasible with respect to these constraints—which leads to our next definition:

A feasible spanning tree is a spanning tree whose solution from the node con- straints also satisfies all the other constraints (0 ::: xij ::: uij or 0 ::: yij ::: uij).

With these definitions, we now can summarize our key conclusion as follows: The fundamental theorem for the network simplex method says that basic solutions are spanning tree solutions (and conversely) and that BF solutions are solutions for feasible spanning trees (and conversely).

To begin illustrating the application of this fundamental theorem, consider the network shown in Fig. 10.16 that results from replacing xAB = 10 with xAB = 10 - yAB for our example in Fig. 10.12. One spanning tree for this network is the one shown in Fig. 10.3e, where the arcs are A --- D, D --- E, C --- E, and B --- C. With these as the basic arcs, the process of finding the spanning tree solution is shown below. On the left is the set of node constraints given in Sec. 10.6 after 10 - yAB is substituted for xAB, where the basic variables are shown in boldface. On the right, starting at the top and moving down, is the sequence of steps for setting or calculating the values of the variables.

Since the values of all these basic variables satisfy the nonnegativity constraints and the one relevant arc capacity constraint (xCE ::: 80), the spanning tree is a feasible spanning tree, so we have a BF solution.

We shall use this solution as the initial BF solution for demonstrating the network simplex method. Figure 10.17 shows its network representation, namely, the feasible span- ning tree and its solution. Thus, the numbers given next to the arcs now represent flows (values of xij) rather than the unit costs cij previously given. (To help you distinguish, we shall always put parentheses around flows but not around costs.)

Selecting the Entering Basic Variable

To begin an iteration of the network simplex method, recall that the standard simplex method criterion for selecting the entering basic variable is to choose the nonbasic vari- able which, when increased from zero, will improve Z at the fastest rate. Now let us see how this is done without having a simplex tableau.

To illustrate, consider the nonbasic variable xAC in our initial BF solution, i.e., the nonbasic arc A --- C. Increasing xAC from zero to some value 8 means that the arc A --- C with flow 8 must be added to the network shown in Fig. 10.17. Adding a nonba- sic arc to a spanning tree always creates a unique undirected cycle, where the cycle in this case is seen in Fig. 10.18 to be AC–CE–DE–AD. Figure 10.18 also shows the effect of adding the flow 8 to arc A --- C on the other flows in the network. Specifically, the flow is thereby increased by 8 for other arcs that have the same direction as A --- C in the cy- cle (arc C --- E ), whereas the net flow is decreased by 8 for other arcs whose direction is opposite to A --- C in the cycle (arcs D --- E and A --- D). In the latter case, the new flow is, in effect, canceling a flow of 8 in the opposite direction. Arcs not in the cycle (arc B --- C ) are unaffected by the new flow. (Check these conclusions by noting the ef- fect of the change in xAC on the values of the other variables in the solution just derived for the initial feasible spanning tree.)

Now what is the incremental effect on Z (total flow cost) from adding the flow 8 to arc A --- C? Figure 10.19 shows most of the answer by giving the unit cost times the change in the flow for each arc of Fig. 10.18. Therefore, the overall increment in Z is

Because the objective is to minimize Z, this large rate of decrease in Z by increasing xAC is very desirable, so xAC becomes a prime candidate to be the entering basic variable.

We now need to perform the same analysis for the other nonbasic variables before we make the final selection of the entering basic variable. The only other nonbasic variables are yAB and xED, corresponding to the two other nonbasic arcs B --- A and E --- D in Fig. 10.16.

Figure 10.20 shows the incremental effect on costs of adding arc B --- A with flow 8

to the initial feasible spanning tree given in Fig. 10.17. Adding this arc creates the undi- rected cycle BA–AD–DE–CE–BC, so the flow increases by 8 for arcs A --- D and D --- E

Since the objective is to minimize Z, the fact that Z increases rather than decreases when yAB (flow through the reverse arc B --- A) is increased from zero rules out this variable as

a candidate to be the entering basic variable. (Remember that increasing yAB from zero re- ally means decreasing xAB, flow through the real arc A --- B, from its upper bound of 10.) A similar result is obtained for the last nonbasic arc E --- D. Adding this arc with flow

8 to the initial feasible spanning tree creates the undirected cycle ED–DE shown in Fig. 10.21, so the flow also increases by 8 for arc D --- E, but no other arcs are affected. Therefore,

so the negative value for xAC implies that xAC becomes the entering basic variable for the first iteration. If there had been more than one nonbasic variable with a negative value of LlZ, then the one having the largest absolute value would have been chosen. (If there had been no nonbasic variables with a negative value of LlZ, the current BF solution would have been optimal.)

Rather than identifying undirected cycles, etc., the network simplex method actually ob- tains these LlZ values by an algebraic procedure that is considerably more efficient (especially for large networks). The procedure is analogous to that used by the transportation simplex method (see Sec. 9.2) to solve for ui and vj in order to obtain the value of cij - ui - vj for each nonbasic variable xij. We shall not describe this procedure further, so you should just use the undirected cycles method when you are doing problems at the end of the chapter.

Finding the Leaving Basic Variable and the Next BF Solution

After selection of the entering basic variable, only one more quick step is needed to si- multaneously determine the leaving basic variable and solve for the next BF solution. For the first iteration of the example, the key is Fig. 10.18. Since xAC is the entering basic variable, the flow 8 through arc A --- C is to be increased from zero as far as possible un- til one of the basic variables reaches either its lower bound (0) or its upper bound (uij). For those arcs whose flow increases with 8 in Fig. 10.18 (arcs A --- C and C --- E ), only the upper bounds (uAC = oo and uCE = 80) need to be considered:

If the leaving basic variable had reached its upper bound, then the adjustments dis- cussed for the upper bound technique would have been needed at this point (as you will see illustrated during the next two iterations). However, because it was the lower bound of 0 that was reached, nothing more needs to be done.

Completing the Example. For the two remaining iterations needed to reach the optimal solution, the primary focus will be on some features of the upper bound technique they illustrate. The pattern for finding the entering basic variable, the leaving basic variable, and the next BF solution will be very similar to that described for the first iteration, so we only summarize these steps briefly.

Iteration 2: Starting with the feasible spanning tree shown in Fig. 10.22 and refer- ring to Fig. 10.16 for the unit costs cij, we arrive at the calculations for selecting the entering basic variable in Table 10.4. The second column identifies the unique undirected cycle that is created by adding the nonbasic arc in the first column to this span- ning tree, and the third column shows the incremental effect on costs because of the changes in flows on this cycle caused by adding a flow of 8 = 1 to the nonbasic arc. Arc E --- D has the largest (in absolute terms) negative value of LlZ, so xED is the en- tering basic variable.

We now make the flow 8 through arc E --- D as large as possible, while satisfying the following flow bounds:

The smallest upper bound (10) on 8 is imposed by yAB, so this variable becomes the leaving basic variable. Setting 8 = 10 in these expressions for xAC and xBC (along with the unchanged values of xAC = 10 and xED = 20) then yields the next BF solution, as shown in Fig. 10.25.

As with iteration 2, the leaving basic variable (yAB) was obtained here by the vari- able reaching its upper bound. In addition, there are two other points of special interest concerning this particular choice. One is that the entering basic variable yAB also became the leaving basic variable on the same iteration! This event occurs occasionally with the upper bound technique whenever increasing the entering basic variable from zero causes its upper bound to be reached first before any of the other basic variables reach a bound.

The other interesting point is that the arc B --- A that now needs to be replaced by a re- verse arc A --- B (because of the leaving basic variable reaching an upper bound) already is a reverse arc! This is no problem, because the reverse arc for a reverse arc is simply the orig- inal real arc. Therefore, the arc B --- A (with cBA = -2 and uBA = 10) in Fig. 10.24 now is replaced by arc A --- B (with cAB = 2 and uAB = 10), which is the arc between nodes A and B in the original network shown in Fig. 10.12, and a generated net flow of 10 is shifted from node B (bB = 50 --- 40) to node A (bA = 40 --- 50). Simultaneously, the variable yAB = 10 is replaced by 10 - xAB, with xAB = 0 as the new nonbasic variable. The resulting adjusted network is shown in Fig. 10.26.

Passing the Optimality Test: At this point, the algorithm would attempt to use Figs. 10.25 and 10.26 to find the next entering basic variable with the usual calcula- tions shown in Table 10.6. However, none of the nonbasic arcs gives a negative value