Sources Esope | Cast3M

perm22
C PERM22    SOURCE    BP208322  16/06/27    21:16:22     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 PERM22(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  INF (DEFINED
C BY THE FIRST EXECUTABLE STATEMENT OF THIS SUBROUTINE). INF
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)
 
      INTEGER A(N,N),F(N),Z
      INTEGER U(N),V(N),FB(N),RC(N),P(N)
 
      INF = 10**9
 
c=======================================================================
C SEARCH FOR THE INITIAL DUAL AND PARTIAL PRIMAL SOLUTIONS.
c=======================================================================
c       CALL INIT(N,A,F,M,INF,U,V,FB,P)
      CALL PERM23(N,A,F,M,INF,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,INF,J,U,V,FB,RC)
        CALL PERM24(N,A,I,F,INF,J,U,V,FB,RC)
 
C ASSIGNMENT OF ROW  I  AND COLUMN  J .
c         CALL INCR(N,F,J,U,V,FB,RC)
        CALL PERM25(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,INF,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 = INF
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 = INF
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,INF,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 = INF
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