Substance: August 2015

The Domino Method of General Mixed Integer Nonlinear Programming Applied to the Air Transport Model of Markowitz and Manne and the Algorithm's Degree of Robustness, Second Edition

Jsun Yui Wong

Based on an earlier computer program [4], the computer program listed below seeks to solve the air transport model of Markowitz and Manne [1, pages 95-100].

While line 133 of the preceding paper is 133 FOR IPP=1 TO (1+FIX(RND*47)), for example, here line 133 is 133 FOR IPP=1 TO (1+FIX(RND*JJLL)), where JJLL is specified by line 22, which is 22 JJLL=FIX(RND*75). The newer line 133 covers more possibilities.

The following computer program uses qb64v1000-win [2, 3], which was also used for the preceding paper.

0 REM DEFDBL A-Z
2 DEFINT I,J,K
3 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(111),PS(33)
12 FOR JJJJ=-32000 TO 32000

15 RANDOMIZE JJJJ

16 M=-1D+37

22 JJLL=FIX(RND*75)

41 FOR J44=1 TO 48
42 A(J44)=FIX(RND*3)
43 NEXT J44
51 FOR J44=37 TO 48
52 A(J44)=FIX(RND*3)
53 NEXT J44
126 IMAR=10+FIX(RND*5000)
128 FOR I=1 TO 1000
129 FOR KKQQ=1 TO 48
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*JJLL))

181 J=1+FIX(RND*48)
183 R=(1-RND*2)*A(J)
187 X(J)=A(J)+(RND^3)*R
192 NEXT IPP
201 FOR J88=37 TO 48
203 X(J88)=CINT(X(J88) )
204 NEXT J88
211 X(43)=5-X(44)-X(45)

212 X(48)=X(43)+X(44)+X(45)-X(38)-X(41)
266 X(46)=X(37)+X(38)+X(39)-X(40)-X(43)
267 X(47)=X(40)+X(41)+X(42)-X(37)-X(44)

301 X(1)=X(20)+X(29)-X(4)-X(7)+6
302 X(5)=X(11)+X(30)-X(8)+6 -X(2)
303 X(9)=X(12)+X(21)-X(6)+6 -X(3)
304 X(10)=X(22)+X(31)-X(13)-X(16)+5
305 X(14) =X(2)-X(11)-X(17)+20 +X(33)
306 X(18) =X(24)+X(3)-X(12)-X(15)+31

307 X(19) =X(34)+X(13)-X(22)-X(25)+2

308 X(23)=X(4)+X(35)-X(20)-X(26)+24
309 X(27)=X(6)+X(15)-X(21)-X(24)+11
310 X(28)=X(16)+X(25)-X(31)-X(34)+14
311 X(32) = X(7)+X(26)-X(29)-X(35)+36

312 X(36) =X(8)+X(17)-X(30)-X(33)+7

371 FOR J44=1 TO 48
372 IF X(J44)<0 THEN 1670
373 NEXT J44

431 PS(21)=-7.5*X(37) +X(1) +X(2)+X(3)
432 PS(22)=-7.2*X(38)+X(4) +X(5) +X(6)
433 PS(23)=-7.5*X(39)+X(7)+X(8) +X(9)
434 PS(24)=-7.5*X(40) +X(10) +X(11)+X(12)
435 PS(25)=-7.5*X(41)+X(13) +X(14) +X(15)
436 PS(26)=-7.5*X(42)+X(16)+X(17) +X(18)
437 PS(27)=-7.2*X(43) +X(19) +X(20)+X(21)
438 PS(28)=-7.5*X(44)+X(22) +X(23) +X(24)
439 PS(29)=-5.6*X(45)+X(25)+X(26) +X(27)
440 PS(30)=-7.5*X(46) +X(28) +X(29)+X(30)
441 PS(31)=-7.5*X(47)+X(31) +X(32) +X(33)
442 PS(32)=-5.6*X(48)+X(34)+X(35) +X(36)

