Jsun Yui Wong
The computer program listed below seeks to solve the following problem.
Objective function:
Maximize:
-10*X(1)-7*X(2)-X(3)-12*X(4)-2*X(5)-8*X(6)-3*X(7)-X(8)-5*X(9)-3*X(10)
Constraints:
-2-3*X(1)+12*X(2)+8*X(3)-X(4)+7*X(9)-2*X(10)>=0
-1-X(2)+10*X(3)+5*X(5)-X(6)-7*X(7)-X(8)>=0
-1-5*X(1)+3*X(2)+X(3)+2*X(8)-X(10)>=0
1+5*X(1)-3*X(2)-X(3)-2*X(8)+X(10)>=0
-3+4*X(3)+2*X(4)+5*X(6)-X(7)+9*X(8)+2*X(9)>=0
-7-9*X(2)+12*X(4)+7*X(5)-6*X(6)-2*X(8)+15*X(9)-3*X(10)>=0
-1+8*X(1)-5*X(2)-2*X(3)+7*X(4)+X(5)+5*X(7)+10*X(9)>=0
X(j)=0, 1
j=1, 2, 3,...,10
This problem is the 10-variable 0,1 problem on page 58 of Plane and McMillan [1].
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 10
93 A(K)=FIX(RND*2)
99 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 10
131 X(K)=A(K)
132 NEXT K
1110 IJU=1+FIX(RND*10)
1111 X(IJU)=FIX(RND*2)
1151 PEN1=-2-3*X(1)+12*X(2)+8*X(3)-X(4)+7*X(9)-2*X(10)
1159 IF PEN1<0 THEN PEN1=PEN1 ELSE PEN1=0
1255 PEN2=-1-X(2)+10*X(3)+5*X(5)-X(6)-7*X(7)-X(8)
1259 IF PEN2<0 THEN PEN2=PEN2 ELSE PEN2=0
1355 PEN3=-1-5*X(1)+3*X(2)+X(3)+2*X(8)-X(10)
1359 IF PEN3<0 THEN PEN3=PEN3 ELSE PEN3=0
1455 PEN4=1+5*X(1)-3*X(2)-X(3)-2*X(8)+X(10)
1459 IF PEN4<0 THEN PEN4=PEN4 ELSE PEN4=0
1462 PEN5=-3+4*X(3)+2*X(4)+5*X(6)-X(7)+9*X(8)+2*X(9)
1469 IF PEN5<0 THEN PEN5=PEN5 ELSE PEN5=0
1472 PEN6=-7-9*X(2)+12*X(4)+7*X(5)-6*X(6)-2*X(8)+15*X(9)-3*X(10)
1479 IF PEN6<0 THEN PEN6=PEN6 ELSE PEN6=0
1482 PEN7=-1+8*X(1)-5*X(2)-2*X(3)+7*X(4)+X(5)+5*X(7)+10*X(9)
1485 IF PEN7<0 THEN PEN7=PEN7 ELSE PEN7=0
1488 P=-10*X(1)-7*X(2)-X(3)-12*X(4)-2*X(5)-8*X(6)-3*X(7)-X(8)-5*X(9)-3*X(10)-333333!*(ABS(PEN1)+ABS(PEN2)+ABS(PEN3)+ABS(PEN4)+ABS(PEN5)+ABS(PEN6)+ABS(PEN7))
1499 PR=-10*X(1)-7*X(2)-X(3)-12*X(4)-2*X(5)-8*X(6)-3*X(7)-X(8)-5*X(9)-3*X(10)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-7 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 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 5 seconds of running is presented below.
0 0 1 0 0
0 0 0 1 0
-6 -6 -32000
This solution also occurred at JJJJ=-31992, -31989, -31988, -31982, -31981, -31980,
-31970, -31969, -31964, -31962, -31960, -31957, -31956, -31954, -31952, -31942,
-31939, -31936, and -31927.
And a different solution also occurred:
0 0 1 0 1
0 1 0 0 0
-6 -6 -31938
0 0 1 0 1
0 1 0 0 0
-6 -6 -31929
0 0 1 0 1
0 1 0 0 0
-6 -6 -31926
Interpreted in accordance with line 1912, line 1913, and line 1914, the output through JJJJ=-31926 was produced in the first 5 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
Reference
[1] D. R. Plane, C. McMillan, Jr., "Discrete Optimization," Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1971.
