Jsun Yui Wong
Case One: The Additional Constraint is a Less-Than-or-Equal-to Constraint
Similar to the computer programs of the preceding papers, the computer program below seeks to solve Li and Sun's Problem 14.4 plus an additional less-than-or-equal-to constraint; see [10, p. 415]. Specifically the computer program below tries to minimize the following:
100-1
SIGMA 100* ( X(i+1) - X(i)^2 )^2 + ( 1-X(i) )^2
i=1
subject to
X(1)+X(2)+X(3)+...+X(100) <= 100
-5<=X(i)<=5, X(i) integer, i=1, 2, 3,..., 100.
One notes line 114, line 174, and line 175, which are as follows:
114 A(J44 )=-5+FIX( RND*11)
174 IF X(J44)>5 THEN X(J44 )=A(J44 )
175 IF X(J44)<-5 THEN X(J44 )=A(J44 ).
0 REM DEFDBL A-Z
1 DEFINT J,K,B,X
2 DIM A(5000),X(5000)
81 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-1.5D+38
111 FOR J44=1 TO 100
114 A(J44)=-5+FIX(RND*11)
117 NEXT J44
128 FOR I=1 TO 3200
129 FOR KKQQ=1 TO 100
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+.3)
140 B=1+FIX(RND*100)
143 GOTO 167
144 REM GOTO 168
145 IF RND<.5 THEN 150 ELSE 167
150 R=(1-RND*2)*A(B)
160 X(B)=(A(B) +RND^3*R)
162 GOTO 168
163 IF RND<.5 THEN X(B)=(A(B)-.001) ELSE X(B)=(A(B) +.001 )
165 GOTO 168
167 IF RND<.5 THEN X(B)=CINT(A(B)-1) ELSE X(B)=CINT(A(B) +1 )
168 REM IF A(B)=0 THEN X(B)=1 ELSE X(B)=0
169 NEXT IPP
171 FOR J44=1 TO 100
174 IF X(J44)>5 THEN X(J44 )=A(J44 )
175 IF X(J44)<-5 THEN X(J44 )=A(J44 )
177 NEXT J44
200 SUMNEW=0
203 FOR J44=1 TO 100
205 SUMNEW=SUMNEW+X(J44)
207 NEXT J44
255 X(101)=100 - SUMNEW
303 IF X(101)<0 THEN X(101)=X(101) ELSE X(101)=0
401 SONE=0
402 FOR J44=1 TO 99
411 SONE=SONE+ 100* ( X(J44+1) - X(J44)^2 )^2 + ( 1-X(J44) )^2
421 NEXT J44
689 PD1=-SONE +5000000!*X(101)
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 101
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-444 THEN 1999
1931 PRINT A(1),A(2),A(3),A(4),A(5)
1936 PRINT A(96),A(97),A(98),A(99),A(100)
1939 PRINT M,JJJJ,A(301)
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=-31991 is shown below:
-1 1 1 1 1
1 0 -1 2 4
-310 -32000 0
-1 1 1 1 1
1 0 -1 2 4
-310 -31999 0
-1 1 1 1 1
1 1 1 1 1
-4 -31998 0
-1 1 1 1 1
1 1 1 1 1
-4 -31997 0
1 1 1 1 1
1 1 1 1 1
0 -31996 0
-1 1 1 1 1
1 1 1 2 4
-307 -31995 0
-1 1 1 1 1
1 1 1 1 1
-4 -31993 0
-1 1 1 1 1
1 1 1 1 1
-4 -31992 0
1 1 1 1 1
1 1 1 1 1
0 -31991 0
Above there is no rounding by hand.
M=0 is optimal.
Of the 100 A's, only the 10 A's of lin 1931 and line 1936 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=-31991 was fifty seconds..
Case Two: The Additional Constraint is an Equality Constraint
The computer program below seeks to solve Li and Sun's Problem 14.4 plus an additional equality constraint; see [10, p. 415]. Specifically the computer program below tries to minimize the following:
100-1
SIGMA 100* ( X(i+1) - X(i)^2 )^2 + ( 1-X(i) )^2
i=1
subject to
X(1)+X(2)+X(3)+...+X(100) = 100
-5<=X(i)<=5, X(i) integer, i=1, 2, 3,..., 100.
One notes line 114, line 174, and line 175, which are as follows:
114 A(J44 )=-5+FIX( RND*11)
174 IF X(J44)>5 THEN X(J44 )=A(J44 )
175 IF X(J44)<-5 THEN X(J44 )=A(J44 ).
0 REM DEFDBL A-Z
1 DEFINT J,K,B,X
2 DIM A(10000),X(10000)
81 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-1.5D+38
111 FOR J44=1 TO 100
114 A(J44)=-5+FIX(RND*11)
117 NEXT J44
128 FOR I=1 TO 3200
129 FOR KKQQ=1 TO 100
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+.3)
140 B=1+FIX(RND*100)
143 GOTO 167
144 REM GOTO 168
145 IF RND<.5 THEN 150 ELSE 167
150 R=(1-RND*2)*A(B)
160 X(B)=(A(B) +RND^3*R)
162 GOTO 168
163 IF RND<.5 THEN X(B)=(A(B)-.001) ELSE X(B)=(A(B) +.001 )
165 GOTO 168
167 IF RND<.5 THEN X(B)=CINT(A(B)-1) ELSE X(B)=CINT(A(B) +1 )
168 REM IF A(B)=0 THEN X(B)=1 ELSE X(B)=0
169 NEXT IPP
171 FOR J44=2 TO 100
174 IF X(J44)>5 THEN X(J44 )=A(J44 )
175 IF X(J44)<-5 THEN X(J44 )=A(J44 )
177 NEXT J44
200 SUMNEW=0
203 FOR J44=2 TO 100
205 SUMNEW=SUMNEW+X(J44)
207 NEXT J44
211 X(1)=100-SUMNEW
222 IF X(1)>5 THEN X(1 )=A(1 )
225 IF X(1)<-5 THEN X(1 )=A(1 )
401 SONE=0
402 FOR J44=1 TO 99
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 KLX=1 TO 100
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-444 THEN 1999
1931 PRINT A(1),A(2),A(3),A(4),A(5)
1936 PRINT A(96),A(97),A(98),A(99),A(100)
1939 PRINT 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=-31976 is shown below:
-1 1 1 1 1
1 1 1 2 4
-307 -31999
1 1 1 1 1
1 1 1 1 1
0 -31989
-1 1 1 1 1
0 1 1 1 1
-409 -31977
1 1 1 1 1
1 1 1 1 1
0 -31976
Above there is no rounding by hand.
M=0 is optimal.
Of the 100 A's, only the 10 A's of lin 1931 and line 1936 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=-31976 was two minutes.
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] M. A. Duran, I. E. Grossmann, An Outer-Approximation Algorithm for a Class of Mixed-Integer Nonlinear Programs. Mathematical Programming, 36:307-339, 1986.
[5] D. M. Himmelblau, Applied Nonlinear Programming. New York: McGraw-Hill Book Company, 1972.
[6] W. Hock, K. Schittkowski, Test Examples for Nonlinear Programming Codes. Springer-Verlag, 1981.
[7] Jack Lashover (November 12, 2012). Monte Carlo Marching. www.academia.edu/5481312/MONTE_ CARLO_MARCHING
[8] 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.
[9] 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.
[10] Duan Li, Xiaoling Sun, Nonlinear Integer Programming. Publisher: Springer Science+Business Media,LLC (2006). http://www.books.google.ca/books?isbn=0387329951
[11] 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.
[12] Harvey M. Salkin, Integer Programming. Menlo Park, California: Addison-Wesley Publishing Company (1975).
[13] Harvey M. Salkin, Kamlesh Mathur, Foundations of Integer Programming. Publisher: Elsevier Science Ltd (1989).
[14] K. Schittkowski, More Test Examples for Nonlinear Programming Codes. Springer-Verlag, 1987.
[15] S. Surjanovic, Zakharov Function. www.sfu.ca/~ssurjano/zakharov.html
[16] 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/
[17] 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/
[18] 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