454 FOR J44=21 TO 32
455 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
456 NEXT J44
459 POB1=-4.5*X(37)- 8.3*X(38)- 2.9*X(39)- 4.5*X(40)- 4.2*X(41)- 6.9*X(42)- 8.3*X(43)-4.2*X(44)-10.9*X(45)- 2.9*X(46)- 6.9*X(47)- 10.9*X(48)
461 POB3=-999999999#*(PS(21)^4+PS(22)^4+PS(23)^4+PS(24)^4+PS(25)^4+PS(26)^4+PS(27)^4+PS(28)^4 +PS(29)^4+PS(30)^4+PS(31)^4+PS(32)^4 )
463 P1NEWMAY=POB1+POB3
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 48
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-153.6 THEN 1999

1900 GOTO 1945
1911 PRINT A(1),A(2),A(3),A(4),A(5)
1912 PRINT A(6),A(7),A(8),A(9),A(10)
1913 PRINT A(11),A(12),A(13),A(14),A(15)
1914 PRINT A(16),A(17),A(18),A(19),A(20)
1915 PRINT A(21),A(22),A(23),A(24),A(25)
1916 PRINT A(26),A(27),A(28),A(29),A(30)
1917 PRINT A(31),A(32),A(33),A(34),A(35)
1945 PRINT A(36),A(37),A(38),A(39),A(40)
1946 PRINT A(41),A(42),A(43),A(44),A(45)
1947 PRINT A(46),A(47),A(48),M,JJJJ,JJLL

1999 NEXT JJJJ

This computer program was run with qb64v1000-win [2, 3]. The complete output through JJJJ=32000 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

5.578844 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -29988
16

5.476037 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -24388
15

5.565383 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -23494
62

5.50935 1 1 1 1
3 7 0 5 0
2 5 1 -153.3035 -18909
69

5.509346 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -13469
27

5.080017 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -9051
58

5.291062 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 10744
33

5.536517 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 15567
52

5.50935 1 1 1 1
3 7 0 5 0
2 5 1 -153.3035 19421
69

5.581297 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 21392
35

5.508467 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 24218
61

5.327009 1 1 2 1
3 6 1 4 0
2 5 1 -153.4006 24861
38

5.59491 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 28598
46

4.877199 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 28746
74

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

At JJJJ=-23494--and elsewhere--M=-153.3 is optimal. See Markowitz and Manne [1, pp. 95-100].

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [2, 3], the wall-clock time for obtaining the output through JJJJ=32000 was 56 minutes.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References

[1] Harry M. Markowitz and Alan S. Manne. On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957) pp. 84-110.

[2] E.K. Virtanen (2008-05-26). "Interview With Galleon",
http://www.basicprogramming.org/pcopy/issue70/#galleoninterview

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

[4] Jsun Yui Wong (2013, August 1). The Domino Method of General Integer Nonlinear Programming Applied to the Air Transport Model of Markowitz and Manne, Third Edition. http://myblogsubstance.typepad.com/substance/2013/08/

Posted at 03:17 AM | Permalink | Comments (0)

The Domino Method of General Mixed Integer Nonlinear Programming Applied to the Air Transport Model of Markowitz and Manne and the Algorithm's Degree of Robustness

Jsun Yui Wong

Based on an earlier computer program [65], the computer program listed below seeks to solve the air transport model of Markowitz and Manne [45, pages 95-100].

One important goal of the present paper is to demonstrate the degree of robustness of the algorithm, especially with respect to the IPP of line 133 of the following computer program, which is 133 FOR IPP=1 TO (1+FIX(RND*47)).

The following computer program uses qb64v1000-win [63, 64], which was also used for the preceding paper.

0 REM DEFDBL A-Z
2 DEFINT I,J,K
3 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(111),PS(33)
12 FOR JJJJ=-32000 TO 32000
15 RANDOMIZE JJJJ

16 M=-1D+37
41 FOR J44=1 TO 48
42 A(J44)=FIX(RND*3)
43 NEXT J44
51 FOR J44=37 TO 48
52 A(J44)=FIX(RND*3)
53 NEXT J44
126 IMAR=10+FIX(RND*5000)
128 FOR I=1 TO 1000
129 FOR KKQQ=1 TO 48
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*47))

