Zeitschrift far OperationsResearch, Volume25, 1981, page 133-142. 9 Physica-Verlag. leiirzburg

Multiterminal Network Flows and Applications By R. Vahrenkamp, Karlsruhe t )

Received April 1980 Revised January 1981

Abstract: The paper discusses the ways to use the condensation technique of Gomory/Hu in the case of non-symmetric networks. Sufficient conditions to get the value of a maximal flow as row resp. column sum of the capacity matrix are derived. Procedures to determine the cut with minimal capacity are developed and applications of the minimal cut technique to problems of optimal sequencing are given.

Zusammenfassung: Das Papier diskutiert die M6glichkeiten, die Kondensationstechnik yon Gomory/Hu auf den Fall unsymmetrischer Netzwerke zu iibertragen. Es werden hinreichende Bedingungen daftir abgeleitet, dag der Wert eines maximalen Flusses mit der Zeilen- bzw. Spaltensumme der Kapazitgtsmatrix iibereinstimmt. Es werden Verfahren entwickelt, den Schnitt minimaler Kapazit~it zu bestimmen. Anwendungen der minimalen Schnitt-Technik auf Probleme der optimalen Reihenfolge werden vorgestellt.

1. Introduction and Notation F o r a symmetric network, Gomory/IIu [ 1961 ] have constructed a flow equivalent tree representing all possible maximal flows between any pairs of nodes of the network. This procedure has the advantage that n - - 1 applications o f the Ford-Fulkerson algorithm in condensed networks determine all n(n -- 1) maximal flows. F o r this so-called multiterminal flow problem, Elmaghraby [ 1964] has made a sensitivity analysis. Hu [ 1969, p. 129] has noted that to transpose the multiterminal flow problem to the nonsymmetric case would be difficult. In 1977, Schnorr developed an approach to cover the non-symmetric case, Schnorr [ 1977, 1978]. He employs the features o f cuts with minimal capacity. Hu/Ruskey [1980] consider the problem to obtain a cut with minimal capacity in a symmetric network with weights on the nodes and certain weight restrictions. In this paper, it is shown in which cases one can use the condensation technique of G o m o r y / H u to solve multiterminal flow problems in non-symmetric networks. t) Priv. Doz. Dr. Richard Vahrenkainp, Fakult~it fiir Wirtschaftswissenschaften der Universit~it Karlsruhe, Kaiserstrage 12, D-7500 Karlsruhe.

134

R. Vahrenkamp

Procedures to determine the cut with minimal capacity are discussed as a second topic. In a third point, some sufficient conditions are derived to get the maximal flow between a pair of nodes directly as a sum of a column resp. row of the capacity matrix notusing the Ford-Fulkerson algorithm. The last topic discusses applications of the cut with minimal capacity to problems of optimal sequences of activities. For valuable discussions, I thank K. Boenchendorf, G. Hammer and H. Meyer from the Faculty of Economics of the University of Kaflsruhe. The algorithms were tested, by use of the input-output matrices of the Federal Republic of Germany of dimension 12 X 12 and 49 X 49 [see DIW 1972, 1979]. The computations were carried out by cand. wiing. A. Bracht and cand. wiing. R. Rohde. A network is given by the triple N = (II, VX V, A). The set V denotes the nodes 1, 2 . . . . . n. A is a non-negative (n X n) capacity matrix with aii = 0. Denoting by q the source and by s the sink, a non-negative (n X n) matrix Fqs = (fi])i] is called flow from node q to node s if the usual conservation conditions are satisfied [see Neumann, p. 106 and Christofides, p. 283s.]. The value of a maximal flow from q to s is denoted by F *qs. Let F * be the matrix ( F qs * ) qs of the values of the maximal flows with F.*. tt = 0 9 A proper subset X of V is called cut. If the cut X separates the two nodes i and], i.e. i E X and j E X c, then X is called a (i, /')-cut. The capacity of a cut X is denoted by c(X). A cut X with minimal capacity under all (i, ])-cuts is denoted by Mi].cut.

2. Condensation in Non-Symmetric Networks One important feature of the flow equivalent tree of Gomory/Hu [1961] is the condensation of the network used in the construction of the tree. The condensation reduces the nodes, lying in one part of a cut, to a single node and, therefore, diminishes the dimension of the network in which the maximal flow is determined. So the complexity of the max-flow problem is reduced. The condensation technique refers to a given cut X. To determine a maximal flow F0. , the node set X resp. X c can be reduced to a single node if there is aM/j-cut Y s.t. yC C X or y c C X c resp. Y C X o r Y C X c. Definition A cut X admits the condensation of a cut Y if YC X or YC_ X c. Hu has shown for the case of symmetric networks that for a given cut X all flow values Fi~ can be determined in a network given by the condensation o f X resp. X c [Hu, Lemma 9.1, 9.2, 9.3]. To consider the case of non-symmetric networks, we start with a network N of this kind and an M s-cut X in N, and we look for conditions s.t. an M/f cut Y admits a condensation of t~e cut X resp. X c. In the non-symmetric case, one can distinguish four situations: 1) i, j E X, 2) i, ] E X c , 3) i E X, / ~ X c, 4) i E X c,

