Jsun Yui Wong
Similar to the computer programs of the preceding papers, the computer program below seeks to solve Schittkowski's Test Problem 377 [14, p. 196]. The source of this Test Problem 377 is S. Walukiewicz; see Schittkowski [14]. The problem is to minimize the following:
10
SIGMA X(i) * ( C(i) +LOG( X(i)/SONE ) )
i=1
10
where SONE= SIGMA X(j)
j=1
C(1) through C(10) are given in line 11 and line 13
subject to
X(1) - 2*X(2) + 2* X(3) + X(6) + X(10) - 2 =0
X(4) - 2* X(5) + X(6) + X(7) - 1 =0
X(3) + X(7) + X(8) +2* X(9) + X(10) - 1 =0
0.1E-04<= X(i)<=10, i=1 , 2 , 3,..., 10.
The computer program's arrangement of line 380, line 381, and line 383 is to induce domino effect.
While line 163 of the preceding paper is 163 IF RND<.5 THEN X(B)=(A(B)-.001) ELSE X(B)=(A(B) +.001 ), here line 163 is 163 IF RND<.5 THEN X(B)=(A(B)-.0001) ELSE X(B)=(A(B) +.0001 ).
0 REM DEFDBL A-Z
1 DEFINT J,K,B
2 DIM A(1001),X(1001)
11 C(1)=-6.089 :C(2)=- 17.164 :C(3)=- 34.054:C(4)=- 5.914 :C(5)=- 24.721
13 C(6)=-14.986 :C(7)=- 24.1 :C(8)=- 10.708:C(9)=-26.662 :C(10)=- 22.179
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-1.5D+38
110 FOR J44=1 TO 10
113 A(J44)= RND*(.1)
114 NEXT J44
128 FOR I=1 TO 32000
129 FOR KKQQ=1 TO 10
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*10)
144 REM GOTO 167
145 IF RND<.33 THEN 150 ELSE IF RND<.5 THEN 163 ELSE 167
150 R=(1-RND*2)*A(B)
160 X(B)=(A(B) +RND^3*R)
162 GOTO 168
163 IF RND<.5 THEN X(B)=(A(B)-.0001) ELSE X(B)=(A(B) +.0001 )
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
370 FOR J44=1 TO 10
371 IF X(J44)<.00001 THEN 1670
372 IF X(J44)>10 THEN 1670
375 NEXT J44
380 X(7)= -X(4) +2* X(5) - X(6) + 1
381 X(10)= -X(3) - X(7) - X(8) -2* X(9) + 1
383 X(1)=2*X(2) -2* X(3) - X(6) - X(10) + 2
396 FOR J44=1 TO 10
397 IF X(J44)<.00001 THEN 1670
398 IF X(J44)>10 THEN 1670
399 NEXT J44
400 SONE=0
401 FOR J44=1 TO 10
403 SONE=SONE+X(J44)
405 NEXT J44
410 STWO=0
411 FOR J44=1 TO 10
412 IF ( X(J44)/SONE ) < 1E-11 THEN 1670
413 STWO=STWO+X(J44) * ( C(J44) +LOG( X(J44)/SONE ) )
415 NEXT J44
455 PD1= - STWO
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 10
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-999999! THEN 1999
1923 PRINT A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(8),A(9),A(10)
1929 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 the BASIC manual [11]. Copied by hand from the screen, the complete output through
JJJJ=-31996 is shown below:
9.999998 9.981577 .9815478 9.999987 9.50916
9.999988 1.834583E-02 1.3025E-05 1.106528E-05
7.116795E-03
794.8063 -32000
10 9.983363 .9833495 10 9.508292
9.999997 1.658726E-02 1.141463E-05
1.10852E-05 2.962351E-05
794.8277 -31999
10 9.988516 .9884736 10 9.505688
9.999984 1.139164E-02 1.299235E-05
1.094947E-05 9.983778E-05
794.885 -31998
10 9.987944 .987878 9.999989 9.505974
9.999999 1.195908E-02 1.069538E-05
1.000319E-05 1.322031E-04
794.8788 -31997
9.999996 9.989264 .9892115 9.999985 9.505311
9.999993 1.064396E-02 1.05749E-05 1.007373E-05
1.138449E-04
794.8931 -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 thirty-one minutes.
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] M. A. Duran, I. E. Grossmann, An Outer-Approximation Algorithm for a Class of Mixed-Integer Nonlinear Programs. Mathematical Programming, 36:307-339, 1986.
[5] D. M. Himmelblau, Applied Nonlinear Programming. New York: McGraw-Hill Book Company, 1972.
[6] W. Hock, K. Schittkowski, Test Examples for Nonlinear Programming Codes. Springer-Verlag, 1981.
[7] Jack Lashover (November 12, 2012). Monte Carlo Marching. www.academia.edu/5481312/MONTE_ CARLO_MARCHING
[8] 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.
[9] 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.
[10] Duan Li, Xiaoling Sun, Nonlinear Integer Programming. Publisher: Springer Science+Business Media,LLC (2006). http://www.books.google.ca/books?isbn=0387329951
[11] 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.
[12] Harvey M. Salkin, Integer Programming. Menlo Park, California: Addison-Wesley Publishing Company (1975).
[13] Harvey M. Salkin, Kamlesh Mathur, Foundations of Integer Programming. Publisher: Elsevier Science Ltd (1989).
[14] K. Schittkowski, More Test Examples for Nonlinear Programming Codes. Springer-Verlag, 1987.
[15] S. Surjanovic, Zakharov Function. www.sfu.ca/~ssurjano/zakharov.html
[16] 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/
[17] 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/