181 J=1+FIX(RND*48)
183 R=(1-RND*2)*A(J)
187 X(J)=A(J)+(RND^3)*R
192 NEXT IPP
201 FOR J88=37 TO 48
203 X(J88)=CINT(X(J88) )
204 NEXT J88
211 X(43)=5-X(44)-X(45)

212 X(48)=X(43)+X(44)+X(45)-X(38)-X(41)
266 X(46)=X(37)+X(38)+X(39)-X(40)-X(43)
267 X(47)=X(40)+X(41)+X(42)-X(37)-X(44)

301 X(1)=X(20)+X(29)-X(4)-X(7)+6
302 X(5)=X(11)+X(30)-X(8)+6 -X(2)
303 X(9)=X(12)+X(21)-X(6)+6 -X(3)
304 X(10)=X(22)+X(31)-X(13)-X(16)+5
305 X(14) =X(2)-X(11)-X(17)+20 +X(33)
306 X(18) =X(24)+X(3)-X(12)-X(15)+31

307 X(19) =X(34)+X(13)-X(22)-X(25)+2

308 X(23)=X(4)+X(35)-X(20)-X(26)+24
309 X(27)=X(6)+X(15)-X(21)-X(24)+11
310 X(28)=X(16)+X(25)-X(31)-X(34)+14
311 X(32) = X(7)+X(26)-X(29)-X(35)+36

312 X(36) =X(8)+X(17)-X(30)-X(33)+7

371 FOR J44=1 TO 48
372 IF X(J44)<0 THEN 1670
373 NEXT J44

431 PS(21)=-7.5*X(37) +X(1) +X(2)+X(3)
432 PS(22)=-7.2*X(38)+X(4) +X(5) +X(6)
433 PS(23)=-7.5*X(39)+X(7)+X(8) +X(9)
434 PS(24)=-7.5*X(40) +X(10) +X(11)+X(12)
435 PS(25)=-7.5*X(41)+X(13) +X(14) +X(15)
436 PS(26)=-7.5*X(42)+X(16)+X(17) +X(18)
437 PS(27)=-7.2*X(43) +X(19) +X(20)+X(21)
438 PS(28)=-7.5*X(44)+X(22) +X(23) +X(24)
439 PS(29)=-5.6*X(45)+X(25)+X(26) +X(27)
440 PS(30)=-7.5*X(46) +X(28) +X(29)+X(30)
441 PS(31)=-7.5*X(47)+X(31) +X(32) +X(33)
442 PS(32)=-5.6*X(48)+X(34)+X(35) +X(36)

454 FOR J44=21 TO 32
455 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
456 NEXT J44
459 POB1=-4.5*X(37)- 8.3*X(38)- 2.9*X(39)- 4.5*X(40)- 4.2*X(41)- 6.9*X(42)- 8.3*X(43)-4.2*X(44)-10.9*X(45)- 2.9*X(46)- 6.9*X(47)- 10.9*X(48)
461 POB3=-999999999#*(PS(21)^4+PS(22)^4+PS(23)^4+PS(24)^4+PS(25)^4+PS(26)^4+PS(27)^4+PS(28)^4 +PS(29)^4+PS(30)^4+PS(31)^4+PS(32)^4 )
463 P1NEWMAY=POB1+POB3
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 48
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-153.6 THEN 1999

1900 GOTO 1945
1911 PRINT A(1),A(2),A(3),A(4),A(5)
1912 PRINT A(6),A(7),A(8),A(9),A(10)
1913 PRINT A(11),A(12),A(13),A(14),A(15)
1914 PRINT A(16),A(17),A(18),A(19),A(20)
1915 PRINT A(21),A(22),A(23),A(24),A(25)
1916 PRINT A(26),A(27),A(28),A(29),A(30)
1917 PRINT A(31),A(32),A(33),A(34),A(35)
1945 PRINT A(36),A(37),A(38),A(39),A(40)
1946 PRINT A(41),A(42),A(43),A(44),A(45)
1947 PRINT A(46),A(47),A(48),M,JJJJ
1999 NEXT JJJJ

This computer program was run with qb64v1000-win [63, 64]. The complete output through JJJJ=32000 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1.206398E-04 1 1 1
1
4 7 0 5 0
2 6 0 -153.5 -31813