i~x. A check of these four cases shows that, only in case 3), one can formulate general conditions for condensation.

Multiterminal Network Flows and Applications

135

Theorem 1 Let X be anMqs-CUt. a) For every ] E X c, there is an Mqi-CUt Y admitting a condensation of X. b) For every i E X, there is an M.s-cut Y admitting a condensation of X c.

Proof: The proof is given for a). The proposition b) can be proved by the same technique. L e t X be an M~/s-CUt andZ an Mq/-cut for a fixed/. C X c. It will be shown that there is the desired cut Y. The cuts X and Z are decomposed in disjoint parts: P = X c r-IZ, Q = X CqZ, R = X c N Z c,S = X N Z c. For arbitrary subsets H, G C V, we denote by CHG the sum E a... The cut Q

--

iEH zl

separates q and s andXis an Mqs-CUt. So we have c (Q) ~>c(X). This implies

cQS >I Csp + cSR.

(1)

The node/' lies in R. So the cut X U P separates q and/' and c(X U P) >1c(Z). This implies

csR > Cps + cg s.

(2)

Adding (1) and (2) and regarding the non-negativity of the terms shows Cps = 0 and cst, = 0. Substitution in (1) and (2) lets cQs = cSR follow. Now we can show that

e ( X U P ) -- CQR + cpR + eSR = CQR + cpR + eQS + Cps = c(Z). So the (q,/')-cut X U P has the minimal capacity of the Mqfcut Z and is, therefore, an Mqi-cut. Therefore, the cut X U P is an Mq]-CUt admitting the condensation of X. q.e.d. Another method to apply the condensation technique of Gomory/Hu to the nonsymmetric case is developed by Schnorr [ 1977, 1978]. He does not start the condensation procedure with an arbitrary Mqs-Cut X but with a cut X* with minimal capacity:

c(X*) = min c(X). Xc V This minimum condition supplies an additional inequality used for the justification of this approach.

Theorem 2 [Schnorr] Let X* be a cut with minimal capacity. For i, ] E X* (resp. i, ] ~ X ' c ) , there is an

R. Vahrenkamp

136

Mi]-cut admitting the condensation of X *c (resp. X*). With the condensation technique of theorem 2, Schnorr constructs an analogon of th~ flow equivalent tree of a non-symmetric network. This tree exhibits the values min(F.~, F.~ii] of the maximal flows. So not all values can be determined by the tree.

3. The Cut with Minimal Capacity In this section,procedures to determine the cut with minimal capacity are discussed. These cuts play a central role in the approach of Schnorr to the multiterminal flow problem. There are also certain applications of these cuts. Schnorr [ 1977, 1978] determines the connectivity of networks with the aid of minimal cuts. In the last section of this paper, applications are shown to the arrangement problems of matrices. One procedure to determine the cut with minimal capacity is based on the "triangle inequality" for maximal flows given by Gomory/Hu [1961]: For arbitrary nodes i, L k, one has F/~ ~> rain (F/~, F~]). The proof for this inequality given by Gomory/Hu for symmetric networks, completely carries over to the non-symmetric case. Denote by F * = rain F*

=

i~]

t]

