Thursday, December 25, 2014

Mixed Integer Nonlinear Programming (MINLP) Solver Applied to a Nonlinear Integer Programming Problem with 10100 General Integer Variables of Lower Bounds of -11s and Upper Bounds of 11s

Jsun Yui Wong

Similar to the computer programs of the preceding papers, the computer program below seeks to solve a problem based on Li and Sun's Problem 14.4, [12, p. 415], but with 10100 unknowns instead of 100 unknowns and with lower bounds of -11s instead of -5s and upper bounds of 11s instead of 5s.  The function is based on the Rosenbrock function--see Schittkowski [16] and Li and Sun [12, p. 415].  Specifically, the test example here is as follows:

Minimize

10100-1
SIGMA    [  100*  ( X(i+1) - X(i)^2  )^2  +  (  1-X(i)   )^2   ]
i=1

subject to

-11<=X(i)<=11, X(i) integer, i=1, 2, 3,..., 10100.

One notes line 111 through line 117 and line 170 through line 173.

The following computer program uses Microsoft's GW-BASIC 3.11 interpreter for DOS.

0 DEFINT J,K,B,X
2 DIM A(10100),X(10100)
81 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-1.5D+38
111 FOR J44=1 TO 10100
114 A(J44)=-11+FIX(RND*23)
117 NEXT J44
128 FOR I=1 TO 32000 STEP .5
129 FOR KKQQ=1 TO 10100
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*.3)
140 B=1+FIX(RND*10100)
167 IF RND<.5 THEN X(B)=A(B)-1   ELSE X(B)=A(B) +1
169 NEXT IPP
170 FOR J44=1 TO 10100
171 IF X(J44)<-11 THEN X(J44 )=A(J44  )
172 IF X(J44)>11 THEN X(J44 )=A(J44  )
173 NEXT J44
200 SUMNEWZ=0
203 FOR J44=1 TO    10099
205 SUMNEWZ=SUMNEWZ+  100*  ( X(J44+1)-X(J44)^2  )^2  +  ( 1-X(J44 ) )  ^2
207 NEXT J44
511 SONE=   - SUMNEWZ
689 PD1=SONE
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 10100
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1559 GOTO 128
1670 NEXT I
1771 PRINT A(1),A(2),A(3),A(4),A(5)
1899 PRINT A(9996),A(9997),A(9998),A(10099),A(10100),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 computer program's complete output through JJJJ=-32000 is shown below:

1   1   1   1   1  
1   1   1   1   1
0         -32000

Above there is no rounding by hand; it is just straight copying by hand from the screen.

M=0 is optimal.  See Li and Sun [12, p. 415].

Of the 10100 A's, only the 10 A's of line 1771 and line 1899  are shown above.

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=-32000 was 13 hours.

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] George B. Dantzig, Discrete-Variable Extrenum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[5] M. A. Duran, I. E. Grossmann, An Outer-Approximation Algorithm for a Class of Mixed-Integer Nonlinear Programs.  Mathematical Programming, 36:307-339, 1986.

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

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

[8] M. Junger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G.   Rinaldi, L. A. Woolsey--Editors, 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art.  Springer, 2010 Edition.  eBook; ISBN 978-3-540-68279-0

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

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

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

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

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

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

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

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

[17] S. Surjanovic, Zakharov Function.  www.sfu.ca/~ssurjano/zakharov.html

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

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

[20] Jsun Yui Wong (2014, June 27).  A Unified Computer Program for Schittkowski's Test Problem 377, Second Edition.  http://nonlinearintegerprogrammingsolver.blogspot.ca/2014_06_01_archive.html