Jsun Yui Wong
Similar to the computer programs of the preceding papers, the computer program below seeks to solve Li and Sun's Problem 14.3, [11, p. 414], but with 10000 unknowns instead of 100 unknowns and with five added equality constraints and two less-than-or-equal-to constraints. The original version of this problem is due to S. Walukiewicz--see Schittkowski's Test Problem 282 [15, p. 106]. Specifically, the computer program below tries to solve the following:
Minimize
10000-1
(X(1)-1)^2+ ( X(10000)-1)^2 +10000* SIGMA (10000-i)* ( X(i)^2-X(i+1) )^2
i=1
subject to
9*X(61) + 7 *X(77)^3 < = 16
X(52) + 2*X(59 ) + 3*X(99) =6
X(1)+ 3* X(2)+ X(3 ) + 6 *X(4 )+ X(5) = 12
X(5996)+ X(5997)+ 5* X(5998 )+ X(5999) + 3* X(8000) = 11
X(6)^5 + 4 *X(7)^5 +X(8 )^5 +X(9)^5 +X(10)^5 = 8
X(1)^3+X(2)^3+X(3)^3+...+X(10000)^3 = 10000
X(1)+X(2)+X(3)+...+X(10000) < = 10000
-5<=X(i)<=5, X(i) integer, i=1, 2, 3,..., 10000.
One notes line 175 through line 181, which are as follows:
175 S=16 -9*X(61) -7*X(77)^3
176 IF S<0 THEN S=S ELSE S=0
177 X(52)=6-2*X(59 )-3*X(99)
178 X(1)=12-3*X(2)-X(3 )-6*X(4 )-X(5)
179 X(5996)=11-X(5997)-5*X(5998 )-X(5999)-3*X(8000)
180 IF (8-4*X(7)^5 -X(8 )^5 -X(9)^5 -X(10)^5 )<0 THEN 1670
181 X(6)=(8-4*X(7)^5 -X(8 )^5 -X(9)^5 -X(10)^5 )^(1/5)
The following computer program uses the IBM Personal Computer BASIC Compiler--through A:\>bascom and A:\>link--Copyright IBM Corp 1982 Version 1.00/Copyright Microsoft.
0 DEFINT J,K,B,X
2 DIM A(10001),X(10001)
81 FOR JJJJ=-32000 TO 32000
85 UB=1+FIX(RND*5)
89 RANDOMIZE JJJJ
90 M=-1.5D+38
111 FOR J44=1 TO 10000
114 IF RND<.5 THEN A(J44)=1 ELSE A(J44)=0
117 NEXT J44
128 FOR I=1 TO 32000
129 FOR KKQQ=1 TO 10000
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*10000)
167 IF RND<.5 THEN X(B)=CINT(A(B)-1) ELSE X(B)=CINT(A(B) +1 )
169 NEXT IPP
170 FOR J44=1 TO 10000
171 IF X(J44)>UB THEN X(J44 )=A(J44 )
172 IF X(J44)<-5 THEN X(J44 )=A(J44 )
173 NEXT J44
175 S=16 -9*X(61) -7*X(77)^3
176 IF S<0 THEN S=S ELSE S=0
177 X(52)=6-2*X(59 )-3*X(99)
178 X(1)=12-3*X(2)-X(3 )-6*X(4 )-X(5)
179 X(5996)=11-X(5997)-5*X(5998 )-X(5999)-3*X(8000)
180 IF (8-4*X(7)^5 -X(8 )^5 -X(9)^5 -X(10)^5 )<0 THEN 1670
181 X(6)=(8-4*X(7)^5 -X(8 )^5 -X(9)^5 -X(10)^5 )^(1/5)
182 SUMY=0
183 FOR J44=1 TO 10000
185 SUMY=SUMY+X(J44)^3
187 NEXT J44
188 U=10000-SUMY
194 SUMNEW=0
195 FOR J44=1 TO 10000
196 SUMNEW=SUMNEW+X(J44)
197 NEXT J44
198 X(10001)=10000- SUMNEW
199 IF X(10001)<0 THEN X(10001)=X(10001) ELSE X(10001)=0
200 SUMNEWZ=0
203 FOR J44=1 TO 9999
205 SUMNEWZ=SUMNEWZ+ (10000-J44)* ( X(J44)^2-X(J44+1) )^2
207 NEXT J44
411 SONE= - (X(1)-1)^2 - ( X(10000)-1)^2 -10000* SUMNEWZ
689 PD1=SONE +50000!*X(10001) -50000!*ABS(U) +50000!*S
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 10001
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1555 UU=U
1559 GOTO 128
1670 NEXT I
1959 PRINT M,JJJJ,UU,A(1),A(8000)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM Personal Computer BASIC Compiler, Version 1.00. See the BASIC manual [12, page iii, Preface]. Copied by hand from the screen, the computer program's complete output through JJJJ=-31998 is shown below:
0 -32000 0 1 1
-4.43708E+09 -31999 0 1 2
0 -31998 0 1 1
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 [11, p. 414].
Of the 10000 A's, only the 2 A's of line 1959 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 12 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] Jack Lashover (November 12, 2012). Monte Carlo Marching. www.academia.edu/5481312/MONTE_ CARLO_MARCHING
[9] 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.
[10] 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.
[11] Duan Li, Xiaoling Sun, Nonlinear Integer Programming. Springer Science+Business Media,LLC (2006). http://www.books.google.ca/books?isbn=0387329951
[12] 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.
[13] Harvey M. Salkin, Integer Programming. Menlo Park, California: Addison-Wesley Publishing Company (1975).
[14] Harvey M. Salkin, Kamlesh Mathur, Foundations of Integer Programming. Elsevier Science Ltd (1989).
[15] K. Schittkowski, More Test Examples for Nonlinear Programming Codes. Springer-Verlag, 1987.
[16] S. Surjanovic, Zakharov Function. www.sfu.ca/~ssurjano/zakharov.html
[17] 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/
[18] 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/
[19] 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
