Testing the Domino Method of General Nonlinear Integer Programming with a Problem Involving a Nonlinear Objective Function, One Nonlinear Inequality Constraint, Five Linear Inequality Constraints, and Three Big Integer Variables, Second Edition

Jsun Yui Wong

The computer program below tries to solve Example 5.1 on page 119-120 of Conley [2].  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 [1] and after the domino method of solving nonlinear systems of equations [10].  Line 221, which is 221 X(6)=-X(1)-X(2)-2*X(3)+2000 from one of the given constraints, through line 459 are illustrative.  Here X(4) through X(9) of line 219 through line 244, respectively, are proxy domino one through proxy domino six, respectively.  When X(4) is optimized/pushed-down, X(5) is relatively easily optimized/pushed-down.  Similarly, X(6), X(7), x(8), and X(9) 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 3
42 A(J44)=FIX(RND*1000)
43 NEXT J44
126 IMAR=10+FIX(RND*2000)
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 GOTO 191
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     X(J)=A(J)+FIX(RND*3)-FIX(RND*3)
192 NEXT IPP
197    FOR J44=1 TO 3
201    IF X(J44)>999 THEN 1670
202    IF X(J44)<0 THEN 1670
203    NEXT J44
219 X(4)=-X(1)-17*X(2)+8000
220 X(5)=-X(2)-5*X(3)+4000
221 X(6)=-X(1)-X(2)-2*X(3)+2000
224 X(7)=X(1) +X(2)   +X(3)  -200
243 X(8)= X(1)+7*X(2)+2*X(3)     -200
244 X(9)= X(1)^2+  X(2)*  X(3)    -900
250 FOR J44=4 TO 9
251 IF X(J44)<0 THEN PR(J44)=ABS(X(J44)) ELSE PR(J44)=0
255 NEXT J44
402 POBA2=-6*X(1)^2-18*X(2)^2-7*X(3)^2+2*X(1)+16*X(2)+31*X(3)+12*X(1)*X(2)*X(3)
411 POBA= POBA2
459 POB1=POBA -999999999#*(PR(4)+PR(5)+PR(6)+PR(7)+PR(8)+PR(9)  )
463 P1NEWMAY=POB1
466 P=P1NEWMAY
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<1573000000# THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9)
1903 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=-31730 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.

758   426   408   0   1534
0   1392   4356   747472
1573099348   -31970

775   425   400   0   1575
0   1400   4350   769725
1573045750   -31827

775   425   400   0   1575
0   1400   4350   769725
1573045750   -31813

758   426   408   0   1534
0   1392   4356   747472
1573099348   -31805

775   425   400   0   1575
0   1400   4350   769725
1573045750   -31751

758   426   408   0   1534
0   1392   4356   747472
1573099348   -31740

758   426   408   0   1534
0   1392   4356   747472
1573099348   -31730

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=-31730 was five minutes.

References

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

[2] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., Copyright 1984.

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

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

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

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

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

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