Jsun Yui Wong
Similar to the computer program of the preceding paper, the following computer program seeks to solve Li and Sun’s Problem 14.5, [5, p. 416], but with n=250 unknowns and -1000<=X(i)<=+1000, as shown in line 112, line 183, and line 184.
0 REM DEFDBL A-Z
1 DEFINT 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 250
112 A(J44)=-1000+FIX( RND*2001)
113 NEXT J44
128 FOR I=1 TO 32000 STEP .5
129 FOR KKQQ=1 TO 250
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*251)
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 REM IF A(B)=0 THEN X(B)=1 ELSE X(B)=0
169 NEXT IPP
182 FOR J44=1 TO 250
183 IF X(J44)<-1000 THEN X(J44)=A(J44)
184 IF X(J44)>1000 THEN X(J44)=A(J44)
185 NEXT J44
209 SUM1=0
210 FOR J44=1 TO 250
212 SUM1=SUM1+X(J44)^4#
213 NEXT J44
215 SUM2=0
216 FOR J44=1 TO 250
217 SUM2=SUM2 + X(J44)
218 NEXT J44
219 SUMT=SUM1+(SUM2)^2#
333 PD1=-SUMT
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 250
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1669 GOTO 128
1670 NEXT I
1889 IF M<-5 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4),A(5)
1927 PRINT A(248),A(249),A(250),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run via basica/D of Microsoft’s GW-BASIC 3.11 interpreter for DOS. See [6]. The complete output through JJJJ=-31992 is copied by hand from the screen and shown below. Immediately below there is no rounding by hand.
0 0 0 0 0
0 0 0 -4 -31999
0 0 0 0 0
0 0 0 -4 -31998
0 0 0 0 0
0 0 0 -4 -31995
0 0 1 0 0
0 0 0 -4 -31994
0 0 0 0 0
0 0 0 0 -31993
0 0 0 0 0
0 0 0 -2 -31992
Only eight of the 250 A’s are shown above. The printout is limited by the computer program–the printing shown above came from line 1904 and line 1927.
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=-31992 was two hours and a half.
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] Duan Li, Xiaoling Sun, Nonlinear Integer Programming. Publisher: Springer Science+Business Media,LLC (2006). http://www.books.google.ca/books?isbn=0387329951
[6] Microsoft Corp., BASIC, Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C,Boca Raton, Floridda 33432, 1981.
[7] Harvey M. Salkin, Integer Programming. Menlo Park, California: Addison-Wesley Publishing Company (1975).
[8] Harvey M. Salkin, Kamlesh Mathur, Foundations of Integer Programming. Publisher: Elsevier Science Ltd (1989).
[9] K. Schittkowski, More Test Examples for Nonlinear Programming Codes. Springer-Verlag, 1987.
[10] 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/
[11] 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/
computerprogramsandresults 