the minimal value of the maximal flows in N corresponding by the min-cut-max-fl0w theorem to the cut with minimal capacity, put F* = F* in the triangle inequality and extend inductively the "path" Fi*k, F~c] to a cycle C in N including all nodes of N, one gets the formula F * = min {F/~ : (i, ]) E C}. To determine F * by this formula, one has to compute n times a maximal flow along the cycle. Another procedure to get _F* computes all maximal flow values of a column and of a row of the matrix F*. This approach requires 2n-3 max-flow computations. The increased number of max-flow computations compared with the procedure above can partly be compensated by the advantage that certain max-flow computations can be carried out in condensed networks. For an Mqs-CUt X and i @ X, ] E X c the cut X is an (i, ])-cut. So we have with the rain-cut-max-flow theorem: 7//*'~
for all i ~ X and ] ~ X c.

Multiterminal Network Flows and Applications

13 7

If we choose X as the cut with minimal Capacity, we have by the minimum property of f*: F* = F* =c(X) t]

=

f o r a l l i E X a n d j E X e.

In the matrix F*, the minimum value F * is, therefore, not unique but appears at least (n - 1) times depending on the cardinality of the set X. From the formula above, one can infer that for every given node r E V the value F * appears in the r-th row or r-th column of the matrix F*. So one puts

F r = { F*, r : i E V , i # r } U {Fr*] : j ~ V , ] r r} and has F* = min F r

for all r ~ V.

For the computation of the set Fr, one can utilize the condensation technique described in theorem 1. Both described procedures to get F * exhibit the common feature that F * is derived as the minimum over a certain set of maximal flow values. But in many cases it is not necessary to compute these sets completely for one can foresee that certain maximal flows have greater values than F * so that the computation of these values is not required. Now we derive a simple sufficient condition for F.~ > =F*. For i ~ V, letX, = {i}, Ci resp. R i the sum of the i-th column ofA resp. row. For given nodes i, ], the cuts X i and X~] are (i, ])-cuts with capacity R, resp. CS. With the rain-cut-maxflow theorem, we have the inequality

F,~ <~min [c(Xi), c(X]C)] = min(Ri, C]). Taking the minimum, one gets F * ~ rain [min(R/, Ci) ] =: a i~ V as an upper bound for F*. On the other hand, every max-flow value F/~ has the trivial lower bound

So we can conclude: If all > c~, then F/~ > F * and a computation of F/~ is not required to get _F*. This exclusion criterion, together with the approach F* = min F r using the condensation technique, seems to be an efficient way to compute 17,.

R. Vahrenkamp

138

Computations in four networks with 49 nodes each have exhibited that an average number of 30 max-flow computations are sufficient to get F * , whereas the number fluctuates between 14 and 50. An important feature of both procedures to determine the cut with minimal capacity can be seen in the reduction of computational complexity. To select this cut is a selection problem of 2n-2 alternatives. The procedures reduce this problem to a selection of a number of flows being of the order of n.

4. The Maximal Flow as Row Resp. Column Sum In the foregoing section, the relation of the maximal flow value F.*. tl to the row and column sums of the capacity matrix has been established by the formula F0*"~< min

(R i, Ci).

Now we raise the question under which sufficient conditions the equality F *tj = rain (R.,l C.) holds ' That this equality is not to be seen as an exotic case, has j been demonstrated by 117 computations of maximal flows in four networks with 49 nodes each. In the case of 95 out of these 117 computations, the maximal flow value was equal to rain (R i, C]). Once one has established sufficient conditions for equality, one can compute the maximal flow value directly from the capacity matrix without using the Ford-Fulkerson algorithm [Ford/Fulkerson]. In these cases, the M/i-cuts are simple: IfF/~ =Ri, then {i} is such a cut. IfFi~ = C], then (]}c is such a cut. To derive the condition, we put Ceil= min (Ri, C]) and assume aii= R i. The other case is analogous. A sufficient condition for F/~ = ceil is based on the capacity of paths of length not greater than 3 from i to j restricting the consideration to a rather uncomplicated situation. If the overall capacity of these paths is not less than ai], the equality F i / = etij holds. This is the intuitive concept, To make this concept precise, fix the two nodes q and s. A flow with the value Ctqs will be constructed to flow from q to s using paths of length ~< 3 only. By t~qs = Rq this flow has to use all capacity aqi, j E 11. Now consider all nodes k ~ q, s. In such a node a flOWfqK = aqK flows. Necessary and sufficient that this flow can flow from k to s is that the capacity of flowing out at node k is not less thanaqK:

R K --aKq >~aqK

forallk@q, s.

(c1)

