Jsun Yui Wong
The problem here is Li and Sun's Problem 14.3 but with 15100 unknowns instead of their 100 unknowns; see Li and Sun [12, pp. 414-415]. Their problem is based on Walukiewicz/Schittkowski [16, Test Problem 282, page 106 and page 23]. Specifically, the test example here is to minimize
15100-1
(X(1)-1)^2 + ( X(15100)-1)^2 + 15100* SIGMA (15100-i)* ( X(i)^2-X(i+1) )^2
i=1
subject to
-5 <= X(i) <= 5, X(i) integer, i=1, 2, 3,..., 15100.
One notes that the problem above is equivalent to minimize
15100-1
(X(1)-1)^2 + ( X(15100)-1)^2 + 15100* SIGMA (15100-i)* ( X(i)^2-X(i+1) )^2
i=1
subject to
X(1)^7 + X(2)^7 + X(3)^7 + ... + X(15100)^7 >= 15100
-5 <= X(i) <= 5, X(i) integer, i=1, 2, 3,..., 15100
and to minimize
15100-1
(X(1)-1)^2 + ( X(15100)-1)^2 + 15100* SIGMA (15100-i)* ( X(i)^2-X(i+1) )^2
i=1
subject to
X(1)^7 + X(2)^7 + X(3)^7 + ... + X(15100)^7 <= 15100
-5 <= X(i) <= 5, X(i) integer, i=1, 2, 3,..., 15100.
Then one takes the best produced.
Generally speaking, while dealing with a given problem directly is advantageous if the given problem is "small," dealing with a given problem with an additional constraint--twice--is advantageous if the given problem is "large" because the two problems each with a smaller search region are easier.
(1) The Additional Constraint Used Immediately Below Is X(1)^7 + X(2)^7 + X(3)^7 + ... + X(15100)^7 >= 15100
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(15103),X(15103)
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 15100
114 A(J44)=-5+FIX(RND*11)
117 NEXT J44
128 FOR I=1 TO 32000
129 FOR KKQQ=1 TO 15100
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*.3)
140 B=1+FIX(RND*15103)
167 IF RND<.5 THEN X(B)=(A(B)-1) ELSE X(B)=(A(B) +1 )
169 NEXT IPP
170 FOR J44=1 TO 15100
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 15100
228 SFE=SFE+X(J44)^7
233 NEXT J44
251 TSL=-15100+SFE
257 IF TSL<0 THEN TSL=TSL ELSE TSL=0
400 SUMNEWZ=0
403 FOR J44=1 TO 15099
405 SUMNEWZ=SUMNEWZ+ (15100-J44)* ( X(J44)^2-X(J44+1) )^2
407 NEXT J44
411 SONE= - (X(1)-1)^2 - ( X(15100)-1)^2 -15100* SUMNEWZ
492 PD1=SONE +5000000000#*TSL
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 15100
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1559 GOTO 128
1670 NEXT I
1778 PRINT A(1),A(2),A(15098),A(15099),A(15100),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=-31998 is shown below:
1 1 1 1 1
-1.028267E+10 -32000
1 1 0 0 1
-4.944112E+11 -31999
1 1 1 1 1
0 -31998
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 15100 A's, only the 5 A's of of 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 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=-31998 was 13 hours.
(2) The Additional Constraint Used Below Is X(1)^7 + X(2)^7 + X(3)^7 + ... + X(15100)^7 <= 15100
While line 251 above is 251 TSL=-15100+SFE, line 251 below is 251 TSL= 15100-SFE.
The following computer program also 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(15103),X(15103)
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 15100
114 A(J44)=-5+FIX(RND*11)
117 NEXT J44
128 FOR I=1 TO 32000
129 FOR KKQQ=1 TO 15100
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*.3)
140 B=1+FIX(RND*15103)
167 IF RND<.5 THEN X(B)=(A(B)-1) ELSE X(B)=(A(B) +1 )
169 NEXT IPP
170 FOR J44=1 TO 15100
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 15100
228 SFE=SFE+X(J44)^7
233 NEXT J44
251 TSL= 15100-SFE
257 IF TSL<0 THEN TSL=TSL ELSE TSL=0
400 SUMNEWZ=0
403 FOR J44=1 TO 15099
405 SUMNEWZ=SUMNEWZ+ (15100-J44)* ( X(J44)^2-X(J44+1) )^2
407 NEXT J44
411 SONE= - (X(1)-1)^2 - ( X(15100)-1)^2 -15100* SUMNEWZ
492 PD1=SONE +5000000000#*TSL
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 15100
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1559 GOTO 128
1670 NEXT I
1778 PRINT A(1),A(2),A(15098),A(15099),A(15100),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=-31996 is shown below:
0 0 1 1 0
-4.28105E+11 -32000
0 0 0 0 0
-2 -31999
-1 1 0 0 1
-4.853535E+11 -31998
0 -1 -1 2 3
-3.763683E+11 -31997
0 -1 0 0 -1
-5.508909E+11 -31996
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 15100 A's, only the 5 A's of of 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 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=-31996 was 23 hours.
(3) The realized solution with M=0 at JJJJ=-31998 and produced through the additional constraint X(1)^7 + X(2)^7 + X(3)^7 + ... + X(15100)^7 >= 15100 is the best produced.
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