The Domino Method Solving a Nonlinear System of 41 Simultaneous Equations and 34 General Integer Variables, Second Edition

Jsun Yui Wong

The following computer program seeks to solve simultaneously the system of forty-one Diophantine equations, including fourteen exponential Diophantine equations like
X(31)^X(5)+ X(32)^ X(4) + X(33)^X(7) = X(34)^X(9), for example, and thirty-four general integer variables taken (with modifications) mainly from page 11381 of Abraham, Sanyal, and Sanglikar [1], from page 252 of Waldschmidt [4], and from page 740, page 744, and page 745 of Perez, Amaya, and Correa [3]. These forty-one simultaneous equations are as follows:

X(1)^15 + X(2)^15 = 1088090731
X(2)^14 + X(9)^14 = 268451840
X(1)^13 + X(3)^13 = 1222297448
X(3)^11 + X(10)^11 = 411625181
X(3)^12 + X(8)^12 = 244144721
X(11)+X(12)+X(13)+X(14) = 32
X(15) +X(16)+X(17)+X(18) = 20
X(19)+X(20)+X(21)+X(22) = 17
X(23)+X(24)+X(25)+X(26) = 20
X(27)+X(28)+X(29)+X(30) = 26
X(31)+X(32)+X(33)+X(34) = 16
1+3^X(8) = (2^X(5) )*(5 ^X(6))
X(8)^2 +X(5)^2 +X(6)^2 = 3*X(8)*X(5)*X(6)
X(11) ^2 +X(12)^2+ X(13)^2 + X(14) ^2 =372
X(15) ^2 +X(16)^2+ X(17)^2 + X(18) ^2 = 108
X(19) ^2 +X(20)^2+ X(21)^2 + X(22) ^2 =87
X(23) ^2 +X(24)^2+ X(25)^2 + X(26) ^2 = 108
X(27) ^2 +X(28)^2+ X(29)^2 + X(30) ^2 = 204
X(31) ^2 +X(32)^2+ X(33)^2 + X(34) ^2 =68
5^X(5)+5^X(1) = 3^X(2) + 7^X(9)
5^X(6)+5^X(3) = 3^X(10) + 7^X(2)
5^X(3)+5^X(7) = 3^X(10) + 7^X(2)
5^X(1)+5^X(5) = 3^X(2) + 7^X(9)
13^X(4)+7^X(5) = 3^X(6) + 5^X(7)
17^X(4)+7^X(5) = 3^X(6) + 5^X(7)
3^X(5)+5^X(4) +7^X(6) = 11^X(7)
X(1) -X(3)+2* X(5) -X(7)-X(9) =-3
X(2)+(2* X(4))^2 -6* X(6)- X(8)+2* X(10) = 8
X(1) -3* X(2)+4* X(4) +X(6)-6*X(7)+ X(8)-2*X(9) =-16
5* X(1)+2* X(2)-8* X(4)-3* X(5)+4* X(6)+X(7)-X(9) =23
2* X(1) +(X(2)+3* X(4))^3 + (5*X(7))^2-6* X(8)+X(9)-9* X(10) =31
(2* X(1) + X(2))^2+3*X(3)-10* X(5)-( X(6)+3*X(7))^3- X(8)-6*X(9) =27
X(11)^X(4)+ X(12)^ X(5) = X(13)^X(6) + X(14)^X(7)
X(15)^X(1)+ X(16)^ X(5) = X(17)^X(2) + X(18)^X(9)
1 + X(19)^X(6)+ X(20)^ X(7) = X(21)^X(9)+ X(22)^X(4)
X(23)^X(6)+ X(24)^ X(7) = X(25)^X(9) + X(26)^X(4)
X(27)^X(5)+ X(28)^ X(4) = X(29)^X(6)+ X(30)^X(7)
X(31)^X(5)+ X(32)^ X(4) + X(33)^X(7) = X(34)^X(9)
3* X(1) +2* X(2)-5*X(3)- X(4)^4-2* X(5) + X(6)+4*X(7)-10* X(8)+8*X(9) = -9
X(1) ^2-2*(X(2)+ X(4))^3 + X(5)-3* X(6)-X(7)+4*X(9) +15* X(10) = -24
3* X(1) -(2* X(2))^2+10*X(3)-9* X(4)+3* X(5) + X(6)-2*X(7)- 8* X(8)+12*X(9)-5* X(10) = -25

While line 369 and line 370 of the preceding paper are 369 FOR J44=1 TO 30 and
370 IF X(J44)<0 THEN 1670, line 369 and line 370 here are 369 FOR J44=1 TO 34 and
370 IF X(J44)<0 THEN X(J44)=20. The new line 370, which is 370 IF X(J44)<0 THEN X(J44)=20, is noteworthy.

