The Domino Method of General Integer Nonlinear Programming Applied to Waste Treatment Plant Design

Jsun Yui Wong

The computer program below tries to solve the waste treatment plant design problem in Ballard, Jelinek, and Schinzinger [1].  Line 181 through line 1111 of the following computer program partly describe the problem.

The following computer program is modeled after the nuclear-chain-reaction picture on page 336 of the World Book Dictionary [2] and after the domino method of solving nonlinear systems of equations [12].  Line 251 through line 459 are illustrative.  Domino one is line 251's X(4), the slack variable of the given constraint.  

0 DEFDBL A-Z
2 DEFINT I,J,K
3 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(111),PS(33)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
41 FOR J44=1 TO 3
42 A(J44)=RND
43 NEXT J44
126 IMAR=10+FIX(RND*5000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 3
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*2))
181 J=1+FIX(RND*3)
182 REM      IF J>4 THEN 183 ELSE 191
183  R=(1-RND*2)*A(J)
185 REM IF RND<.25 THEN PA=(RND)*R ELSE IF RND<.33 THEN PA=(RND^3)*R ELSE IF RND<.5 THEN PA=(RND^5)*R ELSE PA=(RND^7)*R
187    X(J)=A(J)+  (RND^(RND*10))*R
188 GOTO 192
189 REM   X(J)=A(J)+PA
190 REM X(J)=A(J)+FIX(RND*2 )-FIX(RND*2)
191 X(J)=A(J)+FIX(RND*3)-FIX(RND*3)
192 NEXT IPP
228    FOR J44=1 TO 3
230    IF X(J44)<.000001 THEN 1670
231    NEXT J44
251 X(4)=1 -.0000033333333#*X(3)
331 IF  X(4) <0 THEN PS1=ABS(X(4)) ELSE PS1=0
332 REM   IF  X(8) <0 THEN PS2=ABS(X(8)) ELSE PS2=0
403 POBA2= -.000000000021#*X(2)^2.55-62900000#*X(2)^5/X(3)^6  -85000000000#/(X(2)*X(3)^.2*X(1)^2    )-160000#*X(1)^2.5    *X(3)/X(2)
411 POBA= POBA2
459 POB1=POBA -999999999#*( + PS1 )
463 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1453 PPOBA=POBA
1454 FOR KLX=1 TO 4
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-999999! THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),M,JJJJ,PPOBA
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  The complete output through JJJJ=-31998 is shown below.  What follows is a hand copy of the output on the computer-monitor screen; immediately below there is no rounding by hand.

.6168611557253477    581517.9425713552   300000.00299089
3.036670914724482D-11   -71758.44587308557   -32000
-71758.44587308557 

.6168611552372779    581517.9448577983   300000.003
2.081668171172169D-16   -71758.44587260198   -31999
-71758.44587260198  

.6168611548868333    581517.9461914927   300000.0029995419
1.527084014796287D-12   -71758.4458726263   -31998
-71758.4458726263   

On a personal computer with an Intel 2.66 chip and the IBM basica/D interpreter, version GW BASIC 3.11,  the throughput time from JJJJ=-32000 through JJJJ=-31998 was thirteen seconds.

References

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

[2] Clarence L. Barnhart, Robert K. Barnhart (Editors).  The World Book Dictionary, 1993 World Book, Inc., a Scott Fetzer company, Chicago London Sydney Toronto.

[3] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., Copyright 1980.

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

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

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

[7] 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.
 
[8] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Boston: Springer, 2006.

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

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

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

[12] Jsun Yui Wong (2011, April 17).  The Domino Method of Solving Nonlinear Systems of Equations.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/04/17/