Jsun Yui Wong
Similar to the computer program in Wong [8], the following computer program seeks to solve Example 4 in Balas [1, pp. 542-544]. For complete problem details see Balas [1, p. 542]. This example is considered by Salkin and Mathur [6, Problem 9.25, p. 333], as well.
0 REM DEFDBL A-Z
1 DEFINT I,J,K,X
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),PLHS(44),LB(22),UB(22),PX(44),J44(44),PN(22),NN(22)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
110 FOR J44=1 TO 12
112 A(J44)=+FIX( RND*2)
113 NEXT J44
128 FOR I=1 TO 100
129 FOR KKQQ=1 TO 12
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*12)
144 GOTO 167
150 R=(1-RND*2)*A(B)
155 IF RND<.5 THEN 160 ELSE 167
160 X(B)=(A(B) +RND^3*R)
165 GOTO 168
167 REM IF RND<.5 THEN X(B)=CINT(A(B)-1) ELSE X(B)=CINT(A(B) +1)
168 IF A(B)=0 THEN X(B)=1 ELSE X(B)=0
169 NEXT IPP
212 FOR J44=1 TO 12
213 IF X(J44)<0 THEN X(J44)=0
214 IF X(J44)>1 THEN X(J(44)=1
217 NEXT J44
231 X(13)=-1*( -1*X(1)+ 3*X(2)- 12*X(3)- 0*X(4)- 1*X(5)+ 7*X(6)- 1*X(7)- 0*X(8)- 0*X(9)+ 3*X(10)- 5*X(11)- 1*X(12)+6 )
235 X(14)=-1*( +3*X(1)- 7*X(2)+ 0*X(3)+ 1*X(4)+ 6*X(5)+ 0*X(6)+ 0*X(7)- 0*X(8)- 0*X(9)+ 0*X(10)+ 0*X(11)+ 0*X(12)-1 )
239 X(15)=-1*( +11*X(1)+ 0*X(2)+ 1*X(3)- 7*X(4)- 0*X(5)- 1*X(6)+ 2*X(7)+ 1*X(8)- 5*X(9)- 0*X(10)+ 9*X(11)- 0*X(12)+4 )
242 X(16)=-1*( +0*X(1)+ 5*X(2)+ 6*X(3)- 0*X(4)- 12*X(5)+ 7*X(6)- 0*X(7)+ 3*X(8)+ 1*X(9)- 8*X(10)+ 0*X(11)+ 5*X(12)-8 )
245 X(17)=-1*( -7*X(1)- 1*X(2)- 5*X(3)+ 3*X(4)+1 *X(5)- 8*X(6)- 0*X(7)- 2*X(8)+ 7*X(9)+ 1*X(10)+ 0*X(11)- 7*X(12)+7 )
247 X(18)=-1*( -2*X(1)+ 0*X(2)+ 0*X(3)- 4*X(4)- 0*X(5)- 0*X(6)- 3*X(7)- 5*X(8)- 1*X(9)- 0*X(10)+ 1*X(11)+ 1*X(12)+4 )
261 FOR J44=13 TO 18
263 IF X(J44)<0# THEN X(J44)=X(J44) ELSE X(J44)=0#
265 NEXT J44
277 SUMM=10000*(X(13)+X(14)+X(15) +X(16)+X(17)+X(18) )
325 PD1= -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)+SUMM
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 18
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-20 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4),A(5)
1905 PRINT A(6),A(7),A(8),A(9),A(10)
1906 PRINT A(11),A(12)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS. The complete output through JJJJ=-31996 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
0 0 1 1 0
0 0 1 0 1
0 1
-13 -32000
0 0 1 1 0
0 1 0 0 1
0 1
-18 -31999
0 0 1 1 0
0 0 1 0 1
0 1
-13 -31997
0 0 1 1 0
0 0 1 0 1
0 1
-13 -31996
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11, the wall-clock time for obtaining the output through JJJJ=-31996 was one second.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] E. Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, No. 4 (1965), pp. 517-548.
[2] E. Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.
[3] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems. Operations Research, Vol. 14, No. 6 (Nov. - Dec., 1966), pp. 1098-1112.
[4] E. L. Lawler, M. D. Bell, Errata: A Method for Solving Discrete Optimization Problems. Operations Research, Vol. 15, No. 3 (May - June, 1967), p. 578.
[5] Harvey M. Salkin, Integer Programming. Menlo Park, California: Addison-Wesley Publishing Company (1975).
[6] Harvey M. Salkin, Kamlesh Mathur, Foundations of Integer Programming. Publisher: Elsevier Science Ltd (1989).
[7] Jsun Yui Wong (2012, April 23). The Domino Method of General Integer Nonlinear Programming Applied to Problem 2 of Lawler and Bell. http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/23/
[8] Jsun Yui Wong (2013, September 4). A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Literature Problem with Twenty Binary Variables and Three Constraints, Third Edition. http://myblogsubstance.typepad.com/substance/2013/09/
Comments
You can follow this conversation by subscribing to the comment feed for this post.