0 DEFDBL A-Z
1 DEFINT I,J,K,A,X
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99)
5 DIM AA(99),HR(32),HHR(32),PLHS(44),LB(22),UB(22),PX(44),J44(44),PN(22),NN(99)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
111 FOR J44=1 TO 34
112 A(J44)= ( RND *20)
113 NEXT J44
128 FOR I=1 TO 3000
129 FOR KKQQ=1 TO 34
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*9)
140 B=1+FIX(RND*34)
150 R=(1-RND*2)*A(B)
155 IF RND<.5 THEN 160 ELSE 167
160 X(B)=(A(B) +RND^3*R)
165 GOTO 168
167 IF RND<.5 THEN X(B)=CINT(A(B)-1) ELSE X(B)=CINT(A(B) +1)
168 NEXT IPP
201 IF ( +1088090731#-X(1)^15# )<0 THEN 1670
210 X(2)= ( +1088090731#-X(1)^15# )^(1#/15#)
215 X(9)= ( +268451840#-X(2)^14# )^(1#/14#)
222 X(3)= ( +1222297448#-X(1)^13# )^(1#/13#)
233 X(10)= ( +411625181#-X(3)^11# )^(1#/11#)
244 X(8)= ( +244144721#-X(3)^12# )^(1#/12#)
255 X(11)=32#-X(12)-X(13)-X(14)
265 X(15)=20#-X(16)-X(17)-X(18)
275 X(19)=17#-X(20)-X(21)-X(22)
277 X(23)=20#-X(24)-X(25)-X(26)
279 X(27)=26#-X(28)-X(29)-X(30)
281 X(31)=16#-X(32)-X(33)-X(34)
369 FOR J44=1 TO 34
370 IF X(J44)<0 THEN X(J44)=20
371 NEXT J44
399 N(37)=1#+3#^X(8)-(2#^X(5) )*(5# ^X(6))
401 N(39)=X(8)^2# +X(5)^2# +X(6)^2# -3#*X(8)*X(5)*X(6)
505 N(2)=-372#+X(11) ^2 +X(12)^2+ X(13)^2 + X(14) ^2
508 N(1)=-108#+X(15) ^2 +X(16)^2+ X(17)^2 + X(18) ^2
509 N(0)=-87#+X(19) ^2 +X(20)^2+ X(21)^2 + X(22) ^2
510 N(9)=-108#+X(23) ^2 +X(24)^2+ X(25)^2 + X(26) ^2
511 N(10)=-204#+X(27) ^2 +X(28)^2+ X(29)^2 + X(30) ^2
515 N(8)=-68#+X(31) ^2 +X(32)^2+ X(33)^2 + X(34) ^2
519 N(3)= 5#^X(5)+5#^X(1) -3#^X(2) -7#^X(9)
522 N(5)= 5#^X(6)+5#^X(3) -3#^X(10) -7#^X(2)
533 N(7)= 5#^X(3)+5#^X(7) -3#^X(10) -7#^X(2)
602 N(11)= 5#^X(1)+5#^X(5) -3#^X(2) -7#^X(9)
603 N(15)= 13#^X(4)+7#^X(5) -3#^X(6) -5#^X(7)
604 N(18)= 17#^X(4)+7#^X(5) -3#^X(6) -5#^X(7)
605 N(21)= 3#^X(5)+5#^X(4) +7#^X(6) -11#^X(7)
611 N(41)=3# + X(1) -X(3)+2#* X(5) -X(7)-X(9)
613 N(43)=-8# + X(2)+(2#* X(4))^2# -6#* X(6)- X(8)+2#* X(10)
615 N(45)=16# + X(1) -3#* X(2)+4#* X(4) +X(6)-6#*X(7)+ X(8)-2#*X(9)
617 N(47)= -23# +5#* X(1)+2#* X(2)-8#* X(4)-3#* X(5)+4#* X(6)+X(7)-X(9)
619 N(49)=-31# +2#* X(1) +(X(2)+3#* X(4))^3 + (5#*X(7))^2-6#* X(8)+X(9)-9#* X(10)
621 N(51)=- 27# +(2#* X(1) + X(2))^2#+3#*X(3)-10#* X(5)-( X(6)+3#*X(7))^3#- X(8)-6#*X(9)
622 N(54)= X(11)^X(4)+ X(12)^ X(5) – X(13)^X(6)- X(14)^X(7)
623 N(64)= X(15)^X(1)+ X(16)^ X(5) – X(17)^X(2)- X(18)^X(9)
626 N(66)= 1 + X(19)^X(6)+ X(20)^ X(7) – X(21)^X(9)- X(22)^X(4)
629 N(67)= X(23)^X(6)+ X(24)^ X(7) – X(25)^X(9)- X(26)^X(4)
631 N(68)= X(27)^X(5)+ X(28)^ X(4) – X(29)^X(6)- X(30)^X(7)
632 N(79)= X(31)^X(5)+ X(32)^ X(4) + X(33)^X(7)- X(34)^X(9)
634 N(53)=9# +3#* X(1) +2#* X(2)-5#*X(3)- X(4)^4-2#* X(5) + X(6)+4#*X(7)-10#* X(8)+8#*X(9)
635 N(55)=24#+X(1) ^2#-2#*(X(2)+ X(4))^3 + X(5)-3#* X(6)-X(7)+4#*X(9) +15#* X(10)
711 N(69)=25# +3#* X(1) -(2#* X(2))^2+10#*X(3)-9#* X(4)+3#* X(5) + X(6)-2#*X(7)- 8#* X(8)+12#*X(9)-5#* X(10)
922 PD1A=-ABS(N(3))-ABS(N(5))-ABS(N(7))-ABS(N(11))-ABS(N(15))-ABS(N(18))-ABS(N(21))-ABS(N(37))-ABS(N(39))-ABS(N(41))-ABS(N(43))-ABS(N(45))-ABS(N(47))-ABS(N(49)) -ABS(N(51))-ABS(N(53))-ABS(N(54))-ABS(N(55))-ABS(N(69))-ABS(N(2))-ABS(N(64))-ABS(N(1))
925 PD1B=-ABS(N(0))-ABS(N(66)) -ABS( N(9))-ABS( N(67))-ABS(N(10)) -ABS(N(68)) -ABS( N (8) )-ABS( N(79) )
929 PD1=PD1A+PD1B
1111 IF PD1<=M THEN 1670
1452 M=PD1
1454 FOR KLX=1 TO 34
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1461 NN(8)=N(8)
1463 NN(79)=N(79)
1465 NN(9)=N(9)
1466 NN(10)=N(10)
1468 NN(0)=N(0)
1470 NN(1)=N(1)
1471 NN(2)=N(2)
1481 NN(3)=N(3)
1483 NN(5)=N(5)
1485 NN(7)=N(7)
1491 NN(11)=N(11)
1493 NN(15)=N(15)
1495 NN(18)=N(18)
1501 NN(21)=N(21)
1511 NN(37)=N(37)
1513 NN(39)=N(39)
1514 NN(41)=N(41)
1515 NN(43)=N(43)
1516 NN(45)=N(45)
1517 NN(47)=N(47)
1518 NN(49)=N(49)
1519 NN(51)=N(51)
1521 NN(53)=N(53)
1523 NN(55)=N(55)
1524 NN(69)=N(69)
1526 NN(54)=N(54)
1528 NN(64)=N(64)
1530 NN(66)=N(66)
1531 NN(67)=N(67)
1533 NN(68)=N(68)
1557 GOTO 128
1670 NEXT I
1889 IF M<-1 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10)
1903 PRINT A(11),A(12),A(13),A(14)
1904 PRINT A(15),A(16),A(17),A(18)
1905 PRINT A(19),A(20),A(21),A(22)
1906 PRINT A(23),A(24),A(25),A(26)
1916 PRINT A(27),A(28),A(29),A(30)
1917 PRINT A(31),A(32),A(33),A(34)
1936 PRINT M,JJJJ
1937 PRINT NN(9), NN(8), NN(10), NN(0),NN(1),NN(2),NN(3),NN(5),NN(7)
1938 PRINT NN(11),NN(15),NN(18)
1939 PRINT NN(21),NN(37)
1940 PRINT NN(39),NN(41),NN(43),NN(45),NN(47)
1941 PRINT NN(49),NN(51),NN(53),NN(54),NN(55),NN(64),NN(66),NN(67), NN(68),NN(69),NN(79)
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft’s GW-BASIC 3.11 interpreter for DOS. The output through JJJJ=-31285 is summarized below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

3 4 5 0 1
1 1 2 2 6
17 7 3 5
5 5 3 7
7 2 3 5
5 5 3 7
11 3 7 5
5 5 3 3
0 -31794
0 0 0 0 0
0 0 0 0
0 0 0
0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0

3 4 5 0 1
1 1 2 2 6
17 7 5 3
5 5 3 7
7 2 3 5
5 5 3 7
10 6 8 2
5 5 3 3
-1 -31643
0 0 0 0 0
0 0 0 0
0 0 0
0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0

3 4 5 0 1
1 1 2 2 6
17 7 5 3
5 5 3 7
7 2 3 5
5 5 3 7
8 10 2 6
5 5 3 3
-1 -31440
0 0 0 0 0
0 0 0 0
0 0 0
0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0

3 4 5 0 1
1 1 2 2 6
17 7 3 5
5 5 3 7
7 2 3 5
5 5 3 7
7 11 3 5
5 5 3 3
0 -31336
0 0 0 0 0
0 0 0 0
0 0 0
0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0

3 4 5 0 1
1 1 2 2 6
17 7 5 3
5 5 3 7
7 2 3 5
5 5 3 7
8 10 2 6
5 5 3 3
-1 -31302
0 0 0 0 0
0 0 0 0
0 0 0
0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0

3 4 5 0 1
1 1 2 2 6
17 7 5 3
5 5 3 7
7 2 3 5
5 5 3 7
11 3 5 7
5 5 3 3
0 -31285
0 0 0 0 0
0 0 0 0
0 0 0
0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0

Before this solution with M=0 at JJJJ=-31285 came, the message “Overflow” came numerous times.

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=-31285 was 37 minutes.

Acknowledgement

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

References

[1] S. Abraham, S. Sanyal, M. Sanglikar (2013), Finding Numerical Solutions of Diophantine Equations Using Ant Colony Optimization. Applied Mathematics and Computation 219 (2013), Pages 11376-11387.

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

[3] O. Perez, I. Amaya, R. Correa (2013), Numerical Solution of Certain Exponential and Non-linear Diophantine Systems of Equations by Using a Discrete Particles Swarm Optimization Algorithm. Applied Mathematics and Computation, Volume 225, 1 December 2013, Pages 737-746.

[4] Michel Waldschmidt, Open Diophantine Problems. Moscow Mathematical Journal, Volume 4, Number 1, January-March 2004, Pages 245-305.

Testing the Domino Method with a System of Four nonlinear Equations from the Literature

Jsun Yui Wong

The computer program listed below seeks to solve simultaneously the system of four nonlinear equations on page 44 of Greenspan and Casulli [14].  The simultaneous equations are:

– 10*X(1)     +5*X(2)     – EXP(X(1) )  =  0

5*   X(1)  -10*X(2)    +5*X(3)   -EXP(X(2) )   = 0

5*   X(2)  -10*X(3)    +5*X(4)   -EXP(X(3) )    = 0

5*X(3)   –  10*X(4) -EXP(X(4) )  )    =  0

In the following computer program, the right-hand side of the equation in line 181, which is 181 X(2)   =     (   10*X(1) +EXP(X(1) )  )/5, triggers the domino process, and there are four dominos, X(2), X(3), X(5), and X(6) shown in line 181, line 183, line 186, and line 188, respectively.  Generally speaking, when a domino is pushed, the following dominos are more or less pushed.

One notes that X(5) and X(6) are two additional variables defined in line 186 and line 188, respectively.

0 DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
100 FOR KLQ=1 TO 5
101 A(KLQ)=  FIX(-10+RND*20  )
102 NEXT KLQ
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 5
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
135 IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
159 FOR IPP=1 TO FIX(1+RND*3)
160 B=1+FIX(RND*5)
161       GOTO 166
162 REM   IF B>4 THEN 166 ELSE 163
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3)
164 GOTO 169
166 REM IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
167   IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
168 REM IF RND<.1 THEN X(B)=INT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=INT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
169 NEXT IPP
171 IF X(1)>80 THEN 1670
174 IF X(4)>80 THEN 1670
181 X(2)   =     (   10*X(1) +EXP(X(1) )  )/5
183 X(3)   =     (   10*X(4) +EXP(X(4) )  )/5
184 IF X(2)>80 THEN 1670
185 IF X(3)>80 THEN 1670
186 X(5)   =5*   X(1)  -10*X(2)    +5*X(3)   -EXP(X(2) )
188 X(6)   =5*   X(2)  -10*X(3)    +5*X(4)   -EXP(X(3) )
340 P=     -ABS( X(5)  )    -ABS( X(6) )
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 8
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-.00001 THEN 1999
1904 PRINT A(1),A(2),A(3)
1907 PRINT A(4),A(5),A(6)
1988 REM  PRINT A(7),A(8)
1989 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.  The complete output through JJJJ=-31998 is shown below.  What follows is a hand copy from the computer-monitor screen; below there is no rounding by hand.

-.2828138479755622   -.4148956819210858   -.4148956819210858
-.2828138479755622   -9.71445146547012D-17   -9.71445146547012D-17
-1.942890293094024D-16   -32000

-.2828138479756742   -.4148956819213269   -.4148956819212673
-.2828138479756465   1.101674307335543D-12   3.075040222455527D-13
-1.409178329581096D-12   -31999

-.2828138479755622   -.4148956819210858   -.4148956819210858
-.2828138479755622   -9.71445146547012D-17   -9.71445146547012D-17
-1.942890293094024D-16   -31998

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 from JJJJ=-32000 through JJJJ=-31998  was five seconds.

Acknowledgment

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

References

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

[2] A.-M. Bellido, Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems.  Numerical Algorithms 6 (1994) 317-351.

[3] L. G. Bullard, L. T. Biegler, Iterative Linear Programming Strategies for Constrained Simulation.  Computers and Chemical Engineering, Vol. 15, No. 4, pp. 239-254, 1991.

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

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

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

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

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

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

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

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

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

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

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

[15] Ian Jacques, Colin Judd, Numerical Analysis.  London: Chapman and Hall, 1987.

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

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

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

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

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

[21] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

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

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

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

[26] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design.  Cambridge University Press, 2000.

[27] M. J. D. Powell, A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Editor.  Gordon and Breach Science Publishers, 1970.

[28] John R. Rice, Numerical Methods, Software, and Analysis.  Academic Press, 1983.

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

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

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

[32] Terry E. Shoup, A Practical Guide to Computer Methods for Engineers.  Prentice-Hall, 1979.

[33] Terry E. Shoup, Applied Numerical Methods for the Microcomputer.  Prentice-Hall, 1984.

[34] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[35] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[36] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15/

[37] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05/

[38] Jsun Yui Wong (2011, July 27).   A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Alkylation-Process Model, Sixth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/07/27/

[39] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

The Domino Method Applied to Solving a Nonlinear System of Equations, Fourth Edition

Jsun Yui Wong

This is an update of the Third Edition [35] posted on May 5, 2011.  The computer program listed below seeks to solve simultaneously the nonlinear system of five equations on page p. 41 of Shoup [30] and on page 238 of Shoup [31].  The simultaneous equations are:

X(1)   +X(2)   +X(3)+X(4)    =31

X(1)*X(2)+ X(2)*X(3)    +  X(4)*x(5)      =58

X(1)   ^2  + X(3)*X(4)  -X(2)^2+   X(1)  *X(5)  =79

X(1)- X(2)*X(4)  +X(3)^2+X(5)   ^3 =17

X(1)*X(3)- X(2)^ 3  *X(5)  -X(5) *X(2)  +X(3)^2 *  X(4)  =234.

In the following computer program, the right-hand side of the equation in line 181, which is 181 X(4)   =31     -X(1)   -X(2)-X(3), triggers the domino process, and there are five dominos, X(4) through X(8) shown in line 181 through line 189.  Generally speaking, when a domino is pushed, the following dominos are more or less pushed.

One notes that X(6), X(7), and X(8) are three additional variables defined in line 185, line 187, and line 189, respectively.

0    DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
100 FOR KLQ=1 TO 5
101 A(KLQ)=  FIX(-10+RND*20  )
102 NEXT KLQ
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 5
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
159 FOR IPP=1 TO FIX(1+RND*3)
160 B=1+FIX(RND*5)
161       GOTO 166
162 REM   IF B>4 THEN 166 ELSE 163
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3)
164 GOTO 169
166 IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
167   IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
168 REM IF RND<.1 THEN X(B)=INT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=INT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
169 NEXT IPP
181 X(4)   =31     -X(1)   -X(2)-X(3)
182 IF ABS(X(4)  )<.0000001 THEN 1670
183 X(5)= (- X(1)*X(2)- X(2)*X(3)       +58       )/X(4)
185 X(6)=    X(1)   ^2  + X(3)*X(4)  -X(2)^2+   X(1)  *X(5)  -79
187 X(7)=    X(1)- X(2)*X(4)  +X(3)^2+X(5)   ^3 -17
189 X(8)=    X(1)*X(3)- X(2)^ 3  *X(5)  -X(5) *X(2)  +X(3)^2 *  X(4)  -234
340 P=     -ABS( X(6)  )    -ABS( X(7) )  -ABS( X(8) )
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 8
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-.00001 THEN 1999
1904 PRINT A(1),A(2),A(3)
1907 PRINT A(4),A(5),A(6)
1988 PRINT A(7),A(8)
1989 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.  The complete output through JJJJ=-31992 is shown below.  What follows is a hand copy from the computer-monitor screen; below there is no rounding by hand.

11.48325048551679   .8670331038364596   -3.540483936728002
22.19020034747475   2.303420323682036   -2.259278986116442D-08
9.225082031605325D-09   -9.221652419455495D-08
-1.240343960873247D-07   -31996

-13.86607940689277   -.5355828607236737   -2.075432820525316
47.4709508814176   1.041807616602306   6.099107867640896D-07
-5.34340744984263D-08   5.177639650355559D-09
-6.6852225009128715D-07   -31994

11.48325048241049   .8670331033907538   -3.540483935695608
22.19020034989436   2.303420323635648   -8.667949202845193D-08
3.643458423852053D-09   -1.985889523616924D-07
-2.889119428139964D-07   -31992

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 from JJJJ=-32000 through JJJJ=-31992  was ten seconds.

Acknowledgment

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

References

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

[2] A.-M. Bellido, Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems.  Numerical Algorithms 6 (1994) 317-351.

[3] L. G. Bullard, L. T. Biegler, Iterative Linear Programming Strategies for Constrained Simulation.  Computers and Chemical Engineering, Vol. 15, No. 4, pp. 239-254, 1991.

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

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

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

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

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

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

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

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

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

[13] Ian Jacques, Colin Judd, Numerical Analysis.  London: Chapman and Hall, 1987.

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

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

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

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

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

[19] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

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

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

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

[24] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design.  Cambridge University Press, 2000.

[25] M. J. D. Powell, A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Editor.  Gordon and Breach Science Publishers, 1970.

[26] John R. Rice, Numerical Methods, Software, and Analysis.  Academic Press, 1983.

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

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

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

[30] Terry E. Shoup, A Practical Guide to Computer Methods for Engineers.  Prentice-Hall, 1979.

[31] Terry E. Shoup, Applied Numerical Methods for the Microcomputer.  Prentice-Hall, 1984.

[32] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[33] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[34] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15/

[35] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05/

[36] Jsun Yui Wong (2011, July 27).   A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Alkylation-Process Model, Sixth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/07/27/

[37] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

Testing the Domino Method of General Integer Nonlinear Programming with a Nonlinear System of Four Equations, Third Edition

Jsun Yui Wong

The computer program listed below seeks to solve simultaneously the following nonlinear system of four equations; see Shoup [29, pp. 40-41]:

5*X(1)   +3*X(2)+X(3)  + X(4)   =15
X(1)*X(2)    +X(2)*X(3)    +X(3)*X(4)   =17
X(1)^2  +X(2) ^2 +X(3) ^2  -X(4)^2   =9
X(1)*X(3)+ X(2)*X(4)  +X(1)^3     =8

In the following computer program, the right-hand side of the equation in line 181, which is 181 X(4)   =15-5*X(1)   -3*X(2)-X(3), triggers the domino process, and there are four dominos, X(4),
X(5), X(6), and X(7) of line 181, line 183, line 185, and line 187, respectively.  Generally speaking, when a domino is pushed, the following dominos are more or less pushed.

One notes that X(5), X(6), and X(7) are three additional variables defined in line 183, line 185 and line 187, respectively.

While line 101 of the two preceding papers is 101 A(KLQ)=-10+RND*20, line 101 here is 101 A(KLQ)= FIX( -10+RND*20    ).

In contrast to the two preceding papers, here computations are based on line 163, which is
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3).  One uses this line if only integer solutions are of interest.

0 REM DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
100 FOR KLQ=1 TO 4
101 A(KLQ)= FIX( -10+RND*20    )
102 NEXT KLQ
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 4
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
159 FOR IPP=1 TO FIX(1+RND*3)
160 B=1+FIX(RND*4)
161 REM GOTO 166
162 REM IF B>4 THEN 166 ELSE 163
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3)
164 GOTO 169
166 IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
167 REM IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
168 IF RND<.1 THEN X(B)=INT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=INT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
169 NEXT IPP
181 X(4)   =15-5*X(1)   -3*X(2)-X(3)
183 X(5)= X(1)*X(2)    +X(2)*X(3)    +X(3)*X(4)         -17
185 X(6)=     X(1)^2  +X(2) ^2 +X(3) ^2  -X(4)^2   -9
187 X(7)=    X(1)*X(3)+ X(2)*X(4)  +X(1)^3     -8
340 P=-ABS( X(5)  )     -ABS( X(6)  )    -ABS( X(7) )
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 7
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-.0001 THEN 1999
1904 PRINT A(1),A(2),A(3)
1907 PRINT A(4),A(5),A(6)
1988 PRINT A(7),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft’s GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-31995 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1   1   4
3   0   0
0   0   -32000

