Jsun Yui Wong

The problem here is Li and Sun's Problem 14.3 but with **32760 unknowns** instead of their 100 unknowns; see Li and Sun [12, pp. 414-415]. Their problem is based on Walukiewicz/Schittkowski Test Problem 282 [17, Test Problem 282, page 106 and page 23]. Specifically, the test example here is to minimize

32760-1

(X(1)-1)^2 + ( X(32760)-1)^2 + 32760* SIGMA (32760-i)* ( X(i)^2-X(i+1) )^2

i=1

subject to

-5 <= X(i) <= 5, X(i) integer, i=1, 2, 3,..., 32760.

This problem can be solved with the following procedure:

(1) There Is a large penalty when X(1)^7+X(2)^7+X(3)*7+...+X(32760)^7 is <32750 or when X(1)^7+X(2)^7+X(3)*7+...+X(32760)^7 is > 32770; see line 492 below.

The following computer program uses QB64 [19, 21].

0 DEFINT J, K, B, X, A

2 DIM A(32763), X(32763)

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 32760

114 A(J44) = -5 + FIX(RND * 11)

117 NEXT J44

128 FOR I = 1 TO 50000

129 FOR KKQQ = 1 TO 32760

130 X(KKQQ) = A(KKQQ)

131 NEXT KKQQ

139 FOR IPP = 1 TO FIX(1 + RND * .3)

140 B = 1 + FIX(RND * 32763)

167 IF RND < .5 THEN X(B) = (A(B) - 1) ELSE X(B) = (A(B) + 1)

169 NEXT IPP

170 FOR J44 = 1 TO 32760

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 32760

228 SFE = SFE + X(J44)^7

233 NEXT J44

251 TSL = -32750 + SFE

283 TSm = 32770 - SFe

297 IF TSL < 0 THEN TSL = TSL ELSE TSL = 0

367 IF TSm < 0 THEN TSm = TSm ELSE TSm = 0

400 SUMNEWZ = 0

403 FOR J44 = 1 TO 32759

405 SUMNEWZ = SUMNEWZ + (32760 - J44) * (X(J44) ^ 2 - X(J44 + 1)) ^ 2

407 NEXT J44

411 SONE = -(X(1) - 1) ^ 2 - (X(32760) - 1) ^ 2 - 32760 * SUMNEWZ

492 PD1 = SONE + 5000000000# * TSL +5000000000*tsm

1111 IF PD1 <= M THEN 1670

1452 M = PD1

1454 FOR KLX = 1 TO 32760

1455 A(KLX) = X(KLX)

1456 NEXT KLX

1555 rem

1559 GOTO 128

1670 NEXT I

1778 PRINT A(1), A(2), A(3), A(32509), A(32760), M, JJJJ

1788 PRINT A(1111), A(11111), A(32757), A(32758), A(32759)

1999 NEXT JJJJ

Modelled after the computer programs in Wong [25], this BASIC computer program was run with QB64 [19, 21]. Copied by hand from the screen, the computer program's complete output through JJJJ=-31992 is shown below:

-1 3 -3 3 3

-8.114774E+14 -32000

0 3 -1 -1 3

1 1 1 1 1

-4.280749E+08 -31999

1 1 1 1 1

-3 1 -3 -1 2

-8.890357E+14 -31998

0 -3 3 3 -1

0 0 0 0 0

-1.637553E+14 -31997

0 0 0 0 0

1 1 1 1 1

-1.910301E+09 -31996

1 1 1 1 1

2 -3 1 -3 -3

-1.031564E+15 -31995

1 2 -3 0 -1

-3 -3 -3 1 -3

-1.054913E+15 -31994

0 1 -3 -3 -3

3 1 3 -1 -1

-8.16768E+14 -31993

-2 3 -1 3 3

1 1 1 1 1

0 -31992

1 1 1 1 1

Above there is no rounding by hand; it is just straight copying by hand from the screen.

At JJJJ=-31992, M=0 is optimal. See Li and Sun [12, pp. 414-415].

Of the 32760 A's, only the ten A's of line 1778 and line 1788 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 [19, 21], the wall-clock time for obtaining the output through JJJJ=-31992 was 24 hours.

(2) There Is a large penalty when X(1)^7+X(2)^7+X(3)*7+...+X(32760)^7 is between 32750 and 32770; see line 495 below.

The following computer program uses QB64 [19, 21].

0 DEFINT J, K, B, X, A

2 DIM A(32763), X(32763)

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 32760

114 A(J44) = -5 + FIX(RND * 11)

117 NEXT J44

128 FOR I = 1 TO 50000

129 FOR KKQQ = 1 TO 32760

130 X(KKQQ) = A(KKQQ)

131 NEXT KKQQ

139 FOR IPP = 1 TO FIX(1 + RND * .3)

140 B = 1 + FIX(RND * 32763)

167 IF RND < .5 THEN X(B) = (A(B) - 1) ELSE X(B) = (A(B) + 1)