First, we assume that from any node k --/=q, s the flOWfq K can be transferred on a path of length one to the sink s. Necessary and sufficient for this assumption is the condition

aKs>~aqK

forallK~q,s.

Roughly speaking, this means that column s dominates row q.

(c2)

Mulfiterminal Network Flows and Applications

139

Now we assume that the flOWfq K is transferred to the sink s on paths of length ~< 2. Under this assumption for every node k r q, s a flow F K from k to s with the value a .. will be constructed using paths of length ~< 2 only. The construction of qh F K is made inductively. The nodes k E V, k r q, s are enumerated: the flows

kl' k2 .... ' kn-2" The f l o w F : = (f/)) from kl to s with value aqK 1 is given by the following conditions:

O<~f)rls <~aK1~ O <~f~ ij <~min (ak l/, a/s)

f o r j ~ s , q, k~

fils=f~c,] for]=/:s,q,k, f~rp = 0

otherwise.

Necessary and sufficient for F 1 achieving the value aqK: is the condition

akls +j~V ~ min (aklj' ajs) >/a qK a . j~q

(C3)

In the l-th step of the inductive construction, 2 < I ~
I-I O <~flkls <~aklS _ t~=l ~tk lS l-1

O<~tk]<~min[aklk]'a~f--t~=l fk]s]' 1= 1..... n--2,]=/=l

=0 flrp

otherwise.

Necessary and sufficient for F l achieving the value aqk 1 is the condition: 1-1

aklS--t~=l fkl s

n-2 q- ]=1 ~

l-1

min [aklkj' ak]s --t~l fkt]s] ~aqkl"

(c4)

To derive a sufficient condition that (C4) is fulfilled, the left side of (C4) is diminished for l > 2: We have ~fK's = fK tKi by construction. So we have with ]fK's

<~min (aqK t' aK tK/)

R. Vahrenkamp

140

l-1 t I-1 E f~ s ~< E min (aqkt, aktk] ) =: b (q, ],/). t= 1 r/ t=l The left side of (C4) is not less than

n-2 akl s -- b (q, l,/) + ]=El rain" {aklk] , max [0, akl.s -- b (q, ],/)1} = =:d(q,S, kl),

l=2 .....

n--2.

So a sufficient condition that from every node k l the flow F 1 of value aqK l can flow to the sink s using paths of length ~< 2 is given by:

akl s + J~EV min (akl]' ai-s) >~aq k 1

(C5)

and

d (q, s, kl) >~aqk f

l = 2, 3 . . . . , n -- 2.

These considerations are summarized in the following theorem:

Theorem 3 Assume that for the nodes q and s the relation Rq <~C s holds. If one of the conditions (C2) or (C5) is fulfilled, then F~s = Rq.

5. Applications to Optimal Sequencing An activity matrix A representing the intensity of the connection of activity i with activity ] can be regarded on the macro economic level as an input-output matrix and on the micro economic level of the plant as the matrix of the material transport requirements in a network of various machines. In both cases, questions of optimal sequencing of the activities arise [see Korte/Oberhofer and Weil]. The first question discussed here concerns an optimal clustering of the activities into two groups s.t. the connections between these groups are minimal and the measure of independence of at least one group is as great as possible. In the graph theoretic approach, to solve this problem the activity matrix A plays the role of the capacity matrix of a network (putting aii = 0). In this network, the cut with minimal capacity solves this problem. Choose a cut X * minimizing the capacity E

iEX iEX c

a..: -~ min.

Then the activity group represented by the set X *c has the maximum of independ-

Multiterminal Network Flows and Applications

141

ence from the activities given by the set X*. Minimizing the coupling between the two groups means to solve the proNem

i~X ]~X c

(ai] + ~i) ~ rain,