1   1   4
3   0   0
0   0   -31996

1   1   4
3   0   0
0   0   -31995

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 from JJJJ=-32000 through JJJJ=-31995  was one second.

References

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

[2] L. G. Bullard, L. T. Biegler, Iterative Linear Programming Strategies for Constrained Simulation.  Computers and Chemical Engineering, Vol. 15, No. 4, pp. 239-254, 1991.

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

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

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

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

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

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

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

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

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

[12] Ian Jacques, Colin Judd, Numerical Analysis.  London: Chapman and Hall, 1987.

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

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

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

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

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

[18] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

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

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

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

[23] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design.  Cambridge University Press, 2000.

[24] M. J. D. Powell, A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Editor.  Gordon and Breach Science Publishers, 1970.

[25] John R. Rice, Numerical Methods, Software, and Analysis.  Academic Press, 1983.

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

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

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

[29] Terry E. Shoup, A Practical Guide to Computer Methods for Engineers.  Prentice-Hall, 1979.

[30] Terry E. Shoup, Applied Numerical Methods for the Microcomputer.  Prentice-Hall, 1984.

[31] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[32] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[33] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15/

[34] Jsun Yui Wong (2011, July 27).   A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Alkylation-Process Model, Sixth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/07/27/

[35] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

Testing the Domino Method of General Integer Nonlinear Programming with a Nonlinear System of Four Equations, Second Edition

