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

Jsun Yui Wong

The following computer program tries to solve Example 3.35 of Conley [2, pp. 65-66].  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's X(5) is proxy domino one.

0 REM DEFDBL A-Z
2 DEFINT I,J,K,X
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 4
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 4
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*3))
181 J=1+FIX(RND*4)
183 REM 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
189 REM X(J)=A(J)+PA
190 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(5)  = 38    -X(1)-3*X(4)
211 FOR J44=1 TO 4
212 IF X(J44)<0 THEN 1670
213 NEXT J44
221 FOR J44=1 TO 4
222 IF X(J44)>30 THEN 1670
223 NEXT J44
331 IF X(5)<  0 THEN PS(1)=ABS(X(5)) ELSE PS(1)=0
351 PS(2)=X(1)^2+X(1)*X(4)     -45
353 PS(3)=   +X(2) +X(4)   -52
355 PS(4)=   X(1)+X(2) +3*X(3)   -55
356 FOR J44=2 TO 4
357 IF  PS(J44)>0 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
358 NEXT J44
411 POBA= +X(1)   - X(2)+   X(3)   -X(4) +X(1)*X(2)-X(1)*X(4)+X(4)^2-X(1)^2
459 POB1=POBA+    -999999999#*(PS(1) +PS(2)  +PS(3)+PS(4)    )
463 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 5
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<140 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),A(5)
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=-31115 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.

2   26   9   12   0
141   -31932

0   0   18   12   2
150   -31868

0   0   18   12   2
150   -31798

2   30   7   12   0
143   -31115

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=-31115 was forty seconds.

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/