C ALGORITHM 608, COLLECTED ALGORITHMS FROM ACM. C ALGORITHM APPEARED IN ACM-TRANS. MATH. SOFTWARE, VOL.9, NO. 3, C DEC., 1983, P. 461-466. SUBROUTINE HGW(N, C, F, D, NC, NF, ND, LOC3N, WORK4N) HGW 10 DIMENSION C(NC,1), F(NF,1), D(ND,1), LOC3N(1), WORK4N(1) C C D.WEST 6 MAY 83 C PURPOSE: C THE ALGORITHM COMPUTES A PERMUTATION L OF 1:N TO APPROXIMATELY C MINIMIZE THE OBJECTIVE FUNCTION: C OBJ=SUM/I=1 TO N/(C(I,LI)+SUM/J=1 TO N/(F(I,J)*D(LI,LJ)) C WHERE LI,LJ ARE THE IMAGES OF I,J UNDER L. NEITHER F NOR D IS C ASSUMED SYMMETRIC,BUT THEIR DIAGONAL ELEMENTS ARE ZERO. C ARGUMENT DESCRIPTIONS: C INPUT ONLY,UNCHANGED ON EXIT: C N (>1) IS THE SIZE OF THE PROBLEM (SEE ABOVE). C C F AND D ARE REAL ARRAYS CONTAINING THE COEFFICIENTS OF THE C PROBLEM IN THEIR LEADING N BY N SUBMATRICES. THE FIRST C N DIAGONAL ELEMENTS OF F AND D MUST BE ZERO. C NC,NF AND ND ARE THE DECLARED LIMITS OF SUBSCRIPT 1 OF C C F AND D RESPECTIVELY. THEY MUST BE >= N. C OUTPUT ONLY,IGNORED ON INPUT: C LOC3N IS AN INTEGER VECTOR OF LENGTH AT LEAST 3*N. ON EXIT C IT CONTAINS IN ELEMENT I THE IMAGE OF I UNDER THE C PERMUTATION CHOSEN AS SOLUTION FOR 1<=I<=N. THE C REMAINDER OF LOC3N IS USED AS WORKSPACE. C WORK4N IS A REAL VECTOR OF LENGTH AT LEAST 4*N. ON EXIT ELEMENT C 1 CONTAINS THE VALUE OF THE OBJECTIVE FUNCTION C CORRESPONDING TO THE PERMUTATION IN LOC3N. THE C REMAINDER OF WORK4N IS USED AS WORKSPACE. C METHOD: C THE ALGORITHM BUILDS THE FINAL PERMUTATION C IN N STAGES. AFTER K STAGES.THE CURRENT PARTIAL PERMUTATION C CONSISTS OF THE ORDERED SETS S' AND L',WHERE S'(I)<->L'(I) FOR C I=1 TO K. THE CORRESPONDING UNORDERED COMPLEMENTARY SETS S AND C L ARE EACH OF SIZE N-K. AT EACH STAGE WE CHOOSE I FROM S AND C J FROM L SUCH THAT WHEN THESE ARE TRANSFERRED TO S' AND L' C RESPECTIVELY,THE MEAN OBJECTIVE FUNCTION OVER ALL POSSIBLE C COMPLETIONS OF THE RESULTING PARTIAL PERMUTATION IS MINIMIZED C OVER ALL CHOICES OF I AND J. C SEE C. HEIDER, NAV. RES. LOG. Q., VOL 20 (1973) 699 C ALL POSSIBLE PAIR EXCHANGES ARE THEN CONSIDERED,AND THE MOST C ADVANTAGEOUS,IF ANY,IS EXECUTED. THIS PROCESS IS REPEATED UNTIL C N PAIRS HAVE BEEN EXCHANGED,OR NO EXCHANGE GIVES IMPROVEMENT. C EXTERNAL ROUTINES CALLED: C INITRD,DELTA,UPDRD,DELTX. C IF EITHER F OR D IS SYMMETRIC,THE ALTERNATIVE VERSIONS OF C DELTA AND DELTX,WHICH EXPLOIT THIS SYMMETRY,MAY BE USED. C SEE THE COMMENTS IN THESE ALTERNATIVE VERSIONS. C DEFINITIONS OF INTERMEDIATE RESULTS: C THE SET S' IS STORED IN LOC3N(N1+1)...LOC3N(N1+K) C THE SET S IS STORED IN LOC3N(N1+K+1)...LOC3N(N1+N) C THE SET L' IS STORED IN LOC3N(N2+1)...LOC3N(N2+K) C THE SET L IS STORED IN LOC3N(N2+K+1)...LOC3N(N2+N) C FOR I = 1 TO N: C SUM /J IN S/ F(I,J) IS STORED IN WORK4N(I) C SUM /J IN L/ D(I,J) IS STORED IN WORK4N(N1+I) C SUM /J IN S/ F(J,I) IS STORED IN WORK4N(N2+I) C SUM /J IN L/ D(J,I) IS STORED IN WORK4N(N3+I) C IF I IS IN S',THE CORRESPONDING MEMBER OF L' IS DENOTED LI C BELOW. SIMILARLY LJ CORRESPONDS TO J. THEN: C BP(1)=SUM/I,J IN S'/ F(I,J)*D(LI,LJ) C BP(2)=SUM/I IN S',J IN S,M IN L/F(I,J)*D(LI,M)+F(J,I)*D(M,LI) C BP(3)=BP(6)*BP(7) C BP(4)=SUM /I IN S'/ C(I,LI) C BP(5)=SUM /I IN S,J IN L/ C(I,J) C BP(6)=SUM /I,J IN S/ F(I,J) C BP(7)=SUM /I,J IN L/ D(I,J) C THEN THE AVERAGE VALUE OF THE OBJECTIVE FUNCTION OVER ALL C COMPLETIONS OF THE CURRENT PARTIAL PERMUTATION IS: C OBJ=BP(1)+BP(2)/(N1-K)+BP(3)/((N1-K)*(N1-K-1))+ C BP(4)+BP(5)/(N1-K) C WHEN K=N1-1 THE PERMUTATION HAS BEEN COMPLETED AND THIS C DEFINITION BECOMES IDENTICAL TO THE ONE IN LINE 8. THE ABOVE C GROUP OF DEFINITIONS ARE ESSENTIALLY THE INVARIANT ASSERTIONS C FOR THE DO 30 LOOP IN THIS SUBROUTINE. C COMMON /HGWC/ BP(7), BPN(7), BPB(7), RFNK, RFNK1, RFNK2, K, N1, * N2, N3 C IF (N.LE.1) RETURN N1 = N N2 = N + N N3 = 3*N C INITIALIZE RECURRENCE DATA CALL INITRD(C, F, D, NC, NF, ND, PNORM, LOC3N(N1+1), LOC3N(N2+1), * WORK4N(1), WORK4N(N1+1), WORK4N(N2+1), WORK4N(N3+1)) OBJ = (BP(3)*RFNK1+BP(5))*RFNK NM1 = N - 1 C DO 30 KP1=1,NM1 K = KP1 - 1 C SELECT CANDIDATES FOR POSITION KP1 IN S' AND L' TO GIVE A C MAXIMAL REDUCTION IN THE AVERAGE OBJECTIVE FUNCTION. DELBST = PNORM C DELBST NEED ONLY BE LARGER THAN THE ROUNDING ERROR IN DELTA C DO 20 I=KP1,N IS = N1 + I IBAR = LOC3N(IS) C DO 10 J=KP1,N JL = N2 + J C PRE-EVALUATE EFFECT ON OBJ OF ASSIGNMENT IBAR<->LOC3N(JL) TEMP = DELTA(IBAR,LOC3N(JL),C,F,D,NC,NF,ND,LOC3N(N1+1), * LOC3N(N2+1),WORK4N(1),WORK4N(N1+1),WORK4N(N2+1), * WORK4N(N3+1)) IF (TEMP.GE.DELBST) GO TO 10 C GOT AN IMPROVEMENT,SO SAVE IT IBEST = I JBEST = J DELBST = TEMP BPB(1) = BPN(1) BPB(2) = BPN(2) BPB(3) = BPN(3) BPB(4) = BPN(4) BPB(5) = BPN(5) BPB(6) = BPN(6) BPB(7) = BPN(7) 10 CONTINUE C 20 CONTINUE C C EXCHANGE BEST ITEMS INTO POSITION KP1 KP1S = N1 + KP1 KP1L = N2 + KP1 IBESTS = N1 + IBEST JBESTL = N2 + JBEST ITEMP = LOC3N(KP1S) LOC3N(KP1S) = LOC3N(IBESTS) LOC3N(IBESTS) = ITEMP JTEMP = LOC3N(KP1L) LOC3N(KP1L) = LOC3N(JBESTL) LOC3N(JBESTL) = JTEMP OBJ = OBJ + DELBST C UPDATE RECURRENCE DATA IF (KP1.NE.NM1) CALL UPDRD(F, D, NF, ND, LOC3N(N1+1), * LOC3N(N2+1), WORK4N(1), WORK4N(N1+1), WORK4N(N2+1), * WORK4N(N3+1)) 30 CONTINUE C C THE FINAL ITERATION, WITH K=N-1, IS NOT PERFORMED SINCE THERE C IS ONLY ONE CANDIDATE PAIR AND IT IS ALREADY IN PLACE. C NOW UNSCRAMBLE THE PERMUTATION. C DO 40 I=1,N IL = N2 + I IS = N1 + I LS = LOC3N(IS) LOC3N(LS) = LOC3N(IL) 40 CONTINUE C C THE CONSTRUCTION PHASE IS NOW COMPLETE. THE REMAINING CODE TRIES C TO IMPROVE THE CURRENT APPROXIMATE SOLUTION USING PAIR EXCHANGES. C IF THE USER WISHES TO TRADE SOLUTION QUALITY FOR SPEED OF C COMPUTATION, THE FOLLOWING STATEMENTS UP TO AND INCLUDING C LABEL 90 MAY BE OMITTED. C DO 70 M=1,N C AT MOST N TIMES DELBST = 0. C DO 60 I=2,N IM1 = I - 1 C DO 50 J=1,IM1 TEMP = DELTX(I,J,C,F,D,NC,NF,ND,LOC3N) IF (TEMP.GE.DELBST) GO TO 50 C GOT AN IMPROVEMENT,SO SAVE IT IBEST = I JBEST = J DELBST = TEMP 50 CONTINUE C 60 CONTINUE C IF (DELBST.GE.0.) GO TO 80 C PERFORM EXCHANGE LI = LOC3N(IBEST) LJ = LOC3N(JBEST) LOC3N(IBEST) = LJ LOC3N(JBEST) = LI OBJ = OBJ + DELBST 70 CONTINUE C 80 CONTINUE WORK4N(1) = OBJ RETURN END FUNCTION DELTA(IBAR, JBAR, C, F, D, NC, NF, ND, LS, LL, W1, W2, DEL 10 * W3, W4) DIMENSION C(NC,1), F(NF,1), D(ND,1), LS(1), LL(1), W1(1), W2(1), * W3(1), W4(1) C C CALLED BY THE QUADRATIC ASSIGNMENT HEURISTIC HGW. SEE THE C COMMENTS IN THAT ROUTINE FOR MORE INFORMATION. C RETURNS THE CHANGE IN OBJ (NEW - OLD) THAT WOULD BE PRODUCED C BY TRANSFERRING IBAR FROM S TO S' AND JBAR FROM L TO L'. C THESE TRANSFERS ARE ONLY VIRTUAL. ON EXIT BPN CONTAINS THE C CORRESPONDING NEW VALUES OF BP. F AND D ARE NOT ASSUMED SYMMETRIC. C ASSERT:K.LE.N1-2 C COMMON /HGWC/ BP(7), BPN(7), BPB(7), RFNK, RFNK1, RFNK2, K, N1, * N2, N3 C DB1 = 0. DBP2 = W1(IBAR)*W2(JBAR) + W3(IBAR)*W4(JBAR) IF (K.EQ.0) GO TO 20 C DO 10 M=1,K M1 = LS(M) LM1 = LL(M) F1 = F(IBAR,M1) F2 = F(M1,IBAR) D1 = D(JBAR,LM1) D2 = D(LM1,JBAR) DB1 = DB1 + F1*D1 + F2*D2 DBP2 = DBP2 - F2*W2(LM1) - F1*W4(LM1) - W1(M1)*D2 - W3(M1)*D1 10 CONTINUE C DBP2 = DBP2 + DB1 20 CONTINUE C C THE AVERAGE OBJECTIVE FUNCTION, OBJ, FOR THE CURRENT PARTIAL C PERMUTATION IS CALCULABLE FROM THE CONTENTS OF THE ARRAY BP, C ALTHOUGH WE DO NOT DO SO EXPLICITLY. WE NOW CONSTRUCT DELTA, THE C ANTICIPATED CHANGE IN OBJ, FROM THE CORRESPONDING CHANGE IN BP. C BPN(1) = BP(1) + DB1 BPN(2) = BP(2) + DBP2 BPN(6) = BP(6) - W1(IBAR) - W3(IBAR) BPN(7) = BP(7) - W2(JBAR) - W4(JBAR) BPN(3) = BPN(6)*BPN(7) IF (K.GE.N1-2) BPN(3) = 0. BPN(4) = BP(4) + C(IBAR,JBAR) DBP5 = C(IBAR,JBAR) KP1 = K + 1 C DO 30 M=KP1,N1 M1 = LS(M) LM1 = LL(M) DBP5 = DBP5 - C(IBAR,LM1) - C(M1,JBAR) 30 CONTINUE C BPN(5) = BP(5) + DBP5 DELTA = DB1 + C(IBAR,JBAR) - RFNK*(BP(2)+BP(5)) + * RFNK1*((BPN(3)*RFNK2-BP(3)*RFNK)+(BPN(2)+BPN(5))) RETURN END FUNCTION DELTA(IBAR, JBAR, C, F, D, NC, NF, ND, LS, LL, W1, W2, DEL 10 * W3, W4) DIMENSION C(NC,1), F(NF,1), D(ND,1), LS(1), LL(1), W1(1), W2(1), * W3(1), W4(1) C C CALLED BY THE QUADRATIC ASSIGNMENT HEURISTIC HGW. SEE THE C COMMENTS IN THAT ROUTINE FOR MORE INFORMATION. C SYMMETRIC VERSION. IF EITHER F OR D IS SYMMETRIC,THE OTHER C CAN BE REPLACED BY THE AVERAGE OF ITSELF AND ITS TRANSPOSE C WITHOUT CHANGING THE SOLUTION. THIS IS ASSUMED TO HAVE BEEN DONE. C C RETURNS THE CHANGE IN OBJ (NEW - OLD) THAT WOULD BE PRODUCED C BY TRANSFERRING IBAR FROM S TO S' AND JBAR FROM L TO L'. C ON EXIT,BPN CONTAINS THE CORRESPONDING NEW VALUES OF BP. C ASSERT:K.LE.N1-2 C COMMON /HGWC/ BP(7), BPN(7), BPB(7), RFNK, RFNK1, RFNK2, K, N1, * N2, N3 C DB1 = 0. DBP2 = W1(IBAR)*W2(JBAR) IF (K.EQ.0) GO TO 20 C DO 10 M=1,K M1 = LS(M) LM1 = LL(M) F1 = F(IBAR,M1) D1 = D(JBAR,LM1) DB1 = DB1 + F1*D1 DBP2 = DBP2 - F1*W2(LM1) - W1(M1)*D1 10 CONTINUE C DBP2 = DBP2 + DB1 20 CONTINUE C C THE AVERAGE OBJECTIVE FUNCTION, OBJ, FOR THE CURRENT PARTIAL C PERMUTATION IS CALCULABLE FROM THE CONTENTS OF THE ARRAY BP, C ALTHOUGH WE DO NOT DO SO EXPLICITLY. WE NOW CONSTRUCT DELTA, THE C ANTICIPATED CHANGE IN OBJ, FROM THE CORRESPONDING CHANGE IN BP. C DB1 = DB1 + DB1 DBP2 = DBP2 + DBP2 BPN(1) = BP(1) + DB1 BPN(2) = BP(2) + DBP2 BPN(6) = BP(6) - W1(IBAR) - W1(IBAR) BPN(7) = BP(7) - W2(JBAR) - W2(JBAR) BPN(3) = BPN(6)*BPN(7) IF (K.GE.N1-2) BPN(3) = 0. BPN(4) = BP(4) + C(IBAR,JBAR) DBP5 = C(IBAR,JBAR) KP1 = K + 1 C DO 30 M=KP1,N1 M1 = LS(M) LM1 = LL(M) DBP5 = DBP5 - C(IBAR,LM1) - C(M1,JBAR) 30 CONTINUE C BPN(5) = BP(5) + DBP5 DELTA = DB1 + C(IBAR,JBAR) - RFNK*(BP(2)+BP(5)) + * RFNK1*((BPN(3)*RFNK2-BP(3)*RFNK)+(BPN(2)+BPN(5))) RETURN END SUBROUTINE INITRD(C, F, D, NC, NF, ND, PNORM, LS, LL, W1, W2, W3, INI 10 * W4) DIMENSION C(NC,1), F(NF,1), D(ND,1), LS(1), LL(1), W1(1), W2(1), * W3(1), W4(1) C INITIALIZE RECURRENCE DATA C CALLED BY THE QUADRATIC ASSIGNMENT HEURISTIC HGW. SEE THE C COMMENTS IN THAT ROUTINE FOR MORE INFORMATION. COMMON /HGWC/ BP(7), BPN(7), BPB(7), RFNK, RFNK1, RFNK2, K, N1, * N2, N3 C C SCSL = 0. SFS = 0. SDL = 0. CMX = 0. FMX = 0. DMX = 0. RFNK = 1./FLOAT(N1) RFNK1 = 0. RFNK1 = 1./FLOAT(N1-1) RFNK2 = 0. IF (N1.GT.2) RFNK2 = 1./FLOAT(N1-2) C DO 20 I=1,N1 LS(I) = I LL(I) = I C INITIALIZE ROW AND COL SUMS FR = 0. FC = 0. DR = 0. DC = 0. C DO 10 J=1,N1 SCSL = SCSL + C(I,J) CMX = AMAX1(CMX,ABS(C(I,J))) FR = FR + F(I,J) FMX = AMAX1(FMX,ABS(F(I,J))) FC = FC + F(J,I) DR = DR + D(I,J) DMX = AMAX1(DMX,ABS(D(I,J))) DC = DC + D(J,I) 10 CONTINUE C SFS = SFS + FR SDL = SDL + DR W1(I) = FR W3(I) = FC W2(I) = DR W4(I) = DC 20 CONTINUE C BP(1) = 0. BP(2) = 0. BP(3) = SFS*SDL BP(4) = 0. BP(5) = SCSL BP(6) = SFS BP(7) = SDL PNORM = CMX + FMX*DMX C PNORM IS AN UPPER BOUND ON THE ERROR IN EVALUATING OBJ IF N1 IS C LESS THAN THE RECIPROCAL OF THE MACHINE PRECISION RETURN END SUBROUTINE UPDRD(F, D, NF, ND, LS, LL, W1, W2, W3, W4) UPD 10 DIMENSION F(NF,1), D(ND,1), LS(1), LL(1), W1(1), W2(1), W3(1), * W4(1) C C UPDATE RECURRENCE DATA JUST BEFORE K IS INCREMENTED C CALLED BY THE QUADRATIC ASSIGNMENT HEURISTIC HGW. SEE THE C COMMENTS IN THAT ROUTINE FOR MORE INFORMATION. C ASSERT: K<=N1-2 C COMMON /HGWC/ BP(7), BPN(7), BPB(7), RFNK, RFNK1, RFNK2, K, N1, * N2, N3 C KP1 = K + 1 KP11 = LS(KP1) LKP1 = LL(KP1) C DO 10 I=1,N1 W1(I) = W1(I) - F(I,KP11) W3(I) = W3(I) - F(KP11,I) W2(I) = W2(I) - D(I,LKP1) W4(I) = W4(I) - D(LKP1,I) 10 CONTINUE C BP(1) = BPB(1) BP(2) = BPB(2) BP(3) = BPB(3) BP(4) = BPB(4) BP(5) = BPB(5) BP(6) = BPB(6) BP(7) = BPB(7) RFNK = RFNK1 RFNK1 = RFNK2 RFNK2 = 0. IF (KP1.LT.N1-2) RFNK2 = 1./FLOAT(N1-KP1-2) C NEXT VALUE OF K IS KP1 RETURN END FUNCTION DELTX(I, J, C, F, D, NC, NF, ND, LOC3N) DEL 10 DIMENSION C(NC,1), F(NF,1), D(ND,1), LOC3N(1) C C CALLED BY THE QUADRATIC ASSIGNMENT HEURISTIC HGW. SEE THE C COMMENTS IN THAT ROUTINE FOR MORE INFORMATION. C RETURNS THE CHANGE (NEW - OLD) IN THE HGW OBJECTIVE FUNCTION THAT C WOULD BE PRODUCED IF THE EXISTING ASSIGNMENT PAIRS (I<->LI) AND C (J<->LJ) WERE REPLACED BY (I<->LJ) AND (J<->LI). I AND J ARE IN C S',LI AND LJ ARE IN L'. F AND D ARE NOT ASSUMED SYMMETRIC. C COMMON /HGWC/ BP(7), BPN(7), BPB(7), RFNK, RFNK1, RFNK2, K, N1, * N2, N3 LI = LOC3N(I) LJ = LOC3N(J) DELTX = C(I,LJ) - C(I,LI) + C(J,LI) - C(J,LJ) + * (F(I,J)-F(J,I))*(D(LJ,LI)-D(LI,LJ)) C DO 10 M=1,N1 IF (M.EQ.I) GO TO 10 IF (M.EQ.J) GO TO 10 LM = LOC3N(M) DELTX = DELTX + (F(I,M)-F(J,M))*(D(LJ,LM)-D(LI,LM)) + * (F(M,I)-F(M,J))*(D(LM,LJ)-D(LM,LI)) 10 CONTINUE C RETURN END FUNCTION DELTX(I, J, C, F, D, NC, NF, ND, LOC3N) DEL 10 DIMENSION C(NC,1), F(NF,1), D(ND,1), LOC3N(1) C C CALLED BY THE QUADRATIC ASSIGNMENT HEURISTIC HGW. SEE THE C COMMENTS IN THAT ROUTINE FOR MORE INFORMATION. C SYMMETRIC VERSION. IF EITHER F OR D IS SYMMETRIC,THE OTHER C CAN BE REPLACED BY THE AVERAGE OF ITSELF AND ITS TRANSPOSE C WITHOUT CHANGING THE SOLUTION. THIS IS ASSUMED TO HAVE BEEN DONE. C C RETURNS THE CHANGE (NEW - OLD) IN THE HGW OBJECTIVE FUNCTION THAT C WOULD BE PRODUCED IF THE EXISTING ASSIGNMENT PAIRS (I<->LI) AND C (J<->LJ) WERE REPLACED BY (I<->LJ) AND (J<->LI). I AND J ARE IN C S',LI AND LJ ARE IN L'. C COMMON /HGWC/ BP(7), BPN(7), BPB(7), RFNK, RFNK1, RFNK2, K, N1, * N2, N3 LI = LOC3N(I) LJ = LOC3N(J) DELTX = 0. C DO 10 M=1,N1 IF (M.EQ.I) GO TO 10 IF (M.EQ.J) GO TO 10 LM = LOC3N(M) DELTX = DELTX + (F(I,M)-F(J,M))*(D(LJ,LM)-D(LI,LM)) 10 CONTINUE C DELTX = DELTX + DELTX + (C(I,LJ)-C(I,LI)+C(J,LI)-C(J,LJ)) RETURN END C PROGRAM MAIN(OUTPUT,TAPE6=OUTPUT) MAN 10 C MAIN PROG TO TEST THE QUADRATIC ASSIGNMENT HEURISTIC HGW ON MAN 20 C A VARIANT OF GAVETT AND PLYTER'S 4-DIMENSIONAL TEST EXAMPLE. MAN 30 C SEE OPERATIONS RESEARCH VOL 14 (1966) P210 FOR ORIGINAL PROBLEM MAN 40 C SOLUTION IS: OBJ=406, ASSIGNMENTS: 4,1,3,2 MAN 50 DIMENSION C(5,5), F(5,5), D(5,5), LOC3N(12), WORK4N(16) MAN 60 LOGICAL GOOD MAN 70 DATA F(1,1) /0./, F(1,2) /10./, F(1,3) /20./, F(1,4) /5./, F(2,1) MAN 80 * /18./, F(2,2) /0./, F(2,3) /9./, F(2,4) /4./, F(3,1) /8./, MAN 90 * F(3,2) /6./, F(3,3) /0./, F(3,4) /8./, F(4,1) /8./, F(4,2) /0./, MAN 100 * F(4,3) /15./, F(4,4) /0./ MAN 110 DATA D(1,1) /0./, D(1,2) /6./, D(1,3) /7./, D(1,4) /2./, D(2,1) MAN 120 * /6./, D(2,2) /0./, D(2,3) /5./, D(2,4) /6./, D(3,1) /7./, D(3,2) MAN 130 * /5./, D(3,3) /0./, D(3,4) /1./, D(4,1) /2./, D(4,2) /6./, D(4,3) MAN 140 * /1./, D(4,4) /0./ MAN 150 N = 4 MAN 160 NC = 5 MAN 170 NF = 5 MAN 180 ND = 5 MAN 190 DO 20 I=1,N MAN 200 DO 10 J=1,N MAN 210 C(I,J) = 0. MAN 220 C SYMMETRIZE F FOR COMPATIBILITY WITH SYMMETRIC CODE MAN 230 IF (I.GE.J) GO TO 10 MAN 240 F(I,J) = 0.5*(F(I,J)+F(J,I)) MAN 250 F(J,I) = F(I,J) MAN 260 10 CONTINUE MAN 270 20 CONTINUE MAN 280 CALL HGW(N, C, F, D, NC, NF, ND, LOC3N, WORK4N) MAN 290 WRITE (6,99999) WORK4N(1), (LOC3N(I),I=1,N) MAN 300 99999 FORMAT (5H OBJ=, F10.2, 12H ASSIGNMENT=, 4I3) MAN 310 GOOD = (LOC3N(1).EQ.4) .AND. (LOC3N(2).EQ.1) .AND. MAN 320 * (LOC3N(3).EQ.3) .AND. (LOC3N(4).EQ.2) .AND. (ABS(WORK4N(1)-406.) MAN 330 * .LT.0.5) MAN 340 IF (.NOT.GOOD) GO TO 30 MAN 350 WRITE (6,99998) MAN 360 99998 FORMAT (8H CORRECT) MAN 370 STOP MAN 380 30 WRITE (6,99997) MAN 390 99997 FORMAT (6H ERROR) MAN 400 STOP MAN 410 END MAN 420