Jsun Yui Wong

The computer program listed below seeks to solve simultaneously the following nonlinear system of four equations; see Shoup [29, pp. 40-41]:

5*X(1)   +3*X(2)+X(3)  + X(4)   =15
X(1)*X(2)    +X(2)*X(3)    +X(3)*X(4)   =17
X(1)^2  +X(2) ^2 +X(3) ^2  -X(4)^2   =9
X(1)*X(3)+ X(2)*X(4)  +X(1)^3     =8

In the following computer program, the right-hand side of the equation in line 181, which is 181 X(4)   =15-5*X(1)   -3*X(2)-X(3), triggers the domino process, and there are four dominos, X(4),
X(5), X(6), and X(7) of line 181, line 183, line 185, and line 187, respectively.  Generally speaking, when a domino is pushed, the following dominos are more or less pushed.

One notes X(5), X(6), and X(7) are three additional variables defined in line 183, line 185 and line 187, respectively.

While line 168 of the preceding paper is 168 IF RND<.1 THEN X(B)=INT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=INT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R, line 167 here is
167 IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R.  That is int versus cint.

0 REM DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
100 FOR KLQ=1 TO 4
101 A(KLQ)=-10+RND*20
102 NEXT KLQ
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 4
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
159 FOR IPP=1 TO FIX(1+RND*3)
160 B=1+FIX(RND*4)
161 GOTO 166
162 IF B>4 THEN 166 ELSE 163
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3)
164 GOTO 231
166 IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
167 IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
168 REM  IF RND<.1 THEN X(B)=INT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=INT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
169 NEXT IPP
181 X(4)   =15-5*X(1)   -3*X(2)-X(3)
183 X(5)= X(1)*X(2)    +X(2)*X(3)    +X(3)*X(4)         -17
185 X(6)=     X(1)^2  +X(2) ^2 +X(3) ^2  -X(4)^2   -9
187 X(7)=    X(1)*X(3)+ X(2)*X(4)  +X(1)^3     -8
340 P=-ABS( X(5)  )     -ABS( X(6)  )    -ABS( X(7) )
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 7
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-.0001 THEN 1999
1904 PRINT A(1),A(2),A(3)
1907 PRINT A(4),A(5),A(6)
1988 PRINT A(7),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft’s GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-30230 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1.000003   .9999988   3.999997
2.999995   -3.814697E-05   6.67572E-06
5.722046E-06   -5.054474E-05   -31388

