Jsun Yui Wong
Similar to the computer program in Wong [11], the computer program listed below tries to solve Problem 3 of Lawler and Bell [5]. The following line 181 through line 1111 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 241 and line 242 are illustrative. It takes an optimizing integer for
X(1), an optimizing integer for X(2), and an optimizing integer for X(3) to produce an optimizing integer for X(8), the first domino. Then it takes one optimizing integer, X(5), not three optimizing integers, to produce an optimizing value for X(9), the second domino. Then these six optimizing values can simplify the mathematical expressions below line 242.
Reference 6 is noteworthy.
One notes that X(8) and X(9) are slack variables.
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 9
42 A(J44)=FIX(RND*10)
43 NEXT J44
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 9
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*8))
181 J=1+FIX(RND*9)
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
187 REM X(J)=A(J)+(RND^3)*R
189 REM X(J)=A(J)+PA
190 X(J)=A(J)+FIX(RND*2 )-FIX( RND*2 )
192 NEXT IPP
241 X(8)=-6 + X(1) + X(2)+ X(3)
242 X(9)=7 - 3*X(1) - 2*X(3)- X(5)
261 FOR J44=1 TO 9
262 IF X(J44)<0 THEN 1670
263 NEXT J44
345 PS(1)=20 - 3*X(1)*X(3)- 6*X(4) -4*X(5)
348 PS(2)=15 - 4*X(1) - 2*X(3) -X(6)*X(7)
349 PS(3)=-8 + X(4) + X(5) + 6*X(6)
350 PS(4)=-7 + X(1)*X(6)+ X(2) + 3*X(5)
351 PS(5)=-25 + 4*X(2)*X(7)+3*X(4)*X(5)
361 FOR J44=1 TO 5
362 IF PS(J44)<0 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
363 NEXT J44
459 POB1=-X(1)-X(2)-X(3)-X(4)-X(5)-X(6)-X(7)
460 POB3=999999999#*(+PS(1)+PS(2)+PS(3)+PS(4)+PS(5) )
463 P1NEWMAY=POB1+POB3
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<-10 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),A(5)
1911 PRINT A(6),A(7),A(8),A(9)
1913 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=-31431 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.
0 7 0 0 0
2 1 1 7
-10 -31964
0 7 0 0 0
2 1 1 7
-10 -31944
1 5 0 0 0
2 2 0 4
-10 -31906
0 6 0 1 1
1 1 0 6
-10 -31845
0 7 0 0 0
2 1 1 7
-10 -31835
0 7 0 0 0
2 1 1 7
-10 -31765
0 7 0 0 0
2 1 1 7
-10 -31733
0 7 0 0 0
2 1 1 7
-10 -31721
1 5 0 0 0
2 2 0 4
-10 -31666
0 7 0 0 0
2 1 1 7
-10 -31650
0 7 0 0 0
2 1 1 7
-10 -31552
1 5 0 0 0
2 2 0 4
-10 -31459
0 7 0 0 0
2 1 1 7
-10 -31455
0 6 0 1 1
1 1 0 6
-10 -31443
0 7 0 0 0
2 1 1 7
-10 -31441
0 6 0 1 1
1 1 0 6
-10 -31437
0 6 0 1 1
1 1 0 6
-10 -31431
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=-31431 was fifteen 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] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[5] 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.
[6] E. L. Lawler, M. D. Bell, Errata. Operations Research, Vol. 15, No. 3 (May-Jun., 1967), p. 578.
[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/
[11] Jsun Yui Wong (2011, August 13). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Discrete Optimization Problem, Fifth Edition. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/08/13/