The computer program listed below seeks to solve Exercise 8.2 of Conley [4, p. 177]. It is to solve the following simultaneous equations for 0 <= X(i) <= 200 and the X(i)'s are whole numbers:
X(1)^2 + 3*X(2) + 5*X(4) +6*X(3) + 7 *X(6) = 5492
2*X(1)*X(2)*X(3) + X(4) +X(5) +X(6) = 638213
X(1) + X(2) + X(3)+9*X(4) +11*X(5) + X(6) = 2787
3* X(1) + 4* X(2) + X(3) + X(4) +6* X(5) +7* X(6) = 1768
13*X(1) + X(2)*X(3)*X(4) + X(5) * X(6) = 844252
While line 159 of the preceding paper is 159 FOR IPP=1 TO FIX(1+RND*3), line 159 here is 159 FOR IPP=1 TO FIX(1+RND*4).
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 6
101 A(KLQ)=FIX(RND*200)
102 NEXT KLQ
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 6
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
159 FOR IPP=1 TO FIX(1+RND*4)
160 B=1+FIX(RND*6)
161 REM IF B>7 THEN 162 ELSE 167
162 IF RND<.5 THEN X(B)=A(B)-FIX(RND*4) ELSE X(B)=A(B)+FIX(RND*4)
163 GOTO 179
167 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)
177 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
178 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
179 NEXT IPP
180 X(6)=( 5492- X(1)^2 - 3*X(2) -5*X(4) -6*X(3) )/7
181 X(5)= 638213! - 2*X(1)*X(2)*X(3) - X(4) -X(6)
183 REM X(6)= + 2* X(1)^2+ X(2) + X(3) + X(4) -229
185 X(7)= X(1) + X(2) + X(3)+9*X(4) +11*X(5) + X(6)-2787
187 REM X(8)= - 200+ X(1) + X(2) +X(3)
189 X(8)= 3* X(1) + 4* X(2) + X(3) + X(4) +6* X(5) +7* X(6)-1768
193 X(9)= 13*X(1) + X(2) * X(3) * X(4) + X(5) * X(6)-844252!
199 REM GOTO 267
221 FOR J44=1 TO 6
222 IF X(J44)<0 THEN 1670
223 IF X(J44)>200 THEN 1670
224 NEXT J44
267 FOR J44= 7 TO 9
268 IF ABS(X(J44))>0 THEN X(J44)=ABS(X(J44)) ELSE X(J44)=0
269 NEXT J44
321 PENSUM=-X(7)-X(8)-X(9)
342 P=(PENSUM)
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<-300 THEN 1999
1904 PRINT A(1),A(2),A(3)
1907 PRINT A(4),A(5),A(6),A(7)
1989 PRINT A(8),A(9),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 from JJJJ=-32000 through JJJJ=32000 is shown below. What follows is a hand copy from the computer-monitor screen; below there is no rounding by hand.
58 47 117
152 102 75 0
0 0 0 -24955
58 47 117
152 102 75 0
0 0 0 -12526
58 47 117
152 102 75 0
0 0 0 20945
58 47 117
152 102 75 0
0 0 0 23890
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 this run from JJJJ=-32000 through JJJJ=32000 was 28 minutes.
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] O. Berman, N. Ashrafi, Optimization Models for Reliability of Modular Software Systems. IEEE Transactions on Software Engineering, 19 (11): 1119-1123, 1993.
[3] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition. Brooks/Cole 2011.
{4} Wiliam Conley, Computer Optimization Techniques, Revised Edition. New York/Princeton: Petrocelli Books, Inc., 1984.
[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 Enginerring. Addison-Wesley Publishing Company, 1988.
[15] 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.
[16] R. Baker Kearfott, Some Tests of Generalized Bisection. ACM Transactions on Mathematical Software, Vol.13, No. 3, September 1987, pages 197-220.
[17] G. R. Kocis, I. E. Grossmann, Relaxation Strategy for the Structural Optimization of Process Flow Sheets. Ind. Eng. Chem. Res., 26 (9):1869 (1987).
[18] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[19] 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.
[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] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis. Cambridge University Press, 2009.
[25] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition. Cambridge University Press, 2000.
[26] 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.
[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. Vogel, John Wiley and Sons, pp. 163-213.
[30] Terry E. Shoup, A Practical Guide to Computer Methods for Engineers. Prentice-Hall, 1979.
[31] L.-W. Tsai, A. P. Morgan, Solving the Kinematics of the Most General Six- and Five-Degree-of Freedom Manipulators by Continuation Methods. Journal of Mechanisms, Transmissions, and Automation in Design, June 1985, Vol. 107, pp. 189-200.
[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 http://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 http://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 http://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 http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/
[38] Jsun Yui Wong (2013, January 14). The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition. Retrieved from http://myblogsubstance.typepad.com/substance/2013/01/
[39] Jsun Yui Wong (2013, January 24). The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24/