5.514534 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -24022

5.319738 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -14995

5.566916 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 1616

5.520392 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 3032

5.572524 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 3391

4.567156 1 1 2 1
3 6 1 4 0
2 5 1 -153.4042 4833

5.430542 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 9738

9.421259E-06 1 1 2
1
4 6 1 4 0
2 6 0 -153.6 22722

5.342381 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 27450

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

At JJJJ=1616--and elsewhere--M=-153.3 is optimal. See Markowitz and Manne [45, pp. 95-100].

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [63 ,64], the wall-clock time for obtaining the output through JJJJ=32000 was one hour.

The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*45)).

5.587453 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -30987

5.574075 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -20857

5.554199 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -11007

5.573198 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -4460

4.634404 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 1218

5.545411 1 1 1 1
3 7 0 5 0
2 5 1 -153.3005 8704

5.593355 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 26645

5.130655 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 30212

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 55 minutes.

The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*37)).

5.589005 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -31401

5.589306 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -29669

5.346732 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -18153

5.202597 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -2954

4.632438 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 2903

5.489368 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 19948

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 50 minutes.

The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*35)).

5.194385 1 1 2 1
3 6 1 4 0
2 5 1 -153.4001 -24556

5.486193 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -19006

5.19687 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -13985

5.558049 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -11629

5.304744 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -9524

5.17981 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -7061

5.533294 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 11182

5.594732 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 19486

5.479322 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 30014

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 50 minutes.

The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*27)).

5.464866 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -19384

5.42462 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -18445

5.595021 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -7397

5.094746 1 1 1 1
3 7 0 5 0
2 5 1 -153.3001 3767

3.443135E-04 1 1 1
1
4 7 0 5 0
2 6 0 -153.5 23220

5.343966 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 23868

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 42 minutes.

The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*25)).

5.527765 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -19310

1.206994E-04 1 2 1
1
3 7 0 5 0
3 5 0 -153.6 9260

5.515518 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 23266

2.980232E-08 1 2 1
1
3 7 0 5 0
3 5 0 -153.6 30398

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 44 minutes.

The following output was obtained by using the above computer program with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*17)).

5.315485 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -18672

4.69842 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 1011

4.997941 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 2446

4.990879 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 3451

5.560705 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 4059

5.028902 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 10682

4.923874 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 14955

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 38 minutes.

The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*15)).

4.984283 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -15196

5.391785 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -14512

4.815897 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 11963

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 40 minutes.

The following output was obtained by using the above computer program with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*7)).

3.261672E-04 1 1 1
1
4 7 0 5 0
2 6 0 -153.5066 -16926

5.441607 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -5836

5.166392 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 4692

5.494189 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 9590

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 35 minutes.

The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*5)).

5.312799 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 13332

5.464413 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 19616

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 35 minutes.

The following output was obtained by using the above computer program with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*3)).

4.992488 1 1 1 1
3 7 0 5 0
2 5 1 -153.3034 6305

5.374687 1 1 1 1
3 7 0 5 0
2 5 1 -153.3001 11871

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 62], the wall-clock time for obtaining the output through JJJJ=32000 was 38 minutes.

The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*.3)).

5.361702 1 1 2 1
3 6 1 4 0
2 5 1 -153.4011 -825

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [63, 64], the wall-clock time for obtaining the output through JJJJ=32000 was 48 minutes.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References

[1] J. S. Arora, Introduction to Optimun Design. New York: McGraw-Hill; 1989.

[2] Dana H. Ballard, C. O Jelinek, R. Schinzinger (1974), An Algorithm for the Solution of Constrained Generalised Polynomial Programming Problems. The Computer Journal, Volume 17, Number 3, pp. 261-266.

[3] M. C. Bartholomew-Biggs, A Numerical Comparison between Two Approaches to the Nonlinear Programming Problem, in Towards Global Optimization 2, edited by L. C. W. Dixon, G. P. Szego, pp. 293-312. North-Holland Publishing Company 1978.

[4] O. Berman, N. Ashrafi, Optimization Models for Reliability of Modular Software Systems. IEEE Transactions on Software Engineering 19 (11):1119-1123, 1993.

