Jsun Yui Wong
The problem here is based on Li and Sun’s Problem 14.3 [12, 414-415], which is based on Walukiewicz/Schittkowski [16, Test Problem 282, page 106 and page 23]. Specifically, the test example here is to minimize
22120-1
(X(1)-1)^2 + ( X(22120)-1)^2 + 22120* SIGMA (22120-i)* ( X(i)^2-X(i+1) )^2
i=1
subject to
X(1)^3 + X(2)^3 + X(3)^3 + … + X(22120)^3 = 22120
-5 <= X(i) <= 5, X(i) integer, i=1, 2, 3,…, 22120.
The equality constraint above is presently added.
One notes the starting solution vectors of line 111 through line 117, which are as follows:
111 FOR J44 = 1 TO 22120
114 A(J44) = -5 + FIX(RND * 11)
117 NEXT J44.
The following computer program uses QB64 [18, 19].
0 DEFINT J, K, B, X, A
2 DIM A(33123), X(33123)
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 22120
114 A(J44) = -5 + FIX(RND * 11)
117 NEXT J44
128 FOR I = 1 TO 32000
129 FOR KKQQ = 1 TO 22120
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
139 FOR IPP = 1 TO FIX(1 + RND * .3)
140 B = 1 + FIX(RND * 22123)
167 IF RND < .5 THEN X(B) = (A(B) – 1) ELSE X(B) = (A(B) + 1)
169 NEXT IPP
170 FOR J44 = 1 TO 22120
171 IF X(J44) < LB THEN X(J44) = LB
172 IF X(J44) > UB THEN X(J44) = UB
173 NEXT J44
221 SFE = 0
225 FOR J44 = 1 TO 22120
228 SFE = SFE + X(J44) ^ 3
233 NEXT J44
251 TSL = -22120 + SFE
257 REM IF TSL<0 THEN TSL=TSL ELSE TSL=0
267 IF TSL = 0 THEN TSL = TSL ELSE TSL = -ABS(TSL)
400 SZ = 0
403 FOR J44 = 1 TO 22119
405 SZ = SZ + (22120 – J44) * (X(J44) ^ 2 – X(J44 + 1)) ^ 2
407 NEXT J44
411 SONE = -(X(1) – 1) ^ 2 – (X(22120) – 1) ^ 2 – 22120 * SZ
492 PD1 = SONE + 5000000000# * TSL
1111 IF PD1 <= M THEN 1670
1452 M = PD1
1454 FOR KLX = 1 TO 22120
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1559 GOTO 128
1670 NEXT I
1778 PRINT A(1), A(2), A(22118), A(22119), A(22120), M, JJJJ
1999 NEXT JJJJ
Based on the computer program in Wong [24], this BASIC computer program was run with QB64 [18, 19]. Copied by hand from the screen, the computer program’s complete output through JJJJ=-31967 is shown below:
-2 3 0 -1 -3
-3.270111E+14 -32000
0 0 0 0 0
-1.106998E+14 -31999
-1 2 2 0 2
-1.145444E+14 -31998
2 1 2 -4 2
-9.9405E+13 -31997
0 0 0 0 0
-1.106053E+14 -31996
0 0 0 0 0
-1.106484E+14 -31995
0 0 0 0 0
-1.106E+14 -31994
-2 -5 -2 0 3
-3.834372E+14 -31993
0 0 0 0 0
-1.106055E+14 -31992
-3 -2 -2 -2 -1
-4.581762E+14 -31991
0 0 0 0 0
-1.106E+14 -31990
-1 -1 0 0 -1
-3.29308E+13 -31989
0 0 0 0 0
-1.106E+14 -31988
-2 5 4 -1 -2
-1.844149E+14 -31987
2 -1 2 -2 0
-9.990742E+13 -31986
1 1 1 1 1
-1.655205E+10 -31985
1 1 1 1 1
-1.017886E+10 -31984
0 0 0 0 0
-1.106165E+14 -31983
0 0 0 0 0
-1.106E+14 -31982
2 2 0 2 -3
-8.414546E+13 -31981
1 1 1 1 1
-5.645041E+09 -31980
1 1 1 1 1
-5.033556E+09 -31979
0 -3 -3 1 -3
-2.652683E+14 -31978
-1 -1 -1 1 -1
-3.282038E+13 -31977
0 0 0 0 0
-1.106054E+14 -31976
1 1 1 1 1
-5.687512E+09 -31975
0 0 1 1 0
-1.266092E+13 -31974
-4 -4 1 3 3
-3.729486E+14 -31973
2 2 1 -1 0
-6.559005E+13 -31972
2 1 -2 2 2
-1.006949E+14 -31971
0 -1 -1 -3 4
-7.753536E+14 -31970
1 3 3 -1 2
-3.800816E+14 -31969
-2 -2 -1 2 2
-1.001469E+14 -31968
1 1 1 1 1
0 -31967
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, pp. 414-415].
Of the 22120 A’s, only the 5 A’s of line 1778 are shown above.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with QB64 [18, 19], the wall-clock time for obtaining the output through JJJJ=-31967 was 26 hours.
For a computer program involving a mix of continuous variables and integer variables, see Wong [21], 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. http://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. http://www.sfu.ca/~ssurjano/zakharov.html
[18] E.K. Virtanen (2008-05-26). “Interview With Galleon”,
http://www.basicprogramming.org/pcopy/issue70/#galleoninterview
[19] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[20] 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/
[21] 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/
[22] 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/
[23] 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
[24] Jsun Yui Wong (2015, March 11). Nonconvex Mixed-Integer Nonlinear Programming (MINLP) Computer Program Applied to a Problwm with 15120 General Integer Variables and with X(1)^9 + X(2)^9 + X(3)^9 + … + X(15120)^9 = 15120. http://myblogsubstance.typepad.com/substance/2015/03/
computerprogramsandresults 