Jsun Yui Wong
Similar to the computer program in Wong [6], the following computer program seeks to solve Problem 2 in Lawler and Bell [2]. For complete problem details see Lawler and Bell [2 and 3]. This problem is considered by Salkin and Mathur [5, p. 338], 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 7
112 A(J44)=+FIX( RND*7)
113 NEXT J44
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 7
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*7)
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 IF RND<.5 THEN X(B)=CINT(A(B)-1) ELSE X(B)=CINT(A(B) +1)
168 NEXT IPP
212 FOR J44=1 TO 7
213 IF X(J44)<0 THEN X(J44)=0
217 NEXT J44
219 IF X(4)>15 THEN X(4)=15
220 IF X(5)>15 THEN X(5)=15
221 IF X(1)>7 THEN X(1)=7
222 IF X(2)>7 THEN X(2)=7
223 IF X(3)>7 THEN X(3)=7
226 IF X(6)>7 THEN X(6)=7
231 X(8)= X(1) + X(2) +X(3)-6
234 X(9)= -3*X(1) -2*X(3) -X(5)+7
238 X(10)= -3*X(1)*X(3)-6*X(4)-4 *X(5) +20
242 X(11)= X(4) + X(5) + 6* X(6)-8
246 X(12)= 3*X(4)* X(5) + 4*X(2)*X(7)-25
249 X(13)= X(1)*X(6) +X(2) +3*X(5) -7
251 X(14)=-4*X(1)-2*X(3) -X(6)*X(7) +15
261 FOR J44=8 TO 14
263 IF X(J44)<0# THEN X(J44)=X(J44) ELSE X(J44)=0#
265 NEXT J44
311 SUMM=10000*(X(8)+X(9)+X(10)+X(11)+X(12)+X(13)+X(14) )
322 PD1= -X(1)*X(7) -3#*X(2)*X(6) -X(3)*X(5)- 7#*X(4) +SUMM
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 14
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-18 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4)
1905 PRINT A(5),A(6),A(7)
1917 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 4 2 0
2 1 4
-16 -32000
0 4 2 0
2 1 3
-16 -31999
0 6 0 0
3 1 7
-18 -31998
0 4 2 0
2 1 2
-16 -31997
1 4 1 0
2 1 2
-16 -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, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.
[2] 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.
[3] 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.
[4] Harvey M. Salkin, Integer Programming. Menlo Park, California: Addison-Wesley Publishing Company (1975).
[5] Harvey M. Salkin, Kamlesh Mathur, Foundations of Integer Programming. Publisher: Elsevier Science Ltd (1989).
[6] 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/
[7] 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