The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Continuous Variables

Jsun Yui Wong

The computer program below tries to solve the Duffin, Peterson, and Zener 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 [11].  Line 301 through line 459 are illustrative.  Line 301's X(4), a slack variable, is proxy domino one.

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     GOTO 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
189 REM   X(J)=A(J)+PA
190 REM  X(J)=A(J)+FIX(RND*2 )-FIX(RND*2)
191 REM X(J)=A(J)+FIX(RND*3)-FIX(RND*3)
192 NEXT IPP
228    FOR J44=1 TO 3
230    IF X(J44)<1E-09 THEN 1670
231    NEXT J44
301 X(4)=1-440.98*X(1)-28460000#*X(1)^2-615840000000000#*X(1)^2*X(2)-370.18*X(3)-54474000000#*X(3)^2-3223600#*X(1)*X(3)-29200000000#*X(2)*X(3)-44712#*X(2)-379640000000#*X(2)^2-4287600000#*X(1)*X(2)
331 IF  X(4) <0 THEN PS1=ABS(X(4)) ELSE PS1=0
402 POBA2=-1/(X(1)^2*X(2)*X(3)    )
411 POBA= POBA2
459 POB1=POBA -1D+21*( + 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<-5.52532D+20 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=-31973 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.

5.630587680387436D-05   2.449724195244166D-07   2.330336022283708D-06
-3.226585665316861D-16   -5.525312022758336D+20   -31999
-5.525312022758333D+20

5.625444709023255D-05   2.452647001363708D-07   2.331817658777324D-06
-6.749982517373354D-14   -5.52530995189131D+20   -31973
-5.525309951890635D+20

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=-31973 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, 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] Jsun Yui Wong (2011, April 17).  The Domino Method of Solving Nonlinear Systems of Equations.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/04/17/