Jsun Yui Wong

The computer program listed below seeks to solve Li and Sun's Problem 14.4 but with 15155 unknowns instead of their 100 unknowns [12, p. 415]. The function is based on the widely known Rosenbrock function--see, for example, Li and Sun [12, p. 415] and Schittkowski [16, Test Problems 294-299]. Specifically, the test example here is as follows:

Minimize

15155-1

SIGMA 100* ( X(i+1) - X(i)^2 )^2 + ( 1-X(i) )^2

i=1

subject to

-5 <= X(i) <= 5, X(i) integer, i=1, 2, 3,..., 15155.

One notes the starting solution vectors of line 111 through line 118, which are as follows:

111 FOR J44=1 TO 15155

116 A(J44)=-5+FIX(RND*11)

118 NEXT J44.

For a computer program involving a mix of continuous variables and integer variables, see Wong [19], for instance.

The following computer program uses the IBM Personal BASIC Compiler--through A:\>bascom and A:\>link--Copyright IBM Corp 1982 Version 1.00/Copyright Microsoft.

0 DEFINT J,K,B,X,A

2 DIM A(15158),X(15158)

81 FOR JJJJ=-32000 TO 32000

85 LB=- FIX(RND*6)

86 UB= FIX(RND*6)

89 RANDOMIZE JJJJ

90 M=-1.5D+38

111 FOR J44=1 TO 15155

116 A(J44)=-5+FIX(RND*11)

118 NEXT J44

128 FOR I=1 TO 32000

129 FOR KQ=1 TO 15155

130 X(KQ)=A(KQ)

131 NEXT KQ

139 FOR IPP=1 TO FIX(1+RND*.3)

140 B=1+FIX(RND*15158)

167 IF RND<.5 THEN X(B)=(A(B)-1) ELSE X(B)=(A(B) +1 )

169 NEXT IPP

171 FOR J9=1 TO 15155

173 IF X(J9)<LB THEN X(J9)=LB

175 IF X(J9)>UB THEN X(J9)=UB

177 NEXT J9

178 REM

207 REM

401 SONE=0

402 FOR J44=1 TO 15154

411 SONE=SONE+ 100* ( X(J44+1) - X(J44)^2 )^2 + ( 1-X(J44) )^2

421 NEXT J44

689 PD1=-SONE

1111 IF PD1<=M THEN 1670

1452 M=PD1

1454 FOR KX=1 TO 15155

1455 A(KX)=X(KX)

1456 NEXT KX

1559 GOTO 128

1670 NEXT I

1773 PRINT A(1),A(15152),A(15153),A(15154),A(15155)

1777 PRINT M,JJJJ

1999 NEXT JJJJ

This BASIC computer program was run with the IBM Personal Computer BASIC Compiler, Version 1.00. See the* BASIC* manual [13, page iii, Preface]. Copied by hand from the screen, the computer program's complete output through JJJJ=-31992 is shown below:

1 1 1 1 1

0 -32000

1 1 1 1 1

0 -31999

0 0 0 0 0

-15154 -31998

0 0 0 0 0

-15154 -31997

-1 1 1 1 1

-4 -31996

1 1 1 1 1

0 -31995

-1 1 1 1 1

-4 -31994

1 1 1 1 1

0 -31993

0 0 0 0 0

-15154 -31992

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 15155 A's, only the 5 A's of line 1773 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 Personal Computer BASIC Compiler, Copyright IBM Corp 1982 Version 1.00/Copyright Microsoft, Inc. 1982, the wall-clock time for obtaining the output through

JJJJ=-31992 was 35 hours.

For a computer program involving a mix of continuous variables and integer variables, see Wong [19], for instance.

**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, July 16). The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables, Sixth Edition, http://myblogsubstance.typepad.com/substance/2013/07/

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

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

## Comments

You can follow this conversation by subscribing to the comment feed for this post.