Jsun Yui Wong
The computer program listed below seeks to solve the following problem.
Objective function:
Maximize:
-5*X(1)-1*X(2)-3*X(3)-2*X(4)-6*X(5)-4*X(6)-7*X(7)-2*X(8)-4*X(9)-1*X(10)-1*X(11)-5*X(12)
Constraints:
6-1*X(1)+3*X(2)-12*X(3)-X(5)+7*X(6)-X(7)+3*X(10)-5*X(11)-1*X(12)<=0
-1+3*X(1)-7*X(2)+1*X(4)+6*X(5)<=0
4+11*X(1)+X(3)-7*X(4)-1*X(6)+2*X(7)+X(8)-5*X(9)+9*X(11)<=0
-8+5*X(2)+6*X(3)-12*X(5)+7*X(6)+3*X(8)+X(9)-8*X(10)+5*X(12)<=0
7-7*X(1)-1*X(2)-5*X(3)+3*X(4)+1*X(5)-8*X(6)-2*X(8)+7*X(9)+1*X(10)-7*X(12)<=0
4-2*X(1)-4*X(4)-3*X(7)-5*X(8)-1*X(9)+X(11)+X(12)<=0
X(j)=0, 1
j=1, 2, 3,...,12
This problem is based on Example 4 of Balas [1, pp. 542-544].
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 12
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 12
131 X(K)=A(K)
132 NEXT K
1110 IJU=1+FIX(RND*12)
1111 X(IJU)=FIX(RND*2)
1151 PEN1=6-1*X(1)+3*X(2)-12*X(3)-X(5)+7*X(6)-X(7)+3*X(10)-5*X(11)-1*X(12)
1159 IF PEN1>0 THEN PEN1=PEN1 ELSE PEN1=0
1255 PEN2=-1+3*X(1)-7*X(2)+1*X(4)+6*X(5)
1259 IF PEN2>0 THEN PEN2=PEN2 ELSE PEN2=0
1355 PEN3=4+11*X(1)+X(3)-7*X(4)-1*X(6)+2*X(7)+X(8)-5*X(9)+9*X(11)
1359 IF PEN3>0 THEN PEN3=PEN3 ELSE PEN3=0
1455 PEN4=-8+5*X(2)+6*X(3)-12*X(5)+7*X(6)+3*X(8)+X(9)-8*X(10)+5*X(12)
1459 IF PEN4>0 THEN PEN4=PEN4 ELSE PEN4=0
1462 PEN5=7-7*X(1)-1*X(2)-5*X(3)+3*X(4)+1*X(5)-8*X(6)-2*X(8)+7*X(9)+1*X(10)-7*X(12)
1469 IF PEN5>0 THEN PEN5=PEN5 ELSE PEN5=0
1472 PEN6=4-2*X(1)-4*X(4)-3*X(7)-5*X(8)-1*X(9)+X(11)+X(12)
1479 IF PEN6>0 THEN PEN6=PEN6 ELSE PEN6=0
1488 P=-5*X(1)-1*X(2)-3*X(3)-2*X(4)-6*X(5)-4*X(6)-7*X(7)-2*X(8)-4*X(9)-1*X(10)-1*X(11)-5*X(12)-333333!*(ABS(PEN1)+ABS(PEN2)+ABS(PEN3)+ABS(PEN4)+ABS(PEN5)+ABS(PEN6))
1499 PR=-5*X(1)-1*X(2)-3*X(3)-2*X(4)-6*X(5)-4*X(6)-7*X(7)-2*X(8)-4*X(9)-1*X(10)-1*X(11)-5*X(12)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 12
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-20 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 4 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
0 0 1 1 0
0 1 0 0 1
0 1 -18 -18 -31998
0 1 1 1 1
0 0 1 0 0
0 1 -19 -19 -31993
0 1 1 1 1
0 0 1 0 0
0 1 -19 -19 -31984
0 1 1 1 1
0 0 1 0 0
0 1 -19 -19 -31980
0 0 1 1 0
0 1 0 0 1
0 1 -18 -18 -31976
0 0 1 1 0
0 1 0 0 1
0 1 -18 -18 -31971
0 0 1 1 0
0 0 1 0 1
0 1 -13 -13 -31967
0 0 1 1 0
0 1 0 0 1
0 1 -18 -18 -31960
0 0 1 1 0
0 1 0 0 1
0 1 -18 -18 -31953
0 1 1 1 1
0 0 1 0 0
0 1 -19 -19 -31948
0 1 1 1 1
0 0 1 0 0
0 1 -19 -19 -31943
0 1 1 1 1
0 0 1 0 0
0 1 -19 -19 -31942
0 0 1 1 0
0 0 1 0 1
0 1 -13 -13 -31938
0 0 1 1 0
0 0 1 0 1
0 1 -13 -13 -31937
Interpreted in accordance with line 1912, line 1914, and line 1915, the output through JJJJ=-31937 was produced during the first 4 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
Reference
[1] E. Balas, "An Additive Algorithm for Solving Linear Programs with Zero-One Variables," Operations Research 13, 517-546 (1965).
