Jsun Yui Wong
The computer program listed below seeks to solve Problem 7 of Lawler and Bell [1, pp. 1107-1108].
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR K=1 TO 8
93 A(K)=FIX(RND*8)
99 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 8
131 X(K)=A(K)
132 NEXT K
811 IF RND<1/8 THEN 901 ELSE IF RND<2/8 THEN 911 ELSE IF RND<3/8 THEN 921 ELSE IF RND<4/8 THEN 931 ELSE IF RND<5/8 THEN 941 ELSE IF RND<6/8 THEN 951 ELSE IF RND<7/8 THEN 961 ELSE 971
901 X(1)=FIX(RND*8)
905 GOTO 1151
911 X(2)=FIX(RND*16)
915 GOTO 1151
921 X(3)=FIX(RND*8)
925 GOTO 1151
931 X(4)=FIX(RND*8)
935 GOTO 1151
941 X(5)=FIX(RND*16)
945 GOTO 1151
951 X(6)=FIX(RND*8)
955 GOTO 1151
961 X(7)=FIX(RND*16)
965 GOTO 1151
971 X(8)=FIX(RND*8)
1151 P1=-12+2*X(1)+2*X(4)+8*X(8)
1159 IF P1<0 THEN P1=P1 ELSE P1=0
1255 P2=-41+11*X(1)+7*X(4)+13*X(6)
1259 IF P2<0 THEN P2=P2 ELSE P2=0
1355 P3=-60+6*X(2)+9*X(4)*X(6)+5*X(7)
1359 IF P3<0 THEN P3=P3 ELSE P3=0
1455 P4=-42+3*X(2)+5*X(5)+7*X(8)
1459 IF P4<0 THEN P4=P4 ELSE P4=0
1462 P5=-53+6*X(2)*X(7)+9*X(3)+5*X(5)
1469 IF P5<0 THEN P5=P5 ELSE P5=0
1472 P6=-13+4*X(3)*X(7)+X(5)
1479 IF P6<0 THEN P6=P6 ELSE P6=0
1480 P7=-69+2*X(1)+4*X(2)+7*X(4)+3*X(5)+X(7)
1481 IF P7>0 THEN P7=P7 ELSE P7=0
1482 P8=-47+9*X(1)*X(8)+6*X(3)*X(5)+4*X(3)*X(7)
1483 IF P8>0 THEN P8=P8 ELSE P8=0
1484 P9=-73+12*X(2)+8*X(2)*X(8)+2*X(3)*X(6)
1485 IF P9>0 THEN P9=P9 ELSE P9=0
1486 P10=-31+1*X(3)+4*X(5)+2*X(6)+9*X(8)
1487 IF P10>0 THEN P10=P10 ELSE P10=0
1488 P=-3*X(1)*X(4)-X(2)-X(2)*X(5)-X(2)*X(7)-6*X(3)*X(8)-X(5)*X(7)-11*X(6)-333333!*(ABS(P1)+ABS(P2)+ABS(P3)+ABS(P4)+ABS(P5)+ABS(P6)+ABS(P7)+ABS(P8)+ABS(P9)+ABS(P10))
1499 PR=-3*X(1)*X(4)-X(2)-X(2)*X(5)-X(2)*X(7)-6*X(3)*X(8)-X(5)*X(7)-11*X(6)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-999 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 8 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
4 4 1 2 6
2 2 0
-94 -94 -31968
2 4 1 4 6
1 2 0
-83 -83 -31939
Interpreted in accordance with line 1912, line 1914, and line 1915, the output through JJJJ=-31939 was produced in the first 8 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
Reference
[1] E. L. Lawler, M. D. Bell, "A Method for Solving Discrete Optimization Problems," Operations Research 14, 1098-1112 (1965).
