Maximal/minimal flow in networks with lower bounds. The maximal flow algorithm given in this section assumes that all the arcs have zero lower bounds. In some models, the lower bounds may be strictly positive, and we may be interested in finding the maximal or minimal flow in the network (see case 6-3 in Appendix E). The presence of the lower bound poses difficulty because the network may not have a feasible flow at all. The objective of this exercise is to show that any maximal and minimal flow model with positive lower bounds can be solved using two steps.

Step 1. Find an initial feasible solution for the network with positive lower bounds.

Step 2. Using the feasible solution in step 1, find the maximal or minimal flow in the original network.

(a) Show that an arc (i, j) with flow limited by lij … xij … uij can be represented equivalently by a sink with demand lij at node i and a source with supply lij at node j with flow limited by 0 … xij … uij - lij.

(b) Show that finding a feasible solution for the original network is equivalent to finding the maximal flow xij

= in the network after (1) modifying the bounds on xij to 0 … xij

= … uij - lij, (2) “lumping” all the resulting sources into one supersource with outgoing arc capacities lij, (3) “lumping” all the resulting sinks into one supersink with incoming arc capacities lij, and (4) connecting the terminal node t to the source node s in the original network by a return infinite-capacity arc. A feasible solution exists if the maximal flow in the new network equals the sum of the lower bounds in the original network. Apply the procedure to the following network and find a feasible flow solution:

Arc (i, j) (lij, uij)

(1, 2) (5, 20)

(1, 3) (0, 15)

(2, 3) (4, 10)

(2, 4) (3, 15)

(3, 4) (0, 20)

(c) Use the feasible solution for the network in

(b) together with the maximal flow algorithm to determine the minimal flow in the original network. (Hint: First, compute the residue network given the initial feasible solution. Next, determine the maximum flow from the end node to the start node. This is equivalent to finding the maximum flow that should be canceled from the start node to the end node. Now, combining the feasible and maximal flow solutions yields the minimal flow in the original network.)

(d) Use the feasible solution for the network in

(b) together with the maximal flow model to determine the maximal flow in the original network. (Hint: As in part (c), start with the residue network. Next, apply the breakthrough algorithm to the resulting residue network exactly as in the regular maximal flow model.)