Saturday, June 7, 2014

A Unifying Algorithm for Nonlinear Integer/Continuous/Discrete Programming

Jsun Yui Wong

Case One: All Integer Variables

Similar to the computer program of the preceding paper, the first of the two computer programs below seeks to solve a problem based on Schittkowski's Problem 303 [13, p. 127].  Here only integer solutions are of interest.  Thus, in the present paper the first problem is to minimize the following:

20                               20                                                      20    
SIGMA  X(i)^2  +   [  SIGMA  (1/2) * i *X(i)^2  ] ^2  +   [  SIGMA  (1/2) *  i *X(i)^2  ] ^4
i=1                              i=1                                                      i=1

subject to -5000<= X(j)<=5000, X(j) integer, j=1, 2, 3,..., 20.  See Schittkowski [13, p. 127].

One notes line 1, which is 1 DEFINT J,K,B,X.  

0 REM  DEFDBL A-Z
1 DEFINT J,K,B,X
2 DIM A(1001),X(1001)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
110 FOR J44=1 TO 20
112 A(J44)=-5000+FIX(  RND*10001!)
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)
144 GOTO 167
145 IF RND<.5 THEN         150 ELSE 167
150 R=(1-RND*2)*A(B)
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
212 FOR J44=1 TO 20
213 IF X(J44)<-5000 THEN X(J44)=A(J44)
214 IF X(J44)>5000 THEN X(J44)=A(J44)
215 NEXT J44
301 SONE=0
303 FOR J44=1 TO 20
305 SONE=SONE+X(J44)^2
309 NEXT J44
311 SONEONE=SONE
321 STWO=0
323 FOR J44=1 TO 20
325 STWO=STWO+(1/2)*J44*X(J44)
329 NEXT J44
331 STWOTWO=  ( STWO)^2
341 STHR=0
343 FOR J44=1 TO 20
345 STHR=STHR+(1/2)*J44*X(J44)
349 NEXT J44
351 STHRTHR=  ( STHR)^4
447 PD1=-SONEONE-STWOTWO-STHRTHR
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 20
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 REM   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 [10].  Copied by hand from the screen, the complete output through JJJJ=-31998 is as follows:

0   0   0   0   0
0   0   0   0   0
0   0   0   0   0
0   0   0   0   0
0   -32000

0   0   0   0   0
0   0   0   0   0
0   0   0   0   0
0   0   0   0   0
0   -31999

0   0   0   0   0
0   0   0   0   0
0   0   0   0   0
0   0   0   0   0
0   -31998  

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=-31998 was two minutes and ten seconds.

Case Two: All Continuous Variables
.
Similar to the computer program above, the following computer program seeks to solve Hock and Schittkowski's Problem 110 [5, p. 110]; the source of this problem is Himmelblau [4, Problem 17, p. 416].  The problem is to minimize the following:

10                                                                                             10
SIGMA   [   ( LOG ( X(i)-2) )^2  +(  LOG (10-X(i)  )  )^2 ]  -[ PI  X(i)   ]^.2
i=1                                                                                             i=1      

subject to 2.001  <=   X(i)   <= 9.999, i=1,..., 10.   See Himmelblau [4, p. 416] and Hock and Schittkowski [5, p. 110].

One notes that while line 1 above is 1 DEFINT J,K,B,X, line 1 below is  
1 DEFINT J,K,B.

0 REM  DEFDBL A-Z
1 DEFINT J,K,B
2 DIM A(1001),X(1001)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
110 FOR J44=1 TO 10
111 A(J44)=2.001+(  RND*7.998)
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<.5 THEN         150 ELSE 167
150 R=(1-RND*2)*A(B)
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
202 FOR J44=1 TO 10
213 IF X(J44)<2.001 THEN X(J44)=A(J44)
214 IF X(J44)>9.998999 THEN X(J44)=A(J44)
215 NEXT J44
217 GOTO 301
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
301 SONE=0
303 FOR J44=1 TO 10
306 IF ( X(J44)-2)<.0001   THEN 1670
307 IF  (10-X(J44)  ) <.0001 THEN 1670
308 SONE=SONE+ ( LOG ( X(J44)-2) )^2  +(  LOG (10-X(J44)  )  )^2
309 NEXT J44
371 PROD=1
373 FOR J44=1 TO 10
375 PROD=PROD*X(J44)
379 NEXT J44
381 PRODPROD=PROD^.2
444 REM   PD1=-SUMM
447 PD1=-SONE+PRODPROD
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 REM   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)
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 [10].  Copied by hand from the screen, the complete output through JJJJ=-31998 is as follows:

9.350314   9.351601   9.351381   9.350377   9.350853
9.348362   9.350105   9.350344   9.351095   9.350406
45.77849   -32000

9.349132   9.350902   9.352669   9.348278   9.348939
9.348385   9.35071   9.352462   9.351089   9.349948
45.77846   -31999

9.35129   9.351302   9.35021   9.349292   9.350794
9.350446   9.348862   9.351012   9.348884   9.350422
45.7785   -31998

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=-31998 was 32 seconds.

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 MonthlyThe American , Volume 18 #2, pp. 29-32.

[4] D. M. Himmelblau, Applied Nonlinear Programming.  New York: McGraw-Hill Book Company, 1972.

[5] W. Hock, K. Schittkowski, Test Examples for Nonlinear Programming Codes.  Springer-Verlag, 1981.

[6] Jack Lashover (November 12, 2012).  Monte Carlo Marching.  www.academia.edu/5481312/MONTE_ CARLO_MARCHING

[7] 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.

[8] 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.

[9] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Publisher: Springer Science+Business Media,LLC (2006).  http://www.books.google.ca/books?isbn=0387329951

[10] 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.

[11] Harvey M. Salkin, Integer Programming.  Menlo Park, California: Addison-Wesley Publishing Company (1975).

[12] Harvey M. Salkin, Kamlesh Mathur, Foundations of Integer Programming.  Publisher: Elsevier Science Ltd (1989).

[13] K. Schittkowski, More Test Examples for Nonlinear Programming Codes.  Springer-Verlag, 1987.

[14] 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/

[15] 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/