[5] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming. New York: John Wiley and Sons, 1968.

[6] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition. Brooks/Cole 2011.

[7] T. Y. Chen, H. C. Chen (2009): Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[8] S. H. Chew, Q. Zheng, Integral Global Optimization. Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[9] C. A. C. Coello, E. M. Mesura (2002), Constraint Handling in Genetic Algoritmms through the Use of Dominance-Based Tournament Selection. Advanced Engineering Informatics, 16 (3), 193-203.

[10] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[11] Kalyanmoy Deb (2000), An Efficient Constraint Handling Method for Genetic Algorithms. Computer Methods in Applied Mechanics and Engineering, 186 (2000), 311-338.

[12] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications. John Wiley and Sons, 1967.

[13] M. A. Duran, I. E. Grossmann (1986), An Outer-Approximation Algorithm for a Class of Mixed-Integer Nonlinear Programs. Mathematical Programming, Vol. 36:307-339, 1986.

[14] F. Erbatur, O. Hasancebi, I. Tutuncu, H. Kilic (2000) Optimal Design of Planar and Spcae Structures with Genetic Algorithms. Computers and Structures, 75 (2), 209-224.

[15] C. A. Floudas, A. R. Ciric (1989), Strategies for Overcoming Uncertainties in Heat Exchanger Network Synthesis. Computers and Chemical Engineering, Vol 13, No. 10, pp. 1133-1152, 1989.

[16] C. A. Floudas, A. Aggarwal, A. R. Ciric (1989), Global Optimum Search for Nonconvex NLP and MINLP Problems. Computers and Chemical Engineering, Vol 13, No. 10, pp. 1117-1132, 1989.

[17] C. A. Floudas, P. M. Pardalos, A Collection of Test Problems for Constrained Global Optimization Algorithms. Springer-Verlag, 1990.

[18] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization. Oxford University Press, 1995.

[19] C. A. Floudas, Deterministic Global Optimization. Kluwer Academic Publishers, 2000.

[20] S. Gholizadeh, A. Barzegar (2012), Shape Optimization of Structures for Frequency Constraints by Sequential Harmony Search Algorithm, Engineering Optimization, DOI:10.1080/0305215X.2012.704028.

[21] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB. John Wiley and Sons, Inc. 2008.

[22] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring. Addison-Wesley Publishing Company, 1988.

[23] Rick Hesse (1973), A Heuristic Search Procedure for Estimating a Global Solution of Nonconvex Programming Problems. Operations Research, Vol. 21, No. 6 (Nov. - Dec., 1973), pp. 1267-1280.

[24] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes. Springer-Verlag 1981.

[25] Majid Jaberipour, Esmaile Khorram (2010), Two Improved Harmony Search Algorithms for Solving Engineering Optimization Problems. Communications in Nonlinear Science and Numerical Simulation 15 (2010) 3316-3331.

[26] M. Jaberipour, E. Khorram (2010), Solving the Sum-of-Ratios Problems by a Harmony Search Algorithm. Journal of Computational and Applied Mathematics 234 (2010) 733-742.

[27] M. Jaberipour, E. Khorram (2011), A New Harmony Search Algorithm for Solving Mixed Discrete Engineering Optimization Problems. Engineering Optimization, 05/2011, 43:507-523.

[28] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008. Berlin: Springer, 2010.

[29] B. K. Kannen , S. N. Kramer (1994), An Augmented Lagrange Multiplier Based Method for Mixed Integer Discrete Continuous Optimization and its Applications to Mechanical Design. Journal of Mechanical Design, 116, pp. 405-411.

[30] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA). Computer-Aided Design 43 (2011) 1769-1792.

[31] R. Baker Kearfott, Some Tests of Generalized Bisection. ACM Transactions on Mathematical Software, Vol.13, No. 3, September 1987, pages 197-220.

[32] Esmaile Khorram, Majid Jaberipour, Harmony Search Algorithm for Solving Combined Heat and Power Economic Dispatch Problems. Energy Conversion and Management 52 (2011) 1550-1554.