1   1   4
3   0   0
0   0   -30715

1   .9999999   4
3.000001   1.907349E-06   -2.861023E-06
0   -4.768372E-06   -30230

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 from JJJJ=-32000 through JJJJ=-30230  was five minutes.

References

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

[2] L. G. Bullard, L. T. Biegler, Iterative Linear Programming Strategies for Constrained Simulation.  Computers and Chemical Engineering, Vol. 15, No. 4, pp. 239-254, 1991.

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

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

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

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

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

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

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

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

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

[12] Ian Jacques, Colin Judd, Numerical Analysis.  London: Chapman and Hall, 1987.

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

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

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

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

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

[18] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

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

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

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

[23] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design.  Cambridge University Press, 2000.

[24] M. J. D. Powell, A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Editor.  Gordon and Breach Science Publishers, 1970.

[25] John R. Rice, Numerical Methods, Software, and Analysis.  Academic Press, 1983.

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

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

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

[29] Terry E. Shoup, A Practical Guide to Computer Methods for Engineers.  Prentice-Hall, 1979.

[30] Terry E. Shoup, Applied Numerical Methods for the Microcomputer.  Prentice-Hall, 1984.

[31] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[32] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[33] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15/

[34] Jsun Yui Wong (2011, July 27).   A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Alkylation-Process Model, Sixth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/07/27/

[35] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

Testing the Domino Method of General Integer Nonlinear Programming with a Nonlinear System of Four Equations

Jsun Yui Wong

The computer program listed below seeks to solve simultaneously the following nonlinear system of four equations; see Shoup [29, pp. 40-41]:

5*X(1)   +3*X(2)+X(3)  + X(4)   =15
X(1)*X(2)    +X(2)*X(3)    +X(3)*X(4)   =17
X(1)^2  +X(2) ^2 +X(3) ^2  -X(4)^2   =9
X(1)*X(3)+ X(2)*X(4)  +X(1)^3     =8

In the following computer program, the right-hand side of the equation in line 181, which is 181 X(4)   =15-5*X(1)   -3*X(2)-X(3), triggers the domino process, and there are four dominos, X(4),
X(5), X(6), and X(7) of line 181, line 183, line 185, and line 187, respectively.  Generally speaking, when a domino is pushed, the following dominos are more or less pushed.

One notes X(5), X(6), and X(7) are three additional variables defined in line 183, line 185 and line 187, respectively.

0 REM DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
100 FOR KLQ=1 TO 4
101 A(KLQ)=-10+RND*20
102 NEXT KLQ
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 4
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
159 FOR IPP=1 TO FIX(1+RND*3)
160 B=1+FIX(RND*4)
161 GOTO 166
162 IF B>4 THEN 166 ELSE 163
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3)
164 GOTO 231
166 IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
167 REM IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
168 IF RND<.1 THEN X(B)=INT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=INT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
169 NEXT IPP
181 X(4)   =15-5*X(1)   -3*X(2)-X(3)
183 X(5)= X(1)*X(2)    +X(2)*X(3)    +X(3)*X(4)         -17
185 X(6)=     X(1)^2  +X(2) ^2 +X(3) ^2  -X(4)^2   -9
187 X(7)=    X(1)*X(3)+ X(2)*X(4)  +X(1)^3     -8
340 P=-ABS( X(5)  )     -ABS( X(6)  )    -ABS( X(7) )
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 7
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-.0001 THEN 1999
1904 PRINT A(1),A(2),A(3)
1907 PRINT A(4),A(5),A(6)
1988 PRINT A(7),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft’s GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-28898 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1   1   4
3   0   0
0   0   -31694

1   1   4
3   0   0
0   0   -31630

1   1   4
3   0   0
0   0   -28898

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 from JJJJ=-32000 through JJJJ=-28898  was nine minutes.

References

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

[2] L. G. Bullard, L. T. Biegler, Iterative Linear Programming Strategies for Constrained Simulation.  Computers and Chemical Engineering, Vol. 15, No. 4, pp. 239-254, 1991.

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

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

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

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

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

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

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

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

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

