A Successive Shortest Path Algorithm For The Semi-Assignment Problem by S.O. Duffuaa Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 and M.S. AL-Ghassab Saudi Petrochem Co. Jubail, Saudi Arabia Technical Report # 94-15 April 1994

A Successive Shortest Path Algorithm For The Semi-Assignment Problem by S.O. Duffuaa* Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 E-mail: SALIH.ENGIN.UMICH.EDU and M.S. AL-Ghassab Saudi Petrochem Co. Jubail, Saudi Arabia In this paper a successive shortest path algorithm has been developed for the semi-assignment problem. The algorithm can be viewed as a dual method. It maintains dual feasibility and complementary slackness and achieves primal feasibility by solving a sequence of auxiliary shortest path problems. The algorithm has a worst case bound 0(n3), where n is the number of destinations in the semi-assignment problem. Through empirical testing on standard semi-assignment problem it has been shown that the implementation of the proposed algorithm dominates a specialized primal simplex code and an Out-of-Kilter implementation. Subject classification: Networks/graph; Shortest path problem; algorithm for semiassignment problem. * On Sabbatical leave from King Fahd University of Petroleum and Minerals, Dhahran, 31261, Saudi Arabia 1

The semi-assignment problem deals with assigning optimally m tasks to n agents such that each task is assigned to exactly one agent. It is a bipartite network whose demand constraints are the same as those of the classical assignment problem and whose supply constraints are the same as those of the transportation problem. Semi-assignment problems arise in numerous applications of scheduling, project planning and man power planning and assignment [4]. In new car design at General Motors (GM) semi-assignment formulations are used to assign microprocessors to tasks or functions. Here the number of microprocessors are much less than the tasks in the car. The mathematical programming formulation of the semi-assignment problem is as follows: Minimize X cijxi (1) (c,)EE Subject to xii = bi,i E I = (1,2,3,...,m) (2) (i,j)EFS(i) S xii=l, jEJ=(1,2,3,..., n) (3) (i,j)RS(j) xij 0 for alli,j (4) where E denotes the set of arcs in the network, FS(i) is the forward star of node i, RS(/) is the backward star for nodej, Cij is the cost of assigning processor i to taskj, bi denotes the number of tasks a processor can handle, and xij = 1, implies processor i is assigned to taskj. It is clear the model is feasible if and only if X bi = n. i The semi-assignment problem can be viewed as a minimum cost flow problem and therefore algorithms for solving pure networks such as specializations of primal simplex, dual simplex, Out-of-Kilter and shortest augmenting path (successive shortest path methods) can be employed for solving it. Specialization of the simplex method and the use of efficient data structures has resulted in codes for the minimum cost flow network which are 100 times faster than solving network problems with general purpose linear programming codes. For software implementations for the minimum 2

