The following computer program seeks to solve the nonlinear system on page 206 of Kearfott [13]. The problem is to solve simultaneously
-1.697E+07*X(2)*X(4) +2.177E+07*X(2) +.55*X(1)*X(4) +.45*X(1) -1!*X(4) =0
1.585E+14*X(2) * X(4)+4.126E+07*X(1)*X(3) -8285000!*X(1)*X(4) +2.284E+07*X(3)*X(4) -1.918E+07*X(3) +48.4*X(4) -27.73 =0
X(1)^2 -X(2) =0
X(4)^2 -X(3) =0
In the following computer program, the right-hand side of the equation in line 175, which is 175 X(2)=X(1)^2, triggers the domino process, and there are four dominos, X(2), X(4), X(3), and X(5) of line 175, line 181, line 187, and line 190, respectively. In the present case, when X(2) is down/optimized, X(4) is down/optimized, X(3) is down/optimized, and X(5) is down/optimized. Generally speaking, when a domino is pushed, the following dominos are more or less pushed.
One notes that X(5) is an additional variable defined in line 190.
While line 126 of the preceding paper is 126 IMAR=10+FIX(RND*5000), line 126 here is
126 IMAR=10+FIX(RND*1000).
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 4
66 LB(J44)=0
67 NEXT J44
78 FOR J44=1 TO 4
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 4
101 A(J44)=RND
102 NEXT J44
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
169 NEXT IPP
175 X(2)=X(1)^2
181 X(4)=( -2.177E+07*X(2)-.45*X(1) )/ (-1.697E+07*X(2) +.55*X(1) -1! )
187 X(3)= X(4)^2
190 X(5)=+1.585E+14*X(2)*X(4) +4.126E+07*X(1)*X(3) -8285000!*X(1)*X(4) +2.284E+07*X(3)*X(4) -1.918E+07*X(3) +48.4*X(4) -27.73
281 FOR J78=1 TO 4
282 IF X(J78)<LB(J78) THEN 1670
283 NEXT J78
292 FOR J79=1 TO 4
293 IF X(J79)>UB(J79) THEN 1670
294 NEXT J79
303 FOR J44=5 TO 5
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=5 TO 5
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 5
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-1000 THEN 1999
1904 PRINT A(1),A(2),A(3)
1907 PRINT A(4),A(5),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=-17288 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
1.587988022244009D-04 2.521705958790438D-08 .1478617923490562
.3845280124373986 2.637155782636569D-08 -26.37155779999413
-26895
1.587988022243708D-04 2.521705958789483D-08 .1478617923489777
.3845280124372966 -4.927292982515041D-07 -492.7292977587748
-23205
1.58798802224417D-04 2.521705958790951D-08 .1478617923490983
.3845280124374534 3.051889043703682D-07 -305.1889040651793
-17844
1.587988022243992D-04 2.521705958790386D-08 .1478617923490519
.3845280124373931 -1.568385421535368D-09 -1.568385419966982
-17288
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=-17288 was fifteen 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 http://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 http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/