The Domino Method of General Integer Nonlinear Programming Applied to an Electrical Resistance Network

Jsun Yui Wong

The computer program below tries to solve the electrical resistance network problem in Conley [4].  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 [13].  Line 310, which is 310 X(11)=1/ (1/X(1)+1/X(2) )   + 1/(1/X(4)+1/X(5)+1/X(6))  + 1/(1/X(9)+1/X(10))-122, through line 411 are illustrative.  Here X(11) through X(15) of line 310 through line 350, respectively, are proxy domino one through proxy domino five, respectively.  When X(11) is optimized/pushed-down, X(12) is relatively easily optimized/pushed-down.  Similarly, X(13), X(14), and X(15) are relatively easily optimized/pushed-down.

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 10
42 A(J44)=FIX(RND*400)
43 NEXT J44
126 IMAR=10+FIX(RND*32000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 10
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*9))
181 J=1+FIX(RND*10)
183  R=(1-RND*2)*A(J)
185  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
189  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
197    FOR J44=1 TO 10
201    IF X(J44)>400 THEN 1670
202    IF X(J44)<1 THEN 1670
203    NEXT J44
310 X(11)=1/ (1/X(1)+1/X(2) )   + 1/(1/X(4)+1/X(5)+1/X(6))  + 1/(1/X(9)+1/X(10))-122
320 X(12)=1/ (1/X(1)+1/X(2) )   + 1/(1/X(5)+1/X(6)+1/X(7))  + 1/(1/X(9)+1/X(10))-112
330 X(13)=1/ (1/X(2)+1/X(3) )   + 1/(1/X(4)+1/X(5)+1/X(6))  + 1/(1/X(9)+1/X(10))-105
340 X(14)=1/ (1/X(2)+1/X(3) )   + 1/(1/X(5)+1/X(6)+1/X(7))  + 1/(1/X(9)+1/X(10))-95
350 X(15)=1/ (1/X(1)+1/X(2)+1/X(3) )   + 1/(1/X(4)+1/X(5)+1/X(6)+1/X(7))  + 1/(1/X(8)+1/X(9)+1/X(10))-80
411 POBA= -ABS(X(11))-ABS(X(12))-ABS(X(13))-ABS(X(14))- ABS(X(15))
459 POB1=POBA
463 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 15
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-1E-09 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),A(5)
1901 PRINT A(6),A(7),A(8),A(9),A(10)
1903 PRINT A(11),A(12),A(13),A(14),A(15)
1905 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  The complete output through JJJJ=-31993 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.

308.0525920714426   106.1138329576789   148.7127150354939
114.8101109168384   325.5764279450349   
17.37446729712957   6.04225184664533   154.9598328175128   
92.12151121457207   41.58507056766254  
-3.552713678800501D-14   1.522337811366015D-12   -8.046896482483135D-13
7.51398943066306D-13   -1.412203687323199D-12
-4.526157226791838D-12   -31997

77.57292448449295   96.15627009813874   35.51428817811416
397.8358477378793   49.75476332781962   
277.8037481413037   84.56761194556611   211.1392693013211   
58.53767634163486   135.8968557621608  
-2.401634446869139D-12   -1.392663762089796D-12   0
1.0089770684779343D-12   9.013234603116871D-12
-1.381650349685515D-11   -31993

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=-31993 was ten 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 (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] William Conley, An Electrical Resistance Network.  International Journal of Mathematical Education in Science and Technology, Volume 14, Number 3 (1983), pp. 287-291.

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

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

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

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

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

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

[12] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge, UK: Cambridge University Press, 2000.
 
[13] Jsun Yui Wong (2011, April 17).  The Domino Method of Solving Nonlinear Systems of Equations.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/04/17/
 
[14] Jsun Yui Wong (2011, July 2).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Transformer Design Model with Integer Variables and Continuous Variables, Fourth Edition. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/07/02/