[33] G. R. Kocis, I. E. Grossmann (1987), Global Optimization of Nonconvex MINLP Problems in Process Synthesis. http://repository.cmu.edu/cheme/111.

[34] G. R. Kocis, I. E. Grossmann, Relaxation Strategy for the Structural Optimization of Process Flow Sheets. Ind. Eng. Chem. Res., 26 (9):1869 (1987).

[35] Sonia Krzyworzcka, Extension of the Lanczos and CGS Methods to Systems of Nonlinear Equations. Journal of Computational and Aplied Mathematics 69 (1996) 181-190.

[36] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[37] 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.

[38] K. S. Lee, Z. W. Geem (2005), A New Meta-Heuristic Algorithm for Continuous Engineering Optimization: Harmony Search Theory and Practice. Computer Methods in Applied Mechanics and Engineering 194 (2005) 3902-3933.

[39] H. L. Li, P. Papalambros (1985), A Production System for Use of Global Optimization Knowledge. ASME Journal of Mechanisms, Transmissions, and Automation in Design. June 1985, Vol. 107, 277-284.

[40] J. J. Liang, T. P. Runarsson, E. Mezura-Montes, M. Clerc, P. N. Suganthan, C. A. C. Coello, K. Deb. Problem Definitions and Evaluation Criteria for the CEC 2006 Special Session on Constrained Real-Parameter Optimization. www.lania.mx/~emezura/util/files/tr_cec06.pdf

[41] Ming-Hua Lin, Jung-Fa Tsai, Pei-Chun Wang (2012), Solving Engineering Optimization Problems by a Deterministic Global Optimization Approach. Applied Mathematics and Information Sciences 6-3S No. 3, 1101-1107 (2012).

[42] Ya-Zhang Luo, Guo-Jing Tang, Li-Ni Zhou, Hybrid Approach for Solving Systems of Nonlinear Equations Using Chaos Optimization and Quasi-Newton Method. Applied Soft Computing 8 (2008) 1068-1063.

[43] M. Mahdavi, M. Fesanghary, E. Damangir (2007), An Improved Harmony search Algorithm for Solving Optimization Problems. Applied Mathematics and Computation, 188 (2), 1567-1579.

[44] C. D. Maranas, C. A. Floudas, Finding All Solutions of Nonlinearly Constrained Systems of Equations. Journal of Global Optimization, 7(2):143-182, 1995.

[45] Harry M. Markowitz and Alan S. Mann. On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957) pp. 84-110.

[46] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems. ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

[47] E. Mezura-Montes, Alternative Techniques to Handle Constraints in Evolutionary Optimization, Doctor of Science Thesis, December 7th, 2004. www.lania.mx/~emezura/

[48] E. Mezura-Montes, A. G. Palomeque-Ortiz, Self-Adaptive and Deterministic Parameter Control in Differential Evolution for Constrained Optimization, in Constraint-Handling in Evolutionary Optimization. Series: Studies in Computationa Intelligence, Volume 198, Efren Mezura-Montes [Ed.]. Springer, 2009, pp. 95-120.

[49] 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.

[50] Yuanbin Mo, Hetong Liu, Qin Wang, Conjugate Direction Particle Swarm Optimization Solving Systems of Nonlinear Equations. Computers and Mathematics with Applications 57 (2009) 1877-1882.

[51] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis. Cambridge University Press, 2009.

[52] Salam Nema, John Goulermas, Graham Sparrow, Phil Cook (2008), A Hybrid Particle Swarm Branch-and-Bound (HPB) Optimizer for Mixed Discrete Nonlinear Programming. IEEE Transactions on Systems, Man, and Cybernetics--Part A: Systems and Humans Volume 38, Number 6, November 2008, 1411-1424.

[53] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition. Cambridge University Press, 2000.

[54] W. L. Price, Global Optimization by Controlled Random Search. Journal of Optimization Theory and Applications, July 1983, Volume 40, Issue 3, pp. 333-348.

[55] Singiresu S. Rao, Ying Xiong (2005), A Hybrid Genetic Algorithm for Mixed-Discrete Design Optimization. ASME Journal of Mechanical Design, Vol. 127, November 2005, pp. 1100-1112.

