A Heuristic Nonlinear Integer Programming Solver Applied to a Nonlinear Programming Problem

Jsun Yui Wong

The computer program listed below tries to solve the following problem from pages 572-574 of Goldstein and Price [1].

Minimize EXP(USQ)+(SIN(4*X(1)-3*X(2)))^4+(1/2)*(2*X(1)+X(2)-10)^2
where USQ is ( (1/2)*(X(1)^2+X(2)^2-25) )^2.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR KK=1 TO 2
94 A(KK)=RND*5
95 NEXT KK
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 2
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*2)
183 RC=(1-RND*2)*A(J)
191 IF RND<.17 THEN X(J)=RND*5 ELSE IF RND<.2 THEN X(J)=A(J)+(RC) ELSE IF RND<.25 THEN X(J)=A(J)+(RND*RC) ELSE IF RND<.33 THEN X(J)=A(J)+(RND^2*RC) ELSE IF RND<.5 THEN X(J)=A(J)+(RND^3*RC) ELSE X(J)=A(J)+(RND^4*RC)
1221 USQ=((1/2)*(X(1)^2+X(2)^2-25))^2
1222 IF USQ>88.02969 GOTO 1670
1228 P1NEWMAY=-EXP(USQ)-(SIN(4*X(1)-3*X(2)))^4-(1/2)*(2*X(1)+X(2)-10)^2
1448 P=P1NEWMAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 2
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1670 NEXT I
1890 IF M>-1.00001 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),M,JJJJ
1999 NEXT JJJJ

The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. The complete output through JJJJ=-31135 is presented below. What immediately follows is a manual copy from the computer screen.

2.999617983186508 4.000793869733004 -1.000004120842557
-31935

2.997184176516209 4.002264407964584 -1.000006155732966
-31858

3.002505007680922 3.998106750081269 -1.000004920671327
-31555

2.996787080731433 4.002527007369667 -1.000008002822571
-31473

2.999477299300685 4.000418875366682 -1.000000207975854
-31262

3.003159982826601 3.997395781740299 -1.000007940510827
-31135

Interpreted in accordance with line 1912, the output through JJJJ=-31135 was produced in forty seconds on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

[1] A. A. Goldstein, J. F. Price, "On Descent from Local Minima," Mathematics of Computation, Vol. 25, No. 115 (Jul. 1971), pp. 569-574.

[2] C. A. Floudas, P. M. Parados, "A collection of test problems for constrained global optimization," Lecture Notes in Computer Science, vol. 455, 1991.

[3] Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.

A Heuristic Nonlinear Integer Solver Applied to a Nonlinear Integer Problem from the Literature, Second Edition

Jsun Yui Wong

The following computer program tries to solve the following problem from page 102 of Conley (1980) and from page 123 of Mohan and Nguyen (1999). Maximize X(1)^2+X(1)*X(2)-X(2)^2+X(3)*X(1)-X(3)^2+8*X(4)^2-17*X(5)^2+6*X(6)^3+X(6)*X(5)*X(4)*X(7)+X(8)^3+X(9)^4-X(10)^5-X(10)*X(5)+18*X(3)*X(7)*X(6) subject to 0<=X(i)<=99 and integer for i=1,2,3,...,10.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(142),A(142),L(33),K(133),HR(111),F(33),J(33)
19 FOR JJJJ=-32000 TO 32000
20 RANDOMIZE JJJJ
21 M=-1D+17
91 FOR KK=1 TO 10
94 A(KK)=FIX(RND*100)
95 NEXT KK
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 10
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*10)
192 X(J)=FIX(RND*100)
1225 P1NEWWAY=X(1)^2+X(1)*X(2)-X(2)^2+X(3)*X(1)-X(3)^2+8*X(4)^2-17*X(5)^2+6*X(6)^3+X(6)*X(5)*X(4)*X(7)+X(8)^3+X(9)^4-X(10)^5-X(10)*X(5)+18*X(3)*X(7)*X(6)
1448 P=P1NEWWAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>216300717# THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1984 PRINT M,JJJJ
1999 NEXT JJJJ

The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its complete output through JJJJ=-31979 is presented below. What immediately follows is a manual copy from the computer screen.

99 50 99 99 99
99 99 99 99 0
216300719 -31991

99 50 99 99 99
99 99 99 99 0
216300719 -31989

99 50 99 99 99
99 99 99 99 0
216300719 -31983

99 49 99 99 99
99 99 99 99 0
216300719 -31982

99 50 99 99 99
99 99 99 99 0
216300719 -31979

Interpreted in accordance with line 1912 through line 1914, the output through JJJJ=-31979 was produced in five seconds on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

W. Conley. Computer Optimization Techniques. Petrocelli Books Inc., New York, 1980.

D. Li and X. Sun. Nonlinear Integer Programming. Springer Science + Business Media, LLC, New York, 2006.

Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.

C. Mohan and H. T. Nguyen. A controlled random search techniques incorporating the simulated annealling concept for solving integer and mixed integer global optimization problems. Computational Optimization and Applications, 14: 103-132, 1999.