The Domino Method of General Integer Nonlinear Programming Applied to Problem 9 of Lawler and Bell

Jsun Yui Wong

The complete computer program below tries to solve Problem 9 in Lawler and Bell [4 and 5].  Line 181 through line 1111 of the following computer program partly describe the problem.

The following computer program has been 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 [8].  Line 501 through line 711 are illustrative.  The intent behind line 501 through line 518 is to produce domino effect; X(9) through X(26) are slack variables.  Looking at line 501, one sees that it is not hard to knock down X(9), domino one.

0 REM DEFDBL A-Z
2 DEFINT I,J,K,X
3 DIM B(519),N(519),A(2002),H(519),L(519),U(519),X(2002),D(511),P(511),PS(33),AA(1111)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
20 FOR J44=1 TO 8
21 A(J44)=FIX(RND*8)
22 NEXT J44
128 FOR I=1 TO 100
129 FOR KKQQ=1 TO 8
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO FIX(RND*8)
181 J=1+FIX(RND*8)
183 REM R=(1-RND*2)*A(J)
187 REM X(J)=A(J)+  (RND^(RND*10))*R
188 REM GOTO  222
190 X(J)=A(J)+FIX(RND*2 )-FIX(RND*2)
396 NEXT IPP
443 FOR J44=1 TO 8
446 IF X(J44)<0 THEN 1670
449 NEXT J44
501 X(9)=   +7  -X(1)
502 X(10)=   +7  -X(3)
503 X(11)=   +7  -X(4)
504 X(12)=   +7  -X(6)
505 X(13)=   +7  -X(8)
506 X(14)=   +15 -   X(2)
507 X(15)=   +15 -    X(5)
508 X(16)=   +15  -    X(7)
509 X(17)=   -41 + 11* X(1)  +7* X(4)      + 13* X(6)
510 X(18)=   -12 +  2*  X(1) + 2*  X(4)  +8*X(8)
511 X(19)=   -42 +3* X(2) + 5* X(5) + 7*    X(8)
512 X(20)=   -13 +  4* X(3)*X(7)   +      X(5)
513 X(21)=   31 -    X(3) -4* X(5)     -2* X(6)    - 9*   X(8)
514 X(22)=   73  - 12* X(2)      - 8*   X( 2  )*X(8)   -2* X(3) * X(6)
515 X(23)=   -60 + 6*  X(2)  +9* X(4) *X(6)    + 5*  X(7)
516 X(24)=   -53 +6* X(2)*X(7)   +9*  X(3)+5*X(5)
517 X(25)=   47  -9* X(1)* X(8) - 6* X(3)   *X(5)   -  4*  X(3)*X(7)
518 X(26)=  69  -2* X(1)   -4*X(2) -     7* X(4)     -3*X(5)   -   X(7)
519 REM   X(27)=   -4  +   X(1) +2* X(2) +    X(4)
554 FOR J44=9 TO 26
555 IF X(J44)<0 THEN PS(J44)=ABS(X(J44)) ELSE PS(J44)=0
556 NEXT J44
703 POBAT= - X(1) -X(2) -X(3) -X(4) -X(5) -X(6)-X(7)-X(8)
711 POBA= POBAT -999999999#*( PS(9)+PS(10)+PS(11)+PS(12)+PS(13)+PS(14)+PS(15)+PS(16)+ PS(17)+PS(18)+PS(19)+PS(20)+PS(21)+PS(22) +PS(23)+PS(24)+PS(25)+PS(26) )
866 P=POBA
1111 IF P<=M THEN 1670
1452 M=P
1453 PPOBAT=POBAT
1454 FOR KLX=1 TO 26
1455 A(KLX)=       (   X(KLX)   )
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1899 IF M<-20 THEN 2222
2001 PRINT A(1),A(2),A(3),A(4),A(5)
2002 PRINT A(6),A(7),A(8),A(9),A(10)
2003 REM PRINT A(11),A(12),A(13),A(14),A(15)
2004 REM PRINT A(16),A(17),A(18),A(19),A(20)
2005 REM PRINT A(21),A(22),A(23),A(24),A(25)
2022 PRINT A(26),M,JJJJ,PPOBAT
2222 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  The complete output through JJJJ=-31956 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

3   4   1   3   6
1   2   0   4   6
6   -20   -31979   -20

3   4   1   3   6
1   2   0   4   6
6   -20   -31977   -20

2   4   1   4   6
1   2   0   5   6
1   -20   -31975   -20

3   4   1   3   6
1   2   0   4   6
6   -20   -31966   -20

2   4   1   4   6
1   2   0   5   6
1   -20   -31956   -20

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=-31956 was three 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] George B. Dantzig,  Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

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

[4] 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.
 
[5] E. L. Lawler, M. D. Bell, Errata: A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 15, No. 3 (May-June, 1967), p. 578.
 
[6] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

[8] Jsun Yui Wong (2011, April 17).  The Domino Method of Solving Nonlinear Systems of Equations.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/04/17/