cost flow problem see [2,10]. For a complete development of the network simplex and its computational complexity see Ford and Fulkerson [9], Cunningham [5], Kennington and Helgason [14], Papadimitriou and Steiglitz [16], Tarjan [18], Rockefellar [17] and Ahuja, Magnanti and Orlin [1]. A major problem the simplex method specialization for the assignment problem has, is the phenomenon of degenerate pivots. This lead Barr, Glover and Klingman [3] to develop the alternating basis algorithm (AB) for the assignment problem. Later Barr, Glover and Klingman [4] generalized the AB algorithm to the semi-assignment problem which is the first specialized algorithm designed for the semi-assignment problem. The AB algorithm is also discovered in [5]. The shortest augmenting path algorithms or otherwise known as successive shortest path algorithms (SSP) are basically dual methods. Specialization of SSP methods to the assignment problem are done by Tomizawa [19], Hung and Rom [12], Enquist [8], and Jonker and Volgenant [13]. Extensive theoretical studies of shortest path algorithms for solving minimum cost flow problems are in Papadimitriou and Steiglitz [16], Edmonds and Karp [7], Hu [11], and Ahuja, Magnanti and Orlin [1]. Recently Kennington and Wang [15] developed a shortest augmenting path algorithm for the semi-assignment problem which was inspired by work of Jonker and Volgenant [13]. Their algorithm is a generalization of the algorithm in [13] for the assignment problem and their computational results indicate that their algorithm is the best known. In this paper we develop an algorithm for the semi-assignment problem based on successive shortest path approach. Our algorithm generalizes the SSP algorithm developed by Enquist for the classical assignment problem. Empirical testing and comparisons with CAPNET (a specialized simplex codes developed by Barr, Glover and Klingman [3] and TRANS (a network code in the Statistical Analysis Software (SAS) package) have shown that the developed SSP algorithm is uniformly 3

better on all sizes of tested problem. The test problems are generated using NETGEN and are used previously in [4]. The rest of the paper is organized as follows: Section 2 describes the SSP algorithm for the semi-assignment and Section 3 presents the steps of the algorithm and its theoretical properties. Section 4 discusses implementation issues for the algorithm and Section 5 presents the comparative computational testing with other algorithms. Section 6 concludes the paper. 2. Description Of The SSP Algorithm For The Semi-Assignment Problem Given a semi-assignment problem as defined in equations (1-4), we say X = (xij) is a tentative solution provided 3 at least one j e J such that: xij =bi, iEl. (i,j)eFS(i) Since the semi-assignment network will remain fixed in the following discussion, we denote the semi-assignment problem equipped with a tentative solution X by (m,n,C,b,X). We say that (m,n,C,b,X) is in the standard form if cij > 0 for (ij) eE and cij = Oifxij >0. In the starting procedure for SSP a tentative solution is defined as follows. First, ci min {cip (5) (i,p)EFS(i) must be determined for ieI. xij = bi for some j such that cij =. For this X, (m,n,C,bX) may not be in the standard form. However, the forward start of i may be scaled by setting C, - - Cp - ci, for (i,p) e FS(i). (6) The resulting (m,n,C,b,X) is in the standard form. 4

For a given tentative solution X, we let aj= - xij (7) (ij)ERS(j) The modified semi-assignment problem relative to (m,n,C,bX) is defined as follows: Minimize S Cijxij (8) (i,j)eE Subject to xi =bi, i E I (9) (i,j)eFS(i) X xij=aj, jeI (10) (i,j)eRS(i) xij > 0, (i,j)EE (11) We note that when (m,n,C,b,X) is in standard form, X provides an optimal solution to the modified semi-assignment problem in (8) relative to (m,n,C,bX). A destination node j is said to be abundant relative to X when aj > 1. Likewise, j is said to be deficient relative to X when aj = 0, and if a= 1, node j is said to be neutral. The goal is to transform all abundant and deficient nodes to neutral nodes. This will be accomplished via a successive shortest path methodology. Suppose (m,n,C,bX) is in the standard form and d some deficient node with respect to X. Then the shortest path problem relative to (m,n,C,bX) and d is denoted SP(m,n,bX,d) and is defined as follows: The nodes of SP(m,n,bX,d) are arcs (ij) of the semi-assignment problem with, Xij > 0. Such shortest path node is denoted by (i -> Xij) or (i-> j ). Introduce one more node (m +1 -> d) for the shortest path network and make it consistent with previous notation by extending X so that xm+l, d = 1. For SP(m,n,b,X,d) the root node is (m + 1- d), while a node (i- Xij) is abundant provided node j is abundant relative to X. An arc exist in the shortest path network from (i - Xi,j) to (p -> Xpk) in case (p,j) e E and its length cpj, where j = notations: 5

Ri = node potential for the i-th origin node, Kj = node potential for the j-th destination node, Di = distance of the i-th shortest path node from the root, Pi = predecessor of the i-th shortest path node in the shortest path tree. The use of R is to denote the mapping whose value at i is Ri. The use of K, D and P is similar. When a shortest path problem is solved, denote the first abundant node to be permanently labelled by v, and denote the distance from the root by L, and S(v) the set of nodes on the path from the root node to v. Let C = c~ij: (i,j) e-' denote the costs of the origin (original) semi-assignment problem. Then the steps of the SSP are given below. 3. The Steps of the SSP Algorithm and It's Theoretical Properties In this section the steps of the SSP algorithm are stated and clarified by an example. Then the theoretical properties of the algorithm are given. 0. Define X1 and transform CO to C1 by scaling as described in equation (6) above, so that (C1, X1 ) is in the standard form. Set k = 1. 1. Choose a deficient destination node dk relative to Xk. If no deficient node exist, stop Xk defines an optimal solution. 2. Solve SP(m,n,Ck,b,dk). The shortest path algorithm is terminated as soon as an abundarit node is permanently labelled. If the SSP fails to permanently label an abundant node, stop, the semi-assignment problem is infeasible. Otherwise, the results of this step are Dk, pk, vk and Lk. 3. For each permanently labelled shortest path node (i -> j) from step 2, set R, = D,* - L and K/ = L - D/. For any remaining origins i or destinations j, set R, =K=O. 6

4. Set c+ = c1 - R - K, for (i,j)E E. 5. Whenever the i-th shortest path node is in S(vk), i ~ m+l, set Xk1 = X, Q, where O is the destination assignment number for node i, Q is the destination assignment number of node 1, and I = P. For the abundant k+l k k node Xi,r+l = X, Q, if Xi0 receives more than one unit from node i (i.e., /,o40i~~o i~~o-k+ Setxkik xixk > 1). For all other origins, i, not in in S(vk), XO1 = XiQO. Set k- k + 1 and go to step 1 of the SSP. In the case of the semi-assignment problem in an intermediate stage we may have a source supplying several destinations. Let the number of destinations be ri, e.g. (i- Xi,), (i -- Xi,2),...,(i- Xir ). This implies in the shortest path problem SP(m,n,b,Xk,dk) two nodes may have the same origin i, for example (i -> Xi,) and (i- Xi2). Therefore in solving the SP(m,n,Ck,b,Xk,dk) a tie may occur when scanning the predecessor of these two nodes. The tie is broken arbitrarily. This does not occur in the case of the assignment problem, since each source supplies only one destination. In order to fix ideas, we present one iteration of the SSP algorithm on the example showing how SP(m,n,C,X,d) is defined in a particular case. Let the semiassignment problem be as shown in Figure 1, where arc (ij) is labelled with cost cij. 7

SUPPLY EA 12 \713 1 13___________^^^^ — ^ (5)4 __ 1 _ Figure I An Example of a Semi-assignment Problem. Step 0 Put the problem into standard form: c =8, c2=12, 3 =4 C1 =c1- c =10-8=2, c21 =c2 2 =15-12=3 1 0 21 C c12 = c12 -c1 = 12-8 =4, c2 =c22 -C= 18-12 = 6 c13 =C13 -1 =13- 8 =5, c2 c - C2 =17-12 = 5 C14 =C14 -1 8-8=0, 24 =c24 2 =12-12=0 cl5 = c5 -c = 14-8=6 c 25-C =16-12=4 Cl=c3- C 3 =13-4=9, C32 =C2-C3 =19-4=5 c33 =cC 3 - 4-4 0, 34=C34 - 3=14-4=10 C35 =C35-C3 =16-4=12 8

Therefore, X1 = (Xll,Xl,Xl )= (4,4,3) and al=0, al=O, a1=2, a1 =3, as=0 k=l. Iteration 1. Step 1: Choose a deficient node d1 = 1 Step 2: Solve SP(m,n,C1,bX1,d1). m = 3, n = 5. The network for SP(m,n,Cl,b,X 1,dl) is shown in Figure 2 where a shortest path node (i -> Xio) is shown as a node with an upper label (i) and a lower label (Xi,0). The arcs of the shortest path network are labelled with their lengths. The results of this step are: D-=2, P1 4, v =( and L =2 ~ ~ 4 F4 - Figure 2 An Example of SP(CX,d) 9

Step 3 R~ = Dl-L= 2-2=0, K =L1-D1 =2-2=0 R2 = 31 = = A3 = = =0 Step 4 ci2 = l - R - K -=2- O - 0=2, 23 =c3 - R - = 5 - 0 - = 5 c12 = c -R - K =4-0-0=4, c24 =c -R - K =0-0-0=0 12 12 -R1 214= 0 = C15 = c15 - R1 -K = 6-0-0= 6 2= -1 -1 30= 2 1 1 =5-0-0=5 c21=c21-R21-KI =3-0-0=3, c23=C23-R21-K3=5-0-0= c22 = 2 -R-K-16-0-06, c2 1 4 — =0-0-0- 0 -1 =4-0-0=4 325 = c25 - R2-K =12-0-0=12 2 = (X2 22,1, ) (4,1,4,3) a2 =, a=0, a-2 = 2, a4 = 2, =0 let k = 2, go to step 1 Next, the theoretical Properties of the SSP Algorithm are given. 10

Theorem 1. If SSP does not stop because of the infeasibility test in step 2, it reaches optimality in at most n - 1 iterations. Proof: We proceed by induction. We have (m,n,C1,b,X1 ) is in standard form with at most n - 1, deficient destinations. If we assume that (m,n,Ck,bXk) is in standard form with q > 1, deficient destinations, it follows that (m,n,Ck+l,b,Xk+l) is in standard form with q - 1 deficient destinations. At each iteration the number of deficient nodes is reduced by one. Therefore the theorem follows. Theorem 2. SSP algorithm has a O(n3) computational bound. Proof: When the algorithm does not indicate an infeasible semi-assignment problem, it requires at most n - 1 iterations by Theorem 1. This result, together with the O(n2) computational bound, where n is the number of nodes in the shortest path tree, for the Dijkstra shortest path algorithm, implies the O(n3) bound in this case. Theorem 3. The original semi-assignment problem is infeasible if and only if the shortest path algorithmfails to label an abundant node of SP(m,n,Ck,b,dk) on some iteration k. Proof: Half the proof follows from Theorem 1. We proceed with the remaining half. Suppose that the algorithm fails to label an abundant node. Let N1 be the set of origins i such that (i - q) is permanently labelled for some q, and let N2 be the set of destinations j such that (p -> j) is permanently labelled for some p. All arcs of the original semi-assignment network which terminate in N2 must originate in N1 by the way SP(m,n,Ck,b,dk) is defined. Since N2 contains one more element than N1 (namely, dk) it is clear that the original semi-assignment problem is infeasible. 11

4. Implementation of the SSP Algorithm for the Semi-Assignment Problem A Fortran code has been developed for the semi-assignment problem implementing the SSP algorithm developed in this paper and is called SPSN. Some of the details of the implementations are discussed below. let, R~' min {cij, i I, K O,j J (i,j)EFS(i) m-1 m-1 Rm = Rik, i E I, Kj= m Kje J k=O k=O R. m and K im are the accumulated node potential for the modified semi-assignment problem relative to xm. There is a difference between the statement of the algorithm in section 3 and its implementation. In Step 3 of the algorithm node potentials are defined for all nodes of the semi-assignment network at each iteration, while in the code, the accumulated potentials are maintained. Thus at iteration k, only the node potentials corresponding to permanently labelled shortest path nodes need to be updated. In Step 4 the cost data for all arcs is updated, however, this is not the case in the code. Instead, whenever a cost Cqk is needed in the solution of SP(m,n,bXk,d), it is computed using the relation c/ =c/- R/- -KJ. Next we describe how the details of the SSP algorithm is handled in the code. In Step 1 of the SSP, there may be more than one deficient node to choose from. In this implementation the node with the smallest j such that j is deficient is chosen. Then the following technique is used for creating and solving the shortest path problem. The shortest path problem is solved using Dijkstra algorithm. The implementation and data structures for Dijkstra is obtained from [6]. The efficiency of 12

Dijkstra algorithm depends on the maximum arc length in the problem which is the dimension of the array used for address calculation sort. Making a complete path through the arc data to determine the maximum shortest path arc length at each iteration of the SSP would be very inefficient. In the code we simply maintain an upper bound on the maximum shortest path arc length and use this in determining the length of the sort list or the size of the radix. If we let: c= max {ci} (i,j)EE and K = min{K } jej J Then the upper bound on arc length for SP(m,n,b,Xk,dk) is c-k. This upper bound is easily updated along with node potentials K-k. The assignment of each source node i to a destination node j is stored in an array called X (initially X:=0 of length m. Each time a destination node j is satisfied from a source node i, it is linked to the list in position i of the array X. When reversing the assignments in Step 5, a destination node in S(vk) may change its source node. If the abundant node in the modified semi-assignment problem receiving only one unit from a source node i in S(vk), then the position of this abundant node is occupied by the destination node of the predecessor of node i in S(vk). If the abundant node j in the modified semi-assignment problem receiving more than one unit from a source node i in S(vk), the destination of the predecessor of node i in S(vk) is supplied from node i and the abundant destination nodej is supplied also from node i. For the rest of the path S(vk) continue by successively examining the predecessors of v until the root node is encountered. 13

5. Comparative Computation Tests In this section the design and the result of the computational testing will be reported. 5.1 Design of Experiment The developed code is in core and the program is written in Fortran IV and compiled using the same compiler and the same computer (AMDHAL 5850). The computer jobs were executed during periods when the machine load was approximately the same, and all solution times are exclusive of input and output. The total time spent solving the problem was recorded by calling a real time clock upon starting to solve the problem and again when the solution was obtained. Each test problem is solved five times and the average is reported. The problems used in the tests were randomly generated using NETGEN. In contrast to the assignment test problems, the specification of the semi-assignment test problems vary greatly in both the number of nodes and arcs. The test problems vary in size from 50 origins and 500 destinations to 400 origins and 4000 destinations. The number of arcs varies from 2000 arcs to 16,000 arcs. The cost data were randomly generated between 1 - 1000 for the first set of test problems. In the second set of test problems the cost data were randomly generated between 1 - 10,000. 5.2 Computational Results The developed code SPSN is tested and compared with two other codes. The two other codes are CAPNET a specialized primal simplex code developed by Barr, Glover and Klingman at the University of Texas at Austin and the second code is TRANS an implementation of the Out-of-Kilter algorithm part of the Statistical Analysis Software (SAS). 14

In order to compare the three codes a set of semi-assignment problem generated by NETGEN and also used in the study by Barr et al. [4] were solved. The results of comparisons are shown in Tables 1 and 2. Table 1 shows problem size, density (in terms of number of arcs) and solution times (CPU times) for the set of problems with cost vector between 1 and 100. Table 2 presents the same items for the set of problems with cost vector in the range 1 - 10,000. Upon examining Tables 1 and 2 it is evident that SPSN dominates the other two codes and is the fastest code among the three. In terms of total CPU times for all problems solved SPSN is 1.3 times faster than CAPNET. 6. Conclusion A new SSP algorithm has been developed for the semi-assiognment problem. The algorithm generalizes the SSP algorithm proposed by Enquist for the assignment problem [8]. The new algorithm is coded and compared with CAPNET, (a specialized primal simplex code) and TRANS an Out-of-Kilter code part of the SAS package. The empirical computational testing showed that the new algorithm dominates CAPNET and TRANS. 7 Acknowlegement The authors would like to acknowlege the support provided by the department of systems Engineering, King Fhad University of Petroleum and Minerals, Dhahran,31261, Saudi Arabia, for conducting this research 15

Table 1. Solution Times in Seconds on Semi-Assignment Problems with a Cost Range of 1 - 1000. No. of Nodes No. of Arcs Times (in seconds) m x n CAPNET TRANS SPSN 50x 500 2,000 1.247 CNR 0.6332 50x 500 5,000 2.079 CNR 0.7456 50x 500 10,000 3.740 CNR 1.568 50x 1000 4,000 2.515 CNR 1.292 50 x 1000 10,000 5.384 CNR 2.904 50 x 1000 20,000 7.830 CNR 4.502 100x 1000 4,000 3.064 CNR 1.742 100 x 1000 10,000 5.235 CNR 3.625 100x 1000 16,000 7.930 CNR 4.370 400 x 4000 10,000 19.56 CNR 13.15 400 x 4000 16,000 25.13 CNR 17.95 Total Solution 83.714 -52.4818 Times CNR = could not run as a result of memory limitations. 16

Table 2. Solution Times in Seconds on Semi-Assignment Problems with a Cost Range of 1 - 10,000. No. of Nodes No. of Arcs Times (in seconds) m x n CAPNET SPSN 50 x 500 2,000 1.483 1.113 50 x 500 5,000 2.563 1.498 50 x 500 10,000 4.112 2.448 50 x 1000 4,000 2.752 2.059 50x 1000 10,000 5.692 4.122 50x 1000 20,000 8.042 6.751 100x 1000 4,000 3.137 2.015 100 x 1000 10,000 5.652 6.074 100x 1000 16,000 8.195 7.969 400 x 4000 10,000 21.30 21.14 400 x 4000 16,000 27.45 26.30 Total Solution 90.378 81.489 Times 17

References [1]. R.T. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows: Theory, Algorithms and Applications, Prentice Hall, (1993). [2]. R.T. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows. In Handbooks in Operations Research and Management Science, Volume I: Optimization, G. Nemhauser, A. Rinnooy Kan and M. Todd (eds.). North-Holland, Amsterdam, (1989), 211-369. [3]. R.F. Barr, Glover and D. Klingman. The Alternating Basis Algorithm for the Assignment Problems, Mathematical Programming, 13, (1977), 1-13. [4]. R.F. Barr, Glover and D. Klingman. New Alternating Basis Algorithm for Semi-Assignment Networks. In Computers and Mathematical Programming, W. White (ed.) National Bureau of Standards Special Publication, U.S. Government Printing Office, Washington, D.C., (1978), 223-232. [5]. W. Cunningham. A Network Simplex Method. Math Prog, 11, (1976), 105116. [6]. R.F. Dial, Glover, D. Karney and D. Klingman. A Computational Analysis of Alternative Algorithms and Labelling Techniques for Finding Shortest Path Trees. Networks 9, (1979), 215-248. [7]. J. Edmonds and R. Krap. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM, 19, (1972), 248-264. [8]. M. Enquist. A Successive Shortest Path Algorithm for the Assignment Problem, IFOR, 20(4), (1982), 370-384. [9]. L. Ford and D. Fulkerson. Flows in Networks. Princeton. Princeton University Press, N.J. (1962). 18

[10]. F.D. Glover, Karney and D. Klingman. A Computational Comparisons of Primal, Dual and Primal-Dual Computer Codes for Network Flow Problems, Research Report CCS 136, Center for Cybernetic Studies, University of Texas, Austin, Texas (1973). [11]. T. Hu. Combinational Algorithms. Addison-Wesley, Reading, Mass (1982). [12]. M. Hung and W. Rom. Solving the Assignment Problem by Relaxation, Operations Research, 28(4), (1980), 969-982. [13]. R. Jonker and T. Volgenant. A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems, Computing, 38, (1987), 325-340. [14]. J. Kennington and R. Helgason. Algorithms for Network Programming. John Wiley, New York, (1980). [15]. J. Kennington and Z. Wang. A Shortest Augmenting Path Algorithm For The Semi-Assignment Problem Operations Research, 40(1), (1992), 178-187. [16]. J. Papadimitriou and K. Steiglitz. Combinational Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, N.J. (1982). [17]. R. Rockafellar. Network Flows and Monotropic Optimization, John Wiley, New York, (1984). [18]. R. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, (1983). [19]. N. Tomizawa. On Some Techniques Useful for the Solution of Transportation Network Problems, Networks 7, (1971), 173-194. 19