The Domino Method of General Integer Nonlinear Programming Applied to a Problem with Nonlinear Objective Function, Linear Inequality Constraints, and General Integer Variables

Jsun Yui Wong

The computer program below tries to solve Example 10.2 on pages 192-194 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 301, which is 301 X(6)=-X(1)-7*X(2)-3*X(3)-2*X(4)-X(5)+360, through line 459 are illustrative.  Line 301's X(6), a slack variable, is proxy domino one; this line 301 is an expression of the first given nonequality constraint [2, page 192].

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 8
42 A(J44)=FIX(RND*35)
43 NEXT J44
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 5
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*4))
181 J=1+FIX(RND*5)
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 5
201    IF X(J44)>35 THEN 1670
202    IF X(J44)<0 THEN 1670
203    NEXT J44
301 X(6)=-X(1)-7*X(2)-3*X(3)-2*X(4)-X(5)+360
302 L2=X(1)+2*X(2)+3*X(3)+4*X(4)+5*X(5)   -400
303 L3=5*X(1)+4*X(2)+3*X(3)+2*X(4)+X(5)   -400
307 IF X(6)<0 THEN PS(1)=ABS(X(6)) ELSE PS(1)=0
308 IF L2>0 THEN PS(2)=L2 ELSE PS(2)=0
309 IF L3>0 THEN PS(3)=L3 ELSE PS(3)=0
402 POBA2=2*X(1)+X(2)^2+6*X(3)+5*X(4)+9*X(5)
411 POBA= POBA2
459 POB1=POBA -999999999#*(PS(1)+PS(2)+PS(3)  )
463 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 6
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<1735 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),A(5)
1903 PRINT A(6),M,JJJJ
1999 NEXT JJJJ

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

1   35   3   35   35
0   1735   -31993

4   35   2   35   35
0   1735   -31989

7   35   1   35   35
0   1735   -31890

1   35   3   35   35
0   1735   -31821

10   35   0   35   35
0   1735   -31731

10   35   0   35   35
0   1735   -31523

4   35   2   35   35
0   1735   -31422

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=-31422 was two 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/