Similar to the computer program of the preceding paper, the following computer program seeks to solve a problem based on Schittkowski's Problem 287 [11, p. 111]; only integer solutions are of interest in the present paper. Thus, in the present paper the problem is to minimize the following:
5
SIGMA [ 100*(X(i)^2+X(i+5) ) ^2 + ( X(i)- 1 )^2 +90* ( X(i+10)^2
i=1
+X(i+15) )^2 + (X(i+10)-1 )^2+10.1*((X(i+5)-1)^2+(X(i+15)-1)^2)+19.8*(X(i+5)-1)*(X
(i+15)-1) ]
subject to -32000<= X(j)<=32000, X(j) integer, j=1, 2, 3,..., 20. See line 225 and Schittkowski [11, p. 111].
One notes line 112, line 213, and line 214, which are 112 A(J44)=-32000+FIX( RND*64001), 213 IF X(J44)<-32000 THEN X(J44)=A(J44), and 214 IF X(J44)>32000 THEN X(J44)=A(J44), respectively.
0 REM DEFDBL A-Z
1 DEFINT J,K,X,B
2 DIM A(1001),X(1001),T(100)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
110 FOR J44=1 TO 20
112 A(J44)=-32000+FIX( RND*64001!)
114 NEXT J44
128 FOR I=1 TO 32000
129 FOR KKQQ=1 TO 20
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*20)
143 IF RND<.5 THEN 150 ELSE 167
144 REM GOTO 167
150 R=(1-RND*2)*A(B)
155 T(B)=(A(B) +RND^3*R)
158 IF ABS(T(B))>32000 THEN 1670
159 X(B)=T(B)
160 REM 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
212 FOR J44=1 TO 20
213 IF X(J44)<-32000 THEN X(J44)=A(J44)
214 IF X(J44)>32000 THEN X(J44)=A(J44)
215 NEXT J44
220 SUMM=0
222 FOR J44=1 TO 5
225 SUMM=SUMM+100*(X(J44)^2+X(J44+5) ) ^2 + ( X(J44)- 1 )^2 +90* ( X(J44+10)^2+X(J44+15) )^2 + (X(J44+10)-1 )^2+10.1*((X(J44+5)-1)^2+(X(J44+15)-1)^2)+19.8*(X(J44+5)-1)*(X(J44+15)-1)
226 NEXT J44
231 REM SUMN=0
233 REM FOR J45=1 TO 5
236 REM SUMN =SUMN+10.1*( (X(J45+5)-1)^2 +(X(J45+15)-1)^2 )+ 19.8*( X(J45+5) -1 ) *(X(J45+15) -1)
239 REM NEXT J45
244 REM SUMS=SUMM
444 PD1=-SUMM
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 20
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 1557
1544 IF M<-8 THEN 1557
1546 PRINT I,A(30),M,JJJJ
1557 GOTO 128
1670 NEXT I
1889 IF M<-999 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),A(13),A(14),A(15)
1907 PRINT A(16),A(17),A(18),A(19),A(20)
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. See [8]. Copied by hand from the screen, the complete output through JJJJ=-31990 is as follows:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -32000
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -31999
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -31998
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -31997
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -31996
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -31995
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -31994
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -31993
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -31992
-2 0 0 0 0
-4 0 0 0 0
0 0 0 0 0
1 0 0 0 0
-520.5 -31991
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-210 -31990
Immediately above there is no rounding by hand.
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=-31990 was two minutes 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] F. Cajori (1911) Historical Note on the Newton-Raphson Method of Approximation. The American Mathematical Monthly , Volume 18 #2, pp. 29-32.
[4] Jack Lashover (November 12, 2012). Monte Carlo Marching. www.academia.edu/5481312/MONTE_ CARLO_MARCHING
[5] 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.
[6] 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.
[7] Duan Li, Xiaoling Sun, Nonlinear Integer Programming. Publisher: Springer Science+Business Media,LLC (2006). http://www.books.google.ca/books?isbn=0387329951
[8] 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.
[9] Harvey M. Salkin, Integer Programming. Menlo Park, California: Addison-Wesley Publishing Company (1975).
[10] Harvey M. Salkin, Kamlesh Mathur, Foundations of Integer Programming. Publisher: Elsevier Science Ltd (1989).
[11] K. Schittkowski, More Test Examples for Nonlinear Programming Codes. Springer-Verlag, 1987.
[12] 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/
[13] 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/