[56] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition. Academic Press, 1993.

[57] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design. Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[58] E. Sandgren (1990), Nonlinear Integer and Discrete Programming in Mechanical Design Optimization. Journal of Mechanical Design, 112, pp. 223-229.

[59] R. Schinzinger (1965), Optimization in Electromagnetic System Design, in Recent Advances in Optimization Techniques, edited by A. Lavi and T. P. Vogel, John Wiley and Sons, pp. 163-213.

[60] Chaoli Sun, Jianchao Zeng, Jeng-Shyang Pan (2011), A Modified Particle Swarm Optimization with Feasobo;oty-Based Rules for Mixed-Variables Optimization Problems. International Journal of Innovative Computing, Information and Control, Volume 7, Number 6, June 2011, 3081-3096.

[61] Jung-Fa Tsai (2010), Global Optimization for Signomial Discrete Programming Problems in Engineering Design. Engineering Optimization, 42:9, pp. 833-843.

[62] L.-W. Tsai, A. P. Morgan, Solving the Kinematics of the Most General Six- and Five-Degree-of Freedom Manipulators by Continuation Methods. Journal of Mechanisms, Transmissions, and Automation in Design, June 1985, Vol. 107, pp. 189-200.

[63] E.K. Virtanen (2008-05-26). "Interview With Galleon",
http://www.basicprogramming.org/pcopy/issue70/#galleoninterview

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

[65] Jsun Yui Wong (2013, August 1). The Domino Method of General Integer Nonlinear Programming Applied to the Air Transport Model of Markowitz and Manne, Third Edition. http://myblogsubstance.typepad.com/substance/2013/08/

Posted at 01:23 PM | Permalink | Comments (0)

Solving Another Large Nonlinear Integer Programming Test Problem of 32760 General Integer Variables with an Assist from Artificial Constraints, Fourth Edition

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.

One notes that while line 251 and line 283 in the computer programs of the preceding paper are 251 TSL = -32755 + SFE and
283 TSm = 32765 - SFe, respectively, here line 251 and line 283 are 251 TSL = -32745 + SFE and 283 TSm = 32775 - SFe, respectively

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 <32745 or when X(1)^7+X(2)^7+X(3)*7+...+X(32760)^7 is > 32775; 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 = -32745 + SFE

283 TSm = 32775 - 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 [26], this BASIC computer program was run with QB64 [19, 21]. Copied by hand from the screen, the computer program's output through JJJJ=-31989 is shown below:

-1 3 -3 3 3
-8.134479E+14 -32000
0 3 -1 -1 3

0 -1 0 -1 -1
-4.918774E+13 -31999
-1 -1 -1 -1 -1

-1 0 -1 -1 -1
-4.997162E+13 -31998
0 -1 -1 -1 -1

2 2 2 0 2
-1.358585E+14 -31997
1 2 2 -1 2

2 2 -2 2 2
-1.641085E+14 -31996
-1 2 2 2 2

-1 -1 0 -1 -1
-5.046502E+13 -31995
-3 0 -1 -3 3

-3 1 3 3 3
-7.384195E+14 -31994
3 2 -4 -3 -1

1 1 1 1 1
-1.935069E+09 -31993
1 1 1 1 1

4 -2 -2 5 -4
-3.23309E+15 -31992
3 4 -5 5 -5

0 0 0 0 0
-9.998909E+11 -31991
0 0 0 0 0

0 0 0 0 0
-8.442721E+11 -31990
0 0 0 0 0

1 1 1 1 1
0 -31989
1 1 1 1 1

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

At JJJJ=-31989, 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=-31989 was 40 hours.

(2) There is a large penalty when X(1)^7+X(2)^7+X(3)*7+...+X(32760)^7 is between 32745 and 32775 ; 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 = -32745 + SFE

283 TSm = 32775 - 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 [26], this BASIC computer program was run with QB64 [19, 21]. Copied by hand from the screen, the computer program's 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 19 hours.

(3) The realized solution with M=0 of the first computer program at JJJJ=-31989--which was produced with the two artificial constraints X(1)^7 + X(2)^7 + X(3)^7
+ ... + X(32760)^7 >= 32745 and X(1)^7 + X(2)^7 + X(3)^7 + ... + X(32760)^7 <= 32775--is the best produced; hence it can be 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 Operations 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/