[12] Ian Jacques, Colin Judd, Numerical Analysis.  London: Chapman and Hall, 1987.

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

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

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

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

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

[18] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

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

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

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

[23] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design.  Cambridge University Press, 2000.

[24] M. J. D. Powell, A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Editor.  Gordon and Breach Science Publishers, 1970.

[25] John R. Rice, Numerical Methods, Software, and Analysis.  Academic Press, 1983.

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

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

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

[29] Terry E. Shoup, A Practical Guide to Computer Methods for Engineers.  Prentice-Hall, 1979.

[30] Terry E. Shoup, Applied Numerical Methods for the Microcomputer.  Prentice-Hall, 1984.

[31] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[32] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[33] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15/

[34] Jsun Yui Wong (2011, July 27).   A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Alkylation-Process Model, Sixth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/07/27/

[35] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

Testing the Domino Method of General Integer Nonlinear Programming with a Hydrocarbon Combustion Process

Jsun Yui Wong

The following computer program seeks to solve the following nonlinear system based on pages 146-147 of Meintjes and Morgan [20] and on pages 165-166 of Maranas and Floudas [18].  The problem is to solve simultaneously

X(1) *X(2)) +X(1)  -3*X(5)    =0

2*X(1)*X(2)  + X(1)  +2*9.614999E-07*X(2)^2   +  X(2)*X(3)^2  +   .0005451*X(2)*X(3)                +3.407E-05*X(2)*X(4)                +4.497E-07*X(2) -10*X(5)          =0

(  2*X(2)*X(3)^2+.0005451*X(2)*X(3) +  2*.193*X(3)^2  +.0004106*X(3)    )  -8*X(5)    =0

3.407E-05*X(2)*X(4)   +2*X(4)^2   -4*10*X(5)     =0

X(1)*X(2) +X(1) +9.614999E-07*X(2)^2  +X(2)*X(3)^2  +.0005451*X(2)*X(3)+3.407E-05*X(2)*X(4)+4.497E-07*X(2)+.193*X(3)^2  +  .0004106*X(3)+X(4)^2  -1    =0

In the following computer program, the right-hand side of the equation in line 171, which is 171 X(5)=     (  2*X(2)*X(3)^2+.0005451*X(2)*X(3) +  2*.193*X(3)^2  +.0004106*X(3)    )/8, triggers the domino process, and there are five dominos, X(5), X(1), X(4), X(6), and X(7) of line 171, line 173, line 177, line 181, and line 185, respectively.  In the present case, when X(5) is down/optimized, X(1) is down/optimized.   Generally speaking, when a domino is pushed, the following dominos are more or less pushed.

One notes that X(6) and X(7) are additional variable defined in line 181 and line 185, respectively.

0 DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
65 FOR J44=1 TO 5
66 LB(J44)=.0001
67 NEXT J44
78 FOR J44=1 TO 5
79 UB(J44)=100
80 NEXT J44
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
100 FOR J44=1 TO 5
101 A(J44)=.0001+RND*100
102 NEXT J44
126 IMAR=10+FIX(RND*5000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 5
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
159 FOR IPP=1 TO FIX(1+RND*3)
160 B=1+FIX(RND*5)
161 GOTO 166
162 IF B>4 THEN 166 ELSE 163
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3)
164 GOTO 231
166 IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
167 IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
169 NEXT IPP
171 X(5)=     (  2*X(2)*X(3)^2+.0005451*X(2)*X(3) +  2*.193*X(3)^2  +.0004106*X(3)    )/8
172 IF ABS(X(2)+1)<1E-10 THEN 1670
173 X(1)=(3*X(5)   )  /(  X(2)+1  )
176 IF  ABS   (   -3.407E-05*X(2)    )       <1E-10 THEN 1670
177 X(4)=     (  2*X(1)*X(2)  + X(1)  +2*9.614999E-07*X(2)^2   +  X(2)*X(3)^2  +   .0005451*X(2)*X(3) +4.497E-07*X(2) -10*X(5)   )/   (   -3.407E-05*X(2)  )
181 X(6)=3.407E-05*X(2)*X(4)   +2*X(4)^2   -4*10*X(5)
185 X(7)= X(1)*X(2) +X(1) +9.614999E-07*X(2)^2  +X(2)*X(3)^2  +.0005451*X(2)*X(3)+3.407E-05*X(2)*X(4)+4.497E-07*X(2)+.193*X(3)^2  +  .0004106*X(3)+X(4)^2  -1
281 FOR J78=1 TO 5
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
292 FOR J79=1 TO 5
293 IF X(J79)>UB(J79)  THEN 1670
294 NEXT J79
303 FOR J44=6 TO 7
305 IF ABS(X(J44))>0 THEN PX(J44)=-999999999#*ABS(X(J44)) ELSE PX(J44)=0
307 NEXT J44
320 PXT=0
321 FOR J44=6 TO 7
322 PXT=PXT+PX(J44)
323 NEXT J44
331 PD1=        +PXT
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 7
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-10000 THEN 1999
1904 PRINT A(1),A(2),A(3)
1907 PRINT A(4),A(5),A(6)
1908 PRINT A(7),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft’s GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-25021 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

3.114045551061453D-03   34.59862216992439   6.504118955434899D-02
.8593786706447932   3.695191033072355D-02   -8.473777235451507D-14
1.30452076449461D-06   -1304.520847927862   -31875

3.114032535127274D-03   34.59855521603445   .0650410547549879
.8593760661676057   3.695168638208533D-02   5.995204332975845D-15
-4.751578095874009D-06   -4751.578097117636   -25021

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 from JJJJ=-32000 through JJJJ=-25021  was 73 minutes.

References

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

[2] L. G. Bullard, L. T. Biegler, Iterative Linear Programming Strategies for Constrained Simulation.  Computers and Chemical Engineering, Vol. 15, No. 4, pp. 239-254, 1991.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[17] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

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

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

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

[22] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design.  Cambridge University Press, 2000.

[23] M. J. D. Powell, A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Editor.  Gordon and Breach Science Publishers, 1970.

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

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

[26] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[27] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[28] Jsun Yui Wong (2011, July 27).   A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Alkylation-Process Model, Sixth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/07/27/

[29] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

Testing the Domino Method of General Integer Nonlinear Programming with a Robot Kinematics Problem, Second Edition

Jsun Yui Wong

The following computer program seeks to solve the nonlinear system on page 207 of Kearfott [13].  The problem is to solve simultaneously

.004731*X(1)*X(3) -.3578*X(2)*X(3) -.1238*X(1) -.001637*X(2) -.9338*X(4) +1*X(7)  -.3571 )   =0

.2238*X(1)*X(3)   +.7623*X(2)*X(3) +  .2638*X(1)   -.07745*X(2) -.6734*X(4)  -.6022   =0

1*X(6)*X(8)+  .3578*X(1)   +.004731*X(2)  =0

-.7623*X(1)  +.2238 *X(2)  +.3461  =0

X(1)^2+X(2)^2-1   =0