i.e. the cut with minimal capacity in a network with capacity matrix A + A T This approach to identify cuts with minimal capacity is related to the concept of reducible matrices. Call a matrix M reducible if there is a cut with capacity zero. For a given activity matrix A with minimal cut X* letA * be defined by a~. = 0 for i E X * and] E X *c and a~ = ai/otherwise. ThenA* is reducible and the capacity of X* is the distance of A to the set of reducible matrices measured in the matrix norm I1.4 II = 2~ I aij [ : IIa -.4*

II =

c(X*).

So the value c(X*) is a measure of distance of A to the ideal form of reducibility. The approach to identify cuts with minimal capacity can be developed further to a fast heuristic to solve a problem of quadratic assignment of activities - also known as the triangulation problem of matrices. We say that an activity matrix A is in a triangulated state if there is an enumeration of the activities s.t. the activities increase with the order of the enumeration, and the flows in forward direction are maximal resp. in backward direction are minimal [Korte/Oberhofer]. Formally stated, this is the following assignment problem: Find a permutation zro minimizing tile function 7r ~ i>/~" a~(i),~q)' the last sum is the "sum under the main diagonal". This kind of optimization problem also appears in location theory in the case of constant costs per unit [Francis/White, p. 332]. The only known exact algorithm designed to solve this problem has been published by Korte/Oberhofer [1968]. It is a branch and bound procedure and, therefore, not fast. The more general quadratic assignment problem is known to be NP-complete [see Garey/Johnson, p. 218]. Therefore it seems reasonable to develop a fast heuristic which is sketched in the following. Identify the cut I* with minimal capacity in the network given by A. The cut I* represents a rectangle I* • I *c of indices with the property that the sum of matrix entries over this rectangle is minimal with respect to any other rectangle. Now choose a permutation rr putting this rectangle under the main diagonal, i.e. mapping/* on the last indices. Then the sum under the main diagonal contains this minimal sum over the rectangle, and a first step of the approximation of the minimal sum under the main diagonal by a "minimal rectangle!' has been carried out. In the following step, the same procedure is applied to the following quadratic submatrices ofA: A a = (aij)i,/Ei,, A 2 = (ai/)i/~I,C. The algorithm stops when every submatrix has dimension one. A full description of this algorithm, its performance and theoretical justification and computational experience is given by Vahrenkamp [ 1981] showing that the algorithm generates the exact solution if the matrix A is an arbitrary permutation of a matrix B with

142

R. Vahrenkamp

the property b.. ~< b.. for i >/'. The 12 • 12 DIW input-output tables have been triangulated by t~(is he/uristic. The exact order of the activities have been obtained by the lexicographic search algorithm ofKorte/Oberhofer [ 1968]. The heuristic has required a computation time of 4 to 6 seconds for each triangulation on a main frame computer and achieved the minimal value within an error of 4 % to 12 %.

References

Christofides, N.: Graph Theory. New York 1975. DIW 1972, 1979: Deutsches Institut ftir Wirtschafsforschung (Ed.): Beitriige zur Strukturforschung, No. 21, Berlin 1972, and No. 54, Berlin 1979. Elmaghraby, S. : Sensitivity Analysis of Multiterminal Flow Networks. Operations Research 12, 1964, 680-688. Ford, L., and D. Fulkerson: Flows in Networks, Princeton 1962. Francis, R., and J, White: Facility layout and location. Englewood Cliffs 1974. Garey, M., and D. Johnson: Computers and Intractability. San Francisco 1979. Gomory, R., and T. Hu: Multiterminal Network Flows. SIAM Journal 9, 1961, 551-570. Hu, T. : Integer Programming and Network Flows. Reading 1969. Hu, T., and F. Ruskey: Circular Cuts in a Network. Mathematics of Operations Research 5, 1980, 422-434. Korte, B., and W. Oberhofer: Zwei Algorithmen zur L~Ssungeines komplexen Reihenfolgeproblems. Zeitschrift fiir Unternehmensforschung 11, 1968, 217-231. Neumann, K. : Operations Research Verfahren, Vol. III. Miinchen 1975. Schnorr, C. : Multiterminal Network Flows and Connectivity in Unsymmetrical Networks. Optimization and Operations Reseach. Ed. by R. Henn, B. Korte and W. Oettli. (Lecture Notes in Economics and Mathematical Systems, Vol. 157) Berlin 1977, 241-254, and in G. Goos, and H. Hartmanis (Eds.): Automata, Languagesand Programming. (Lecture Notes in Computer Science No. 62) Berlin 1978, 425-437. Vahrenkamp, R. : Triangulation and Decomposition of Input-Output Matrices by Network Methods. Proceedings of the V-th Symposium on Operations Research in Cologne, August 25-27, 1980. Methods of Operations Research 40, 1981, 437-440. Well, R. : The Decomposition of Economic Production Systems. Econometrica 36, 1968, 260-278.