C PERM12 SOURCE BP208322 16/06/27 21:16:19 8990 C ******* SAMPLE CALLING PROGRAM FOR SUBROUTINE APC ******* C *** (MIN-COST ASSIGNMENT PROBLEM) *** C *** *** C *** THE PROGRAM IS BASED ON THE PAPER *** C *** G. CARPANETO, S. MARTELLO, P. TOTH "ALGORITHMS *** C *** AND CODES FOR THE ASSIGNMENT PROBLEM", *** C *** ANNALS OF OPERATIONS RESEARCH 7, 1988. *** C *** *** C *** ALL THE SUBROUTINES ARE WRITTEN IN AMERICAN *** C *** STANDARD FORTRAN AND ARE ACCEPTED BY THE *** C *** PFORT VERIFIER. *** C *** *** C *** QUESTIONS AND COMMENTS SHOULD BE DIRECTED TO *** C *** SILVANO MARTELLO AND PAOLO TOTH *** C *** D.E.I.S., UNIVERSITA' DI BOLOGNA, *** C *** VIALE RISORGIMENTO 2, *** C *** 40136, BOLOGNA, ITALY. *** C ************************************************************ C SUBROUTINE PERM12(N,A,F,Z) C C SOLUTION OF THE LINEAR MIN-SUM ASSIGNMENT PROBLEM. C C HUNGARIAN METHOD. COMPLEXITY O(N**3). C C C MEANING OF THE INPUT PARAMETERS: C N = NUMBER OF ROWS AND COLUMNS OF THE COST MATRIX. C A(I,J) = COST OF THE ASSIGNMENT OF ROW I TO COLUMN J . C ON RETURN, THE INPUT PARAMETERS ARE UNCHANGED. C C MEANING OF THE OUTPUT PARAMETERS: C F(I) = COLUMN ASSIGNED TO ROW I . C Z = COST OF THE OPTIMAL ASSIGNMENT = C = A(1,F(1)) + A(2,F(2)) + ... + A(N,F(N)) . C C ALL THE PARAMETERS ARE INTEGERS. C VECTOR F MUST BE DIMENSIONED AT LEAST AT N , MATRIX A C AT LEAST AT (N,N) . AS CURRENTLY DIMENSIONED, THE SIZE C LIMITATION IS N .LE. 260 . IN ALL THE SUBROUTINES, THE C INTERNAL VARIABLES WHICH ARE PRESENTLY DIMENSIONED AT C 260 MUST BE DIMENSIONED AT LEAST AT N . C C THE ONLY MACHINE-DEPENDENT CONSTANT USED IS XINF (DEFINED C BY THE FIRST EXECUTABLE STATEMENT OF THIS SUBROUTINE). XINF C MUST BE SET TO A VERY LARGE INTEGER VALUE. C C THE CODE IS BASED ON THE HUNGARIAN METHOD AS DESCRIBED BY C LAWLER (COMBINATORIAL OPTIMIZATION : NETWORKS AND C MATROIDS, HOLT, RINEHART AND WINSTON, NEW YORK, 1976). C THE ALGORITHMIC PASCAL-LIKE DESCRIPTION OF THE CODE IS C GIVEN IN G.CARPANETO, S.MARTELLO AND P.TOTH, ALGORITHMS AND C CODES FOR THE ASSIGNMENT PROBLEM, ANNALS OF OPERATIONS C RESEARCH 7, 1988. C C SUBROUTINE APC DETERMINES THE INITIAL DUAL AND PARTIAL C PRIMAL SOLUTIONS AND THEN SEARCHES FOR AUGMENTING PATHS C UNTIL ALL ROWS AND COLUMNS ARE ASSIGNED. C C MEANING OF THE MAIN INTERNAL VARIABLES: C FB(J) = ROW ASSIGNED TO COLUMN J . C M = NUMBER OF INITIAL ASSIGNMENTS. C U(I) = DUAL VARIABLE ASSOCIATED WITH ROW I . C V(J) = DUAL VARIABLE ASSOCIATED WITH COLUMN J . C C APC NEEDS THE FOLLOWING SUBROUTINES: INCR C INIT C PATH C C ALL THE SUBROUTINES ARE WRITTEN IN AMERICAN NATIONAL C STANDARD FORTRAN AND ARE ACCEPTED BY THE PFORT VERIFIER. C C C THIS WORK WAS SUPPORTED BY C.N.R. , ITALY. C IMPLICIT INTEGER(I-N) IMPLICIT REAL*8(A-H,O-Z) -INC CCREEL REAL*8 A(N,N),U(N),V(N),Z INTEGER F(N) INTEGER FB(N),RC(N),P(N) XINF = XSGRAN c======================================================================= C SEARCH FOR THE INITIAL DUAL AND PARTIAL PRIMAL SOLUTIONS. c======================================================================= c CALL INIT(N,A,F,M,XINF,U,V,FB,P) CALL PERM13(N,A,F,M,XINF,U,V,FB) IF ( M .EQ. N ) GO TO 2 c======================================================================= C SOLUTION OF THE REDUCED PROBLEM. c======================================================================= DO 1 I=1,N IF ( F(I) .GT. 0 ) GO TO 1 C DETERMINATION OF AN AUGMENTING PATH STARTING FROM ROW I . c CALL PATH(N,A,I,F,XINF,J,U,V,FB,RC) CALL PERM14(N,A,I,F,XINF,J,U,V,FB,RC) C ASSIGNMENT OF ROW I AND COLUMN J . c CALL INCR(N,F,J,U,V,FB,RC) CALL PERM15(N,F,J,FB,RC) 1 CONTINUE c======================================================================= C COMPUTATION OF THE SOLUTION COST Z . c======================================================================= 2 Z = 0 DO 3 K=1,N Z = Z + U(K) + V(K) 3 CONTINUE RETURN END c c======================================================================= c SUBROUTINE INCR(N,F,J,U,V,FB,RC) c C c C ASSIGNMENT OF COLUMN J . c C c INTEGER F(N) c INTEGER U(N),V(N),FB(N),RC(N) c 1 I = RC(J) c FB(J) = I c JJ = F(I) c F(I) = J c J = JJ c IF ( J .GT. 0 ) GO TO 1 c RETURN c END c c======================================================================= c SUBROUTINE INIT(N,A,F,M,XINF,U,V,FB,P) c C c C SEARCH FOR THE INITIAL DUAL AND PARTIAL PRIMAL SOLUTIONS. c C c C P(I) = FIRST UNSCANNED COLUMN OF ROW I . c C c INTEGER A(N,N),F(N) c INTEGER U(N),V(N),FB(N),P(N),R c C PHASE 1 . c M = 0 c DO 10 K=1,N c F(K) = 0 c FB(K) = 0 c 10 CONTINUE c C SCANNING OF THE COLUMNS ( INITIALIZATION OF V(J) ). c DO 40 J=1,N c MIN = XINF c DO 30 I=1,N c IA = A(I,J) c IF ( IA .GT. MIN ) GO TO 30 c IF ( IA .LT. MIN ) GO TO 20 c IF ( F(I) .NE. 0 ) GO TO 30 c 20 MIN = IA c R = I c 30 CONTINUE c V(J) = MIN c IF ( F(R) .NE. 0 ) GO TO 40 c C ASSIGNMENT OF COLUMN J TO ROW R . c M = M + 1 c FB(J) = R c F(R) = J c U(R) = 0 c P(R) = J + 1 c 40 CONTINUE c C PHASE 2 . c C SCANNING OF THE UNASSIGNED ROWS ( UPDATING OF U(I) ). c DO 110 I=1,N c IF ( F(I) .NE. 0 ) GO TO 110 c MIN = XINF c DO 60 K=1,N c IA = A(I,K) - V(K) c IF ( IA .GT. MIN ) GO TO 60 c IF ( IA .LT. MIN ) GO TO 50 c IF ( FB(K) .NE. 0 ) GO TO 60 c IF ( FB(J) .EQ. 0 ) GO TO 60 c 50 MIN = IA c J = K c 60 CONTINUE c U(I) = MIN c JMIN = J c IF ( FB(J) .EQ. 0 ) GO TO 100 c DO 80 J=JMIN,N c IF ( A(I,J) - V(J) .GT. MIN ) GO TO 80 c R = FB(J) c KK = P(R) c IF ( KK .GT. N ) GO TO 80 c DO 70 K=KK,N c IF ( FB(K) .GT. 0 ) GO TO 70 c IF ( A(R,K) - U(R) - V(K) .EQ. 0 ) GO TO 90 c 70 CONTINUE c P(R) = N + 1 c 80 CONTINUE c GO TO 110 c C REASSIGNMENT OF ROW R AND COLUMN K . c 90 F(R) = K c FB(K) = R c P(R) = K + 1 c C ASSIGNMENT OF COLUMN J TO ROW I . c 100 M = M + 1 c F(I) = J c FB(J)= I c P(I) = J + 1 c 110 CONTINUE c RETURN c END c c======================================================================= c SUBROUTINE PATH(N,A,II,F,XINF,JJ,U,V,FB,RC) c C c C DETERMINATION OF AN AUGMENTING PATH STARTING FROM c C UNASSIGNED ROW II AND TERMINATING AT UNASSIGNED COLUMN c C JJ , WITH UPDATING OF DUAL VARIABLES U(I) AND V(J) . c C c C MEANING OF THE MAIN INTERNAL VARIABLES: c C LR(L) = L-TH LABELLED ROW ( L=1,NLR ). c C PI(J) = MIN ( A(I,J) - U(I) - V(J) , SUCH THAT ROW I IS c C LABELLED AND NOT EQUAL TO FB(J) ). c C RC(J) = ROW PRECEDING COLUMN J IN THE CURRENT c C ALTERNATING PATH. c C UC(L) = L-TH UNLABELLED COLUMN ( L=1,NUC ). c C c INTEGER A(N,N),F(N),Z c INTEGER PI(N),LR(N),UC(N) c INTEGER U(N),V(N),FB(N),RC(N),R c C INITIALIZATION. c LR(1) = II c DO 10 K=1,N c PI(K) = A(II,K) - U(II) - V(K) c RC(K) = II c UC(K) = K c 10 CONTINUE c NUC = N c NLR = 1 c GO TO 40 c C SCANNING OF THE LABELLED ROWS. c 20 R = LR(NLR) c DO 30 L=1,NUC c J = UC(L) c IA = A(R,J) - U(R) - V(J) c IF ( IA .GE. PI(J) ) GO TO 30 c PI(J) = IA c RC(J) = R c 30 CONTINUE c C SEARCH FOR A ZERO ELEMENT IN AN UNLABELLED COLUMN. c 40 DO 50 L=1,NUC c J = UC(L) c IF ( PI(J) .EQ. 0 ) GO TO 100 c 50 CONTINUE c C UPDATING OF THE DUAL VARIABLES U(I) AND V(J) . c MIN = XINF c DO 60 L=1,NUC c J = UC(L) c IF ( MIN .GT. PI(J) ) MIN = PI(J) c 60 CONTINUE c DO 70 L=1,NLR c R = LR(L) c U(R) = U(R) + MIN c 70 CONTINUE c DO 90 J=1,N c IF ( PI(J) .EQ. 0 ) GO TO 80 c PI(J) = PI(J) - MIN c GO TO 90 c 80 V(J) = V(J) - MIN c 90 CONTINUE c GO TO 40 c 100 IF ( FB(J) .EQ. 0 ) GO TO 110 c C LABELLING OF ROW FB(J) AND REMOVAL OF THE LABEL OF c C COLUMN J . c NLR = NLR + 1 c LR(NLR) = FB(J) c UC(L) = UC(NUC) c NUC = NUC - 1 c GO TO 20 c C DETERMINATION OF THE UNASSIGNED COLUMN J . c 110 JJ = J c RETURN c END c