diff options
Diffstat (limited to 'glpk-5.0/src/misc/mt1.f')
| -rw-r--r-- | glpk-5.0/src/misc/mt1.f | 277 |
1 files changed, 277 insertions, 0 deletions
diff --git a/glpk-5.0/src/misc/mt1.f b/glpk-5.0/src/misc/mt1.f new file mode 100644 index 0000000..82cc4a1 --- /dev/null +++ b/glpk-5.0/src/misc/mt1.f @@ -0,0 +1,277 @@ + SUBROUTINE MT1(N,P,W,C,Z,X,JDIM,JCK,XX,MIN,PSIGN,WSIGN,ZSIGN) +C +C THIS SUBROUTINE SOLVES THE 0-1 SINGLE KNAPSACK PROBLEM +C +C MAXIMIZE Z = P(1)*X(1) + ... + P(N)*X(N) +C +C SUBJECT TO: W(1)*X(1) + ... + W(N)*X(N) .LE. C , +C X(J) = 0 OR 1 FOR J=1,...,N. +C +C THE PROGRAM IS INCLUDED IN THE VOLUME +C S. MARTELLO, P. TOTH, "KNAPSACK PROBLEMS: ALGORITHMS +C AND COMPUTER IMPLEMENTATIONS", JOHN WILEY, 1990 +C AND IMPLEMENTS THE BRANCH-AND-BOUND ALGORITHM DESCRIBED IN +C SECTION 2.5.2 . +C THE PROGRAM DERIVES FROM AN EARLIER CODE PRESENTED IN +C S. MARTELLO, P. TOTH, "ALGORITHM FOR THE SOLUTION OF THE 0-1 SINGLE +C KNAPSACK PROBLEM", COMPUTING, 1978. +C +C THE INPUT PROBLEM MUST SATISFY THE CONDITIONS +C +C 1) 2 .LE. N .LE. JDIM - 1 ; +C 2) P(J), W(J), C POSITIVE INTEGERS; +C 3) MAX (W(J)) .LE. C ; +C 4) W(1) + ... + W(N) .GT. C ; +C 5) P(J)/W(J) .GE. P(J+1)/W(J+1) FOR J=1,...,N-1. +C +C MT1 CALLS 1 PROCEDURE: CHMT1. +C +C THE PROGRAM IS COMPLETELY SELF-CONTAINED AND COMMUNICATION TO IT IS +C ACHIEVED SOLELY THROUGH THE PARAMETER LIST OF MT1. +C NO MACHINE-DEPENDENT CONSTANT IS USED. +C THE PROGRAM IS WRITTEN IN 1967 AMERICAN NATIONAL STANDARD FORTRAN +C AND IS ACCEPTED BY THE PFORT VERIFIER (PFORT IS THE PORTABLE +C SUBSET OF ANSI DEFINED BY THE ASSOCIATION FOR COMPUTING MACHINERY). +C THE PROGRAM HAS BEEN TESTED ON A DIGITAL VAX 11/780 AND AN H.P. +C 9000/840. +C +C MT1 NEEDS 8 ARRAYS ( P , W , X , XX , MIN , PSIGN , WSIGN +C AND ZSIGN ) OF LENGTH AT LEAST N + 1 . +C +C MEANING OF THE INPUT PARAMETERS: +C N = NUMBER OF ITEMS; +C P(J) = PROFIT OF ITEM J (J=1,...,N); +C W(J) = WEIGHT OF ITEM J (J=1,...,N); +C C = CAPACITY OF THE KNAPSACK; +C JDIM = DIMENSION OF THE 8 ARRAYS; +C JCK = 1 IF CHECK ON THE INPUT DATA IS DESIRED, +C = 0 OTHERWISE. +C +C MEANING OF THE OUTPUT PARAMETERS: +C Z = VALUE OF THE OPTIMAL SOLUTION IF Z .GT. 0 , +C = ERROR IN THE INPUT DATA (WHEN JCK=1) IF Z .LT. 0 : CONDI- +C TION - Z IS VIOLATED; +C X(J) = 1 IF ITEM J IS IN THE OPTIMAL SOLUTION, +C = 0 OTHERWISE. +C +C ARRAYS XX, MIN, PSIGN, WSIGN AND ZSIGN ARE DUMMY. +C +C ALL THE PARAMETERS ARE INTEGER. ON RETURN OF MT1 ALL THE INPUT +C PARAMETERS ARE UNCHANGED. +C + INTEGER P(JDIM),W(JDIM),X(JDIM),C,Z + INTEGER XX(JDIM),MIN(JDIM),PSIGN(JDIM),WSIGN(JDIM),ZSIGN(JDIM) + INTEGER CH,CHS,DIFF,PROFIT,R,T + Z = 0 + IF ( JCK .EQ. 1 ) CALL CHMT1(N,P,W,C,Z,JDIM) + IF ( Z .LT. 0 ) RETURN +C INITIALIZE. + CH = C + IP = 0 + CHS = CH + DO 10 LL=1,N + IF ( W(LL) .GT. CHS ) GO TO 20 + IP = IP + P(LL) + CHS = CHS - W(LL) + 10 CONTINUE + 20 LL = LL - 1 + IF ( CHS .EQ. 0 ) GO TO 50 + P(N+1) = 0 + W(N+1) = CH + 1 + LIM = IP + CHS*P(LL+2)/W(LL+2) + A = W(LL+1) - CHS + B = IP + P(LL+1) + LIM1 = B - A*FLOAT(P(LL))/FLOAT(W(LL)) + IF ( LIM1 .GT. LIM ) LIM = LIM1 + MINK = CH + 1 + MIN(N) = MINK + DO 30 J=2,N + KK = N + 2 - J + IF ( W(KK) .LT. MINK ) MINK = W(KK) + MIN(KK-1) = MINK + 30 CONTINUE + DO 40 J=1,N + XX(J) = 0 + 40 CONTINUE + Z = 0 + PROFIT = 0 + LOLD = N + II = 1 + GO TO 170 + 50 Z = IP + DO 60 J=1,LL + X(J) = 1 + 60 CONTINUE + NN = LL + 1 + DO 70 J=NN,N + X(J) = 0 + 70 CONTINUE + RETURN +C TRY TO INSERT THE II-TH ITEM INTO THE CURRENT SOLUTION. + 80 IF ( W(II) .LE. CH ) GO TO 90 + II1 = II + 1 + IF ( Z .GE. CH*P(II1)/W(II1) + PROFIT ) GO TO 280 + II = II1 + GO TO 80 +C BUILD A NEW CURRENT SOLUTION. + 90 IP = PSIGN(II) + CHS = CH - WSIGN(II) + IN = ZSIGN(II) + DO 100 LL=IN,N + IF ( W(LL) .GT. CHS ) GO TO 160 + IP = IP + P(LL) + CHS = CHS - W(LL) + 100 CONTINUE + LL = N + 110 IF ( Z .GE. IP + PROFIT ) GO TO 280 + Z = IP + PROFIT + NN = II - 1 + DO 120 J=1,NN + X(J) = XX(J) + 120 CONTINUE + DO 130 J=II,LL + X(J) = 1 + 130 CONTINUE + IF ( LL .EQ. N ) GO TO 150 + NN = LL + 1 + DO 140 J=NN,N + X(J) = 0 + 140 CONTINUE + 150 IF ( Z .NE. LIM ) GO TO 280 + RETURN + 160 IU = CHS*P(LL)/W(LL) + LL = LL - 1 + IF ( IU .EQ. 0 ) GO TO 110 + IF ( Z .GE. PROFIT + IP + IU ) GO TO 280 +C SAVE THE CURRENT SOLUTION. + 170 WSIGN(II) = CH - CHS + PSIGN(II) = IP + ZSIGN(II) = LL + 1 + XX(II) = 1 + NN = LL - 1 + IF ( NN .LT. II) GO TO 190 + DO 180 J=II,NN + WSIGN(J+1) = WSIGN(J) - W(J) + PSIGN(J+1) = PSIGN(J) - P(J) + ZSIGN(J+1) = LL + 1 + XX(J+1) = 1 + 180 CONTINUE + 190 J1 = LL + 1 + DO 200 J=J1,LOLD + WSIGN(J) = 0 + PSIGN(J) = 0 + ZSIGN(J) = J + 200 CONTINUE + LOLD = LL + CH = CHS + PROFIT = PROFIT + IP + IF ( LL - (N - 2) ) 240, 220, 210 + 210 II = N + GO TO 250 + 220 IF ( CH .LT. W(N) ) GO TO 230 + CH = CH - W(N) + PROFIT = PROFIT + P(N) + XX(N) = 1 + 230 II = N - 1 + GO TO 250 + 240 II = LL + 2 + IF ( CH .GE. MIN(II-1) ) GO TO 80 +C SAVE THE CURRENT OPTIMAL SOLUTION. + 250 IF ( Z .GE. PROFIT ) GO TO 270 + Z = PROFIT + DO 260 J=1,N + X(J) = XX(J) + 260 CONTINUE + IF ( Z .EQ. LIM ) RETURN + 270 IF ( XX(N) .EQ. 0 ) GO TO 280 + XX(N) = 0 + CH = CH + W(N) + PROFIT = PROFIT - P(N) +C BACKTRACK. + 280 NN = II - 1 + IF ( NN .EQ. 0 ) RETURN + DO 290 J=1,NN + KK = II - J + IF ( XX(KK) .EQ. 1 ) GO TO 300 + 290 CONTINUE + RETURN + 300 R = CH + CH = CH + W(KK) + PROFIT = PROFIT - P(KK) + XX(KK) = 0 + IF ( R .LT. MIN(KK) ) GO TO 310 + II = KK + 1 + GO TO 80 + 310 NN = KK + 1 + II = KK +C TRY TO SUBSTITUTE THE NN-TH ITEM FOR THE KK-TH. + 320 IF ( Z .GE. PROFIT + CH*P(NN)/W(NN) ) GO TO 280 + DIFF = W(NN) - W(KK) + IF ( DIFF ) 370, 330, 340 + 330 NN = NN + 1 + GO TO 320 + 340 IF ( DIFF .GT. R ) GO TO 330 + IF ( Z .GE. PROFIT + P(NN) ) GO TO 330 + Z = PROFIT + P(NN) + DO 350 J=1,KK + X(J) = XX(J) + 350 CONTINUE + JJ = KK + 1 + DO 360 J=JJ,N + X(J) = 0 + 360 CONTINUE + X(NN) = 1 + IF ( Z .EQ. LIM ) RETURN + R = R - DIFF + KK = NN + NN = NN + 1 + GO TO 320 + 370 T = R - DIFF + IF ( T .LT. MIN(NN) ) GO TO 330 + IF ( Z .GE. PROFIT + P(NN) + T*P(NN+1)/W(NN+1)) GO TO 280 + CH = CH - W(NN) + PROFIT = PROFIT + P(NN) + XX(NN) = 1 + II = NN + 1 + WSIGN(NN) = W(NN) + PSIGN(NN) = P(NN) + ZSIGN(NN) = II + N1 = NN + 1 + DO 380 J=N1,LOLD + WSIGN(J) = 0 + PSIGN(J) = 0 + ZSIGN(J) = J + 380 CONTINUE + LOLD = NN + GO TO 80 + END + SUBROUTINE CHMT1(N,P,W,C,Z,JDIM) +C +C CHECK THE INPUT DATA. +C + INTEGER P(JDIM),W(JDIM),C,Z + IF ( N .GE. 2 .AND. N .LE. JDIM - 1 ) GO TO 10 + Z = - 1 + RETURN + 10 IF ( C .GT. 0 ) GO TO 30 + 20 Z = - 2 + RETURN + 30 JSW = 0 + RR = FLOAT(P(1))/FLOAT(W(1)) + DO 50 J=1,N + R = RR + IF ( P(J) .LE. 0 ) GO TO 20 + IF ( W(J) .LE. 0 ) GO TO 20 + JSW = JSW + W(J) + IF ( W(J) .LE. C ) GO TO 40 + Z = - 3 + RETURN + 40 RR = FLOAT(P(J))/FLOAT(W(J)) + IF ( RR .LE. R ) GO TO 50 + Z = - 5 + RETURN + 50 CONTINUE + IF ( JSW .GT. C ) RETURN + Z = - 4 + RETURN + END |