Posted at 01:35 PM | Permalink | Comments (0)

Solving Another Large Nonlinear Integer Programming Test Problem of 32760 General Integer Variables with an Assist from Artificial Constraints, Third Edition

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 <32755 or when X(1)^7+X(2)^7+X(3)*7+...+X(32760)^7 is > 32765; 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 100000

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 = -32755 + SFE

283 TSM = 32765 - SFE

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

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

388 rem 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 PD1 = SONE + 5000000000# * TSL +5000000000*tsm

495 rem 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 [26], this BASIC computer program was run with QB64 [19, 21]. Copied by hand from the screen, the computer program's output through JJJJ=-31977 is shown below:

-1 3 -3 3 3
-8.12255E+14 -32000
0 3 -1 -1 3

-1 0 -1 -1 -1
-4.268276E+13 -31999
-1 -1 -1 -1 -1

0 -4 4 -3 -5
-2.117627E+15 -31998
3 3 -1 4 -2

0 -3 4 -1 4
-2.10472E+15 -31997
4 4 4 3 2

2 2 -2 -2 -2
-2.455755E+14 -31996
1 -2 2 1 -2

2 -2 -2 -1 2
-2.69868E+14 -31995
-2 1 1 1 -2

3 1 3 -1 3
-8.905697E+14 -31994
-3 0 -1 -3 3

2 -3 1 0 2
-1.157419E+14 -31993
2 1 2 2 0

1 1 1 1 1
-1.744634E+09 -31992
1 1 1 1 1

0 -3 3 -3 -3
? -31991
-3 2 0 1 -3

-4 3 1 2 3
? -31990
2 -3 -5 -1 -2

3 1 3 -1 -2
-8.883873E+14 -31989
0 0 -1 3 -2

2 2 2 2 -2
-1.633181E+14 -31988
2 2 2 2 -1

2 1 2 -1 2
-1.213422E+14 -31987
2 -1 2 2 2

-1 -1 0 -1 -1
? -31986
-1 -1 -1 -1 -1

-1 0 1 -1 -1
-5.036602E+13 -31985
0 -1 -1 -1 -1

0 0 0 0 0
-1.63775E+14 -31984
0 0 0 0 0

-3 1 0 2 -3
-1.042043E+15 -31983
0 3 3 -3 -3

-1 2 -2 -2 -2
-2.433735E+14 -31982
2 2 -2 2 -1

0 0 0 0 1
-6.363939E+11 -31981
0 0 1 2 1

0 0 0 0 0
-1.63775E+14 -31980
0 0 0 0 0

0 -2 0 -2 -1
-2.768958E+14 -31979
0 0 -2 -2 -2

-5 4 -4 -1 -1
-3.208586E+15 -31978
-3 1 -1 2 5

1 1 1 1 1
0 -31977
1 1 1 1 1

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

At JJJJ=-31977, 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=-31977 was 60 hours.

(2) There is a large penalty when X(1)^7+X(2)^7+X(3)*7+...+X(32760)^7 is between 32755 and 32765; 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 100000

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 = -32755 + SFE

283 TSM = 32765 - 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 [26], this BASIC computer program was run with QB64 [19, 21]. Copied by hand from the screen, the computer program's output through JJJJ=-31999 is shown below:

-1 1 1 1 3
-4.967824E+12 -32000
0 1 -1 1 2

0 0 0 0 0
-2 -31999
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=-31999 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=-31999 was seven hours.

(3) The realized solution with M=0 of the first computer program at JJJJ=-31977--which was produced with the two artificial constraints X(1)^7 + X(2)^7 + X(3)^7
+ ... + X(32760)^7 >= 32755 and X(1)^7 + X(2)^7 + X(3)^7 + ... + X(32760)^7 <= 32765--is the best produced; hence it can be 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/

Posted at 06:42 PM | Permalink | Comments (0)

Solving Another Large Nonlinear Integer Programming Test Problem of 32760 General Integer Variables with an Assist from Artificial Constraints, Second Edition

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.