169 NEXT IPP

170 FOR J44 = 1 TO 32760

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 32760

228 SFE = SFE + X(J44)^7

233 NEXT J44

251 TSL = -32750 + SFE

283 TSM = 32770 - SFE

297 REM IF TSL < 0 THEN TSL = TSL ELSE TSL = 0

367 REM IF TSm < 0 THEN TSm = TSm ELSE TSm = 0

388 IF TSL >0 AND TSM <0 THEN TSZ= -1000000 ELSE TSZ=0

400 SUMNEWZ = 0

403 FOR J44 = 1 TO 32759

405 SUMNEWZ = SUMNEWZ + (32760 - J44) * (X(J44) ^ 2 - X(J44 + 1)) ^ 2

407 NEXT J44

411 SONE = -(X(1) - 1) ^ 2 - (X(32760) - 1) ^ 2 - 32760 * SUMNEWZ

492 REM PD1 = SONE + 5000000000# * TSL +5000000000*tsm

495 PD1 = SONE + 5000000000# * TSZ

1111 IF PD1 <= M THEN 1670

1452 M = PD1

1454 FOR KLX = 1 TO 32760

1455 A(KLX) = X(KLX)

1456 NEXT KLX

1555 rem

1559 GOTO 128

1670 NEXT I

1778 PRINT A(1), A(2), A(3), A(32509), A(32760), M, JJJJ

1788 PRINT A(1111), A(11111), A(32757), A(32758), A(32759)

1999 NEXT JJJJ

Modelled after the computer programs in Wong [25], this BASIC computer program was run with QB64 [19, 21]. Copied by hand from the screen, the computer program's complete output through JJJJ=-31992 is shown below:

-1 1 1 1 3

-4.975006E+12 -32000

0 1 -1 1 2

0 0 0 2 5

-5.002075E+15 -31999

1 1 2 1 1

1 1 1 1 0

-5.002891E+15 -31998

0 1 2 0 0

1 1 1 1 1

-5.002059E+15 -31997

1 1 1 0 0

0 0 -1 -1 4

-4.919169E+12 -31996

1 1 -1 2 2

-1 1 0 0 -1

-4.348984E+12 -31995

1 0 0 -1 0

0 -1 1 -1 -1

-5.004152E+15 -31994

0 0 1 4 0

-1 1 1 1 -1

-5.165049E+12 -31993

1 1 1 1 0

0 0 0 0 0

-2 -31992

0 0 0 0 0

Above there is no rounding by hand; it is just straight copying by hand from the screen.

One notes the solution at JJJJ=-31992 with M=-2 because sometimes a nonoptimal solution is noteworthy; see Wah and Chen [20].

Of the 32760 A's, only the ten A's of line 1778 and line 1788 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 [19, 21], the wall-clock time for obtaining the output through JJJJ=-31992 was 20 hours.

(3) The realized solution with M=0 of the first computer program at JJJJ=-31996--which was produced with the two artificial constraints X(1)^7 + X(2)^7 + X(3)^7

+ ... + X(32760)^7 >= 32750 and X(1)^7 + X(2)^7 + X(3)^7 + ... + X(32760)^7 <= 32770--is the best produced; hence it is adopted.

For a computer program involving a mix of continuous variables and integer variables, see Wong [23], 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] J. Plummer, L. S. Lasdon, M. Ahmed, Solving a Large Nonlinear Progammming Problem on a Vector Processing Computer, *Annals of Operatons Research*, Volume 14 (1988), Issue 1, pp.. 291-304.

[15] Harvey M. Salkin, *Integer Programming*. Menlo Park, California: Addison-Wesley Publishing Company (1975).

[16] Harvey M. Salkin, Kamlesh Mathur, *Foundations of Integer Programming*. Elsevier Science Ltd (1989).

[17] K. Schittkowski, *More Test Examples for Nonlinear Programming Codes*. Springer-Verlag, 1987.

[18] S. Surjanovic, Zakharov Function. www.sfu.ca/~ssurjano/zakharov.html

[19] E.K. Virtanen (2008-05-26). "Interview With Galleon",

http://www.basicprogramming.org/pcopy/issue70/#galleoninterview

[20] Benjamin W. Wah, Yixin Chen. Solving Large-Scale Nonlinear Programming Problems by Constraint Partitioning. http://www.cse.wustl.edu/~ychen/public/C154.pdf

[21] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64

[22] 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/

[23] 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/

[24] 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 Elemsdition. http://myblogsubstance.typepad.com/substance/2013/09/

[25] 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

[26] Jsun Yui Wong (2015, March 08). Nonconvex Mixed Integer Nonlinear Programming (MINLP) Computer Programs with a Divide-and-Conquer Strategy To Solve Li and Sun's Problem 14.3 but with n=15110 General Integer Variables. http://myblogsubstance.typepad.com/substance/2015/03/

## Comments

You can follow this conversation by subscribing to the comment feed for this post.