Testing the Domino Method of General Integer Nonlinear Programming with a Minimization Problem Involving a Nonlinear Objective Function, One Nonlinear Equality Constraint, One Linear Equality Constraint, and Three Continuous Variables

Jsun Yui Wong

The following computer program tries to solve Example 3.9 of Conley [2, p. 55].  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 193 through line 459 are illustrative.  Line 193, which is 193 X(2)=100-3*X(1)-6*X(3), is an expression of the given linear equality constraint.  X(2) is proxy domino one.

0 REM 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*100)
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)
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*51)-FIX(RND*51)
192 NEXT IPP
193 X(2)  = 100-3*X(1)       -6*  X(3)
211 FOR J44=1 TO 4
212 IF X(J44)<0 THEN 1670
213 NEXT J44
351 PS(2)=X(1)+2*X(2)^2+10*X(3)     -80
356 FOR J44=2 TO 2
357 IF  ABS(PS(J44))   >.00005 THEN PS(J44)=ABS(PS(J44))  ELSE PS(J44)=0
358 NEXT J44
411 POBA= -2*  X(1)   - 9*X(2)-  14*X(3)   -   2*X(3) *X(1)+X(3)^2
459 POB1=POBA+    -999999999#*( +PS(2)      )
463 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 3
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-117 THEN 1999
1900 PRINT A(1),A(2),A(3)
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=-31186 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.

31.69516   4.914513   0
-107.6209   -31922

31.69516   4.914513   0
-107.6209   -31597

31.69516   4.914513   0
-107.6209   -31186

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=-31186 was ten 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, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., Copyright 1981.

[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/