X(3)^2+X(4)^2-1   =0

X(5)^2+X(6)^2-1   =0

X(7)^2+X(8)^2-1   =0.

One notes that the right-hand side of the equation in line 195 triggers a domino process and that X(10), X(11), X(12), and X(13) are additional variables defined in line 271 through line 277, respectively.

While line 268 of the preceding paper is 268  X(9)= (  .2238*X(1)*X(3)   +.7623*X(2)*X(3) +  .2638*X(1)         -.07745*X(2) -.6734*X(4)  -.6022  ), line 265 here is
265  X(4)= (  .2238*X(1)*X(3)   +.7623*X(2)*X(3) +  .2638*X(1)         -.07745*X(2)   -.6022  )       /.6734.

0 REM DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
65 FOR J44=1 TO 8
66 LB(J44)=-1
67 NEXT J44
78 FOR J44=1 TO 8
79 UB(J44)=1
80 NEXT J44
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
100 FOR J44=1 TO 8
101 A(J44)=-1+RND*2
102 NEXT J44
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 8
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
159 FOR IPP=1 TO FIX(1+RND*3)
160 B=1+FIX(RND*8)
161 GOTO 166
162 IF B>4 THEN 166 ELSE 163
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3)
164 GOTO 231
166 IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
167 IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
169 NEXT IPP
195  X(2)= (  -.7623*X(1)   +.3461  )  /  ( -.2238   )
262  IF ABS( X(6)    )   <1E-10 THEN 1670
263  X(8)= (  .3578*X(1)   +.004731*X(2)  )  /  (  -X(6)   )
265  X(4)= (  .2238*X(1)*X(3)   +.7623*X(2)*X(3) +  .2638*X(1)         -.07745*X(2)   -.6022  )       /.6734
266  X(7)= (  .004731*X(1)*X(3)   -.3578*X(2)*X(3)    -.1238*X(1)     -.001637*X(2)   -.9338*X(4)  -.3571 )   /   ( -1   )
268  REM   X(9)= (  .2238*X(1)*X(3)   +.7623*X(2)*X(3) +  .2638*X(1)         -.07745*X(2) -.6734*X(4)  -.6022  )
271 X(10)=X(1)^2+X(2)^2-1
273 X(11)=X(3)^2+X(4)^2-1
275 X(12)=X(5)^2+X(6)^2-1
277 X(13)=X(7)^2+X(8)^2-1
281 FOR J78=1 TO 8
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
292 FOR J79=1 TO 8
293 IF X(J79)>UB(J79)  THEN 1670
294 NEXT J79
303 FOR J44=9 TO 13
305 IF ABS(X(J44))>0 THEN PX(J44)=-999999999#*ABS(X(J44)) ELSE PX(J44)=0
307 NEXT J44
320 PXT=0
321 FOR J44=9 TO 13
322 PXT=PXT+PX(J44)
323 NEXT J44
331 PD1=        +PXT
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 13
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-120 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4)
1907 PRINT A(5),A(6),A(7),A(8)
1908 PRINT A(9),A(10),A(11),A(12)
1988 PRINT A(13),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft’s GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-31232 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

.6715543   .7409554   -.2396116   -.9708688
.9579171   .287045   -.527909   -.849301
0   -5.960465E-08   -5.960465E-08
0
0   -119.2093       -31574
.6715543   .7409554   -.2396117   -.9708688
-.9579171   .287045   -.527909   -.849301
0   -5.960465E-08   -5.960465E-08
0
0   -119.2093       -31495

.6715543   .7409554   -.2396117   -.9708688
.9579171   .287045   -.527909   -.849301
0   -5.960465E-08   -5.960465E-08
0
0   -119.2093       -31433

.6715543   .7409554   -.2396117   -.9708688
-.9579171   .287045   -.527909   -.849301
0   -5.960465E-08   -5.960465E-08
0
0   -119.2093       -31232

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 from JJJJ=-32000 through JJJJ=-31232  was three minutes.

References

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

[2] L. G. Bullard, L. T. Biegler, Iterative Linear Programming Strategies for Constrained Simulation.  Computers and Chemical Engineering, Vol. 15, No. 4, pp. 239-254, 1991.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[17] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

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

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

[21] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design.  Cambridge University Press, 2000.

[22] M. J. D. Powell, A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Editor.  Gordon and Breach Science Publishers, 1970.

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

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

[25] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[26] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[27] Jsun Yui Wong (2011, July 27).   A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Alkylation-Process Model, Sixth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/07/27/

[28] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

Testing the Domino Method of General Integer Nonlinear Programming with a Robot Kinematics Problem

Jsun Yui Wong

The following computer program seeks to solve the nonlinear system on page 207 of Kearfott [13].  The problem is to solve simultaneously

.004731*X(1)*X(3) -.3578*X(2)*X(3) -.1238*X(1) -.001637*X(2) -.9338*X(4) +1*X(7)  -.3571 )   =0

.2238*X(1)*X(3)   +.7623*X(2)*X(3) +  .2638*X(1)   -.07745*X(2) -.6734*X(4)  -.6022   =0

1*X(6)*X(8)+  .3578*X(1)   +.004731*X(2)  =0

-.7623*X(1)  +.2238 *X(2)  +.3461  =0

X(1)^2+X(2)^2-1   =0

X(3)^2+X(4)^2-1   =0

X(5)^2+X(6)^2-1   =0

X(7)^2+X(8)^2-1   =0.

One notes that in the following computer program, X(9), X(10), X(11), X(12), and X(13) are additional variables defined in line 268 through line 277, respectively.

0 REM DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
65 FOR J44=1 TO 8
66 LB(J44)=-1
67 NEXT J44
78 FOR J44=1 TO 8
79 UB(J44)=1
80 NEXT J44
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
100 FOR J44=1 TO 8
101 A(J44)=-1+RND*2
102 NEXT J44
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 8
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
159 FOR IPP=1 TO FIX(1+RND*3)
160 B=1+FIX(RND*8)
161 GOTO 166
162 IF B>4 THEN 166 ELSE 163
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3)
164 GOTO 231
166 IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
167 IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
169 NEXT IPP
195  X(2)= (  -.7623*X(1)   +.3461  )  /  ( -.2238   )
262  IF ABS( X(6)    )   <1E-10 THEN 1670
263  X(8)= (  .3578*X(1)   +.004731*X(2)  )  /  (  -X(6)   )
266  X(7)= (  .004731*X(1)*X(3)   -.3578*X(2)*X(3)    -.1238*X(1)     -.001637*X(2)   -.9338*X(4)  -.3571 )   /   ( -1   )
268  X(9)= (  .2238*X(1)*X(3)   +.7623*X(2)*X(3) +  .2638*X(1)         -.07745*X(2) -.6734*X(4)  -.6022  )
271 X(10)=X(1)^2+X(2)^2-1
273 X(11)=X(3)^2+X(4)^2-1
275 X(12)=X(5)^2+X(6)^2-1
277 X(13)=X(7)^2+X(8)^2-1
281 FOR J78=1 TO 8
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
292 FOR J79=1 TO 8
293 IF X(J79)>UB(J79)  THEN 1670
294 NEXT J79
303 FOR J44=9 TO 13
305 IF ABS(X(J44))>0 THEN PX(J44)=-999999999#*ABS(X(J44)) ELSE PX(J44)=0
307 NEXT J44
320 PXT=0
321 FOR J44=9 TO 13
322 PXT=PXT+PX(J44)
323 NEXT J44
331 PD1=        +PXT
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 13
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-120 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4)
1907 PRINT A(5),A(6),A(7),A(8)
1908 PRINT A(9),A(10),A(11),A(12)
1988 PRINT A(13),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft’s GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-27763 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

.6715543   .7409554   -.2396118   -.9708688
.9579171   -.287045   -.527909   .849301
-5.960465E-08   -5.960465E-08   0
0
0   -119.2093       -31038

.6715543   .7409554   -.2396117   -.9708688
-.9579171   .287045   -.527909   -.849301
0   -5.960465E-08   0   0
0   -59.60465   -30732

.6715543   .7409554   -.2396117   -.9708688
.9579171   -.287045   -.527909   .849301
0   -5.960465E-08   -5.960465E-08
0
0   -119.2093       -29317

.6715543   .7409554   -.2396116   -.9708688
.9579171   .287045   -.527909   -.849301
0   -5.960465E-08   0   0
0   -59.60465   -27763

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 from JJJJ=-32000 through JJJJ=-27763  was 19 minutes.

References

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

[2] L. G. Bullard, L. T. Biegler, Iterative Linear Programming Strategies for Constrained Simulation.  Computers and Chemical Engineering, Vol. 15, No. 4, pp. 239-254, 1991.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[17] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

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

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

[21] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design.  Cambridge University Press, 2000.

[22] M. J. D. Powell, A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Editor.  Taylor and Francis, Inc., 1970.

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

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

[25] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[26] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[27] Jsun Yui Wong (2011, July 27).   A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Alkylation-Process Model, Sixth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/07/27/

[28] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

Testing the Domino Method of General Integer Nonlinear Programming with Brown’s Almost Linear System of Equations

Jsun Yui Wong

The following computer program seeks to solve the nonlinear system on page 660 of Floudas [11].  The problem is to solve simultaneously

2* X(1) +  X(2)   +    X(3)    +   X(4)     +X(5)     -6=0
X(1) +2*X(2)   +    X(3)    +   X(4)     +X(5)     -6=0
X(1) +  X(2)   + 2* X(3)    +   X(4)     +X(5)     -6=0
X(1) +  X(2)   +    X(3)    + 2*X(4)     +X(5)     -6=0
X(1) *  X(2)  * X(3) *X(4) *X(5)     -1              =0.

“It is a difficult problem to solve because it involves two distinct solutions which are very close to each other,” Floudas [11, p. 660].

One notes that in the following computer program, X(6), X(7), X(8), and X(9) are additional variables defined in line 222, line 223, line 224, and line 225, respectively.

0 REM DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
65 FOR J44=1 TO 5
66 LB(J44)=-100
67 NEXT J44
78 FOR J44=1 TO 5
79 UB(J44)=100
80 NEXT J44
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
100 FOR J44=1 TO 5
101 A(J44)=-100+RND*200
102 NEXT J44
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 5
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
159 FOR IPP=1 TO FIX(1+RND*3)
160 B=1+FIX(RND*5)
161 GOTO 166
162 IF B>4 THEN 166 ELSE 163
163 IF RND<.5 THEN X(B)=A(B)-FIX(1+RND*3) ELSE X(B)=A(B)+FIX(1+RND*3)
164 GOTO 231
166 IF RND<.9 THEN R=(1-RND*2)*A(B) ELSE IF RND<.5 THEN R=(1-RND*2)*(A(B)  -.1) ELSE R=(1-RND*2)*(A(B) +.1)
167 IF RND<.1 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.1 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(RND^(RND*10) )*R
169 NEXT IPP
211   IF ABS(X(1))<.0000001 THEN 1670
212   IF ABS(X(2))<.0000001 THEN 1670
213   IF ABS(X(3))<.0000001 THEN 1670
214   IF ABS(X(4))<.0000001 THEN 1670
221 X(5)=(1 )  /(   X(1) *  X(2)  * X(3) *X(4)  )
222 X(6)=2* X(1) +  X(2)   +    X(3)    +   X(4)     +X(5)     -6
223 X(7)=   X(1) +2*X(2)   +    X(3)    +   X(4)     +X(5)     -6
224 X(8)=   X(1) +  X(2)   + 2* X(3)    +   X(4)     +X(5)     -6
225 X(9)=   X(1) +  X(2)   +    X(3)    + 2*X(4)     +X(5)     -6
281 FOR J78=1 TO 5
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
292 FOR J79=1 TO 5
293 IF X(J79)>UB(J79)  THEN 1670
294 NEXT J79
303 FOR J44=6 TO 9
305 IF ABS(X(J44))>0 THEN PX(J44)=-999999999#*ABS(X(J44)) ELSE PX(J44)=0
307 NEXT J44
320 PXT=0
321 FOR J44=6 TO 9
322 PXT=PXT+PX(J44)
323 NEXT J44
331 PD1=        +PXT
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 9
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-100000! THEN 1999
1904 PRINT A(1),A(2),A(3)
1907 PRINT A(4),A(5),A(6)
1908 PRINT A(7),A(8),A(9)
1988 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.  Some candidate solutions through JJJJ=-31855 are shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1   .9999996   .9999998
.9999996   1.000001   0
0   0   0
0   -32000

1     .9999999   1.000001
1   .9999991   0
0   4.768372E-07   0
-476.8372   -31996

.9163503   .9163493   .9163511
.9163608   1.418238   -4.768372E-07
-1.430512E-06   4.768372E-07   9.536743E-06
-11920.93   -31985
.
.
.
.916394   .9163932   .9163084
.916392   1.41812   1.430512E-06
4.768372E-07   -8.392334E-05   -4.768372E-07
-86307.52   -31929
.
.
.
.9163524   .9163558   .9163549
.9163558   1.418227   -1.907349E-06
9.536743E-07   0   9.536743E-07
-3814.697   -31855

Many other candidate solutions with A(1)>.95 were produced but are not 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 from JJJJ=-32000 through JJJJ=-31855 was two minutes.

References

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

[2] L. G. Bullard, L. T. Biegler, Iterative Linear Programming Strategies for Constrained Simulation.  Computers and Chemical Engineering, Vol. 15, No. 4, pp. 239-254, 1991.

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

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

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

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

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

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

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

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

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

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

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

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

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

[16] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

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

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

[20] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design.  Cambridge University Press, 2000.

[21] M. J. D. Powell, A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Editor.  Taylor and Francis, Inc., 1970.

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

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

[24] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[25] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[26] Jsun Yui Wong (2011, July 27).   A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Alkylation-Process Model, Sixth Edition.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2011/07/27/

[27] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from https://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/