Substance

Testing the Domino Method of General Integer Nonlinear Programming with a Problem from the Literature, Second Edition

Jsun Yui Wong

This is an extension of Example 12.6 in Conley [2, pp. 226-228], an extension from 10 variables to 20 variables.  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].  The present example has no slack variable.

0 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 20
42 A(J44)=FIX(RND*20)
43 NEXT J44
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 20
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*19))
181 J=1+FIX(RND*20)
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
195 FOR J44=1 TO 20
196 IF X(J44)<0 THEN 1670
197 IF X(J44)>1000 THEN 1670
198 NEXT J44
411 POBA=900000000# -(X(1)   -370)^2-(X(2)-535   )^2 -(X(3) -892)^2-(X(4) -312) ^2     -(X(5) -427) ^2    -(X(6) -243)   ^2
412 POBB= -(X(7) -183)^2-(X(8)-873   )^2 -(X(9) -919)^2-(X(10) -944) ^2
413 POBC= -(X(11)   -695)^2-(X(12)-630   )^2 -(X(13) -326)^2-(X(14) -679) ^2     -(X(15) -552) ^2    -(X(16) -480)   ^2
414 POBD= -(X(17) -351)^2-(X(18)-98   )^2 -(X(19) -929)^2-(X(20) -288) ^2
459 POB1=POBA+POBB+POBC+POBD
463 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 20
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<0 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4)
1905 PRINT A(5),A(6),A(7),A(8)
1906 PRINT A(9),A(10),A(11),A(12)
1907 PRINT A(13),A(14),A(15),A(16)
1908 PRINT A(17),A(18),A(19),A(20)
1916 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=-31998 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.

370   535   892   311
427   243   183   873
919   945   695   629
326   679   552   480
351   98   929   288
899999997   -32000

370   535   892   312
427   243   183   873
919   944   695   630
326   679   552   480
351   98   929   288
900000000   -31999

370   535   892   312
427   243   183   873
919   944   695   630
326   679   552   480
351   98   929   288
900000000   -31998

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=-31998 was twenty 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, 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/

Testing the Domino Method of General Integer Nonlinear Programming with a Problem from the Literature

Jsun Yui Wong

The computer program listed below tries to find integer solutions to Example 12.6 in Conley [2, pp. 226-228].  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].  The present example has no slack variable.

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 10
42 A(J44)=FIX(RND*20)
43 NEXT J44
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 10
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*9))
181 J=1+FIX(RND*10)
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
195 FOR J44=1 TO 10
196 IF X(J44)<0 THEN 1670
197 IF X(J44)>1000 THEN 1670
198 NEXT J44
411 POBA=900000000# -(X(1)   -370)^2-(X(2)-535   )^2 -(X(3) -892)^2-(X(4) -312) ^2     -(X(5) -427) ^2    -(X(6) -243)   ^2
412 POBB= -(X(7) -183)^2-(X(8)-873   )^2 -(X(9) -919)^2-(X(10) -944) ^2
459 POB1=POBA+POBB
463 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 10
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<0 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4)
1905 PRINT A(5),A(6),A(7),A(8)
1906 PRINT A(9),A(10),M,JJJJ
1999 NEXT JJJJ

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

370   535   892   312
427   243   183   873
919   944   900000000   -32000

370   535   892   312
427   243   183   873
919   944   900000000   -31999

370   535   892   312
427   243   183   873
919   944   900000000   -31998

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=-31998 was ten 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, 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/

The Domino Method of General Integer Nonlinear Programming Applied to a Chemical Yield Equation with General Integer Variables

Jsun Yui Wong

The computer program listed below tries to find integer solutions to the chemistry problem on page 119 of Conley [2].  Line 181 through line 1111 of the following computer program partly describe the problem.  Line 190 and line 191 are noteworthy.

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=0 TO 9
42 A(J44)=FIX(RND*500)
43 NEXT J44
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=0 TO 9
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*8))
181 J=0+FIX(RND*10)
183 REM R=(1-RND*2)*A(J)
185 REM
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 REM
195 FOR J44=0 TO 9
196 IF X(J44)<100 THEN 1670
197 IF X(J44)>800 THEN 1670
198 NEXT J44
449 POBA= 7000000!-.00062*X(3)*X(4)*X(5)-.000071*X(6)*X(7)*X(8)-4*X(0)^2+480*X(0)  +.011*X(0)*X(1)-9*X(1)^2+2160*X(1)+9.000001E-02*X(1)*X(2)-5.25*X(2)^2+2350*X(2)  +8.000001E-03*X(2)*X(3)  -X(3)^2  +948*X(3)   +.012*X(3)*X(4)   -16*X(4)^2
450 POBB=   9568!*X(4)+.0068*X(4)*X(5)    -4*X(5)^2  +2754*X(5) +.015*X(5)*X(6)   -25*X(6)^2 +19500*X(6)    +.007*X(6)*X(7)   -X(7)^2    +900*X(7)   +.0072*X(7)*X(8)    -3.61*X(8)^2  + 3853.2*X(8) +.0081*X(8)*X(9)-.6724*X(9)^2+1804*X(9)
459 POB1=POBA+POBB
463 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=0 TO 9
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<0 THEN 1999
1900 PRINT A(0),A(1),A(2),A(3),A(4)
1905 PRINT A(5),A(6),A(7),A(8),A(9)
1911 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=-31991 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.

100   121   225   446   296
335   390   446   533   800
1.555444E+07   -31994

100   121   225   445   296
335   390   446   533   800
1.555444E+07   -31992

100   121   225   446   296
335   390   446   533   800
1.555444E+07   -31991

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=-31991 was five 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, Applications of Multi-Stage Monte Carlo Integer Programs.  Int. J. Math. Educ. Sci. Technol., 1981, Vol. 12, No. 1, 117-120.

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

The Domino Method of General Integer Nonlinear Programming Applied to Solving a System of Nonlinear Equations with Continuous Variables

Jsun Yui Wong

The computer program listed below tries to find solutions to a system of nonlinear equations in Conley and Kossik [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 201 through line 352 of the computer program below are illustrative.

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 REM   M=-1D+37
17 M=1D+37
41 FOR J44=1 TO 7
42 A(J44)=FIX(RND*10)
43 NEXT J44
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 7
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*6))
181 J=1+FIX(RND*7)
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
187 REM X(J)=A(J)+(RND^3)*R
189 X(J)=A(J)+PA
190 REM      X(J)=A(J)+FIX(RND*2  )-FIX( RND*2    )
192 NEXT IPP
195 FOR J44=1 TO 7
196 IF X(J44)<.00001 THEN 1670
198 NEXT J44
200 IF X(7)>1.57 THEN 1670
201 X(5)=( -3.1416 +X(4) + ( TAN(X(7) ) +X(1)*X(4)  )^(1.33333333#) )  /X(2)^2.71828
351 PS(1)=  (  X(1)+X(3)  ) /(X(6)*SIN(  X(7)  )   )  +X(1)*X(5)*COS(X(7)  )  -X(3)    -43
352 PS(2)=  (  X(3)+X(2)-X(1) +X(4)  )*(X(3)+X(5)     )
459 POB1=ABS(PS(1))+ABS(PS(2))
463 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 REM  IF P<=M THEN 1670
1112 IF P>=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 7
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M>.0000001 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),A(5),A(6),A(7),M,JJJJ
1999 NEXT JJJJ

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

11.12386   3.851568   .1621062   7.110183   9.124459
5.297564   1.156748   0   -31933

8.499642   2.532304   3.111087   2.856251   5.775221
7.20509   .5110232   0   -31915

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=-31915 was 28 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, Ronald Kossik, A 100000 Variable Nonlinear Problem.  Int. J. Math. Educ. Sci. Technol., 1983, Vol. 14, No. 1, 117-125.

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

The Domino Method of General Integer Nonlinear Programming Applied to a Problem with Nonlinear Objective Function, One Nonlinear Constraint, and General Integer Variables

Jsun Yui Wong

The computer program listed below tries to find integer solutions to 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 201 through line 363 of the computer program below are illustrative.

X(5) and X(6) 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 6
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 6
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*5))
181 J=1+FIX(RND*6)
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
201 X(5)=52-X(2)    -  X(4)
204 X(6)=38     -X(1)  -3*X(4)
261 FOR J44=1 TO 6
262 IF X(J44)<0 THEN 1670
273 NEXT J44
281 REM FOR J44=1 TO 4
282 REM IF X(J44)>30 THEN 1670
283 REM NEXT J44
351 PS(1)=X(1)+X(2)+3*X(3)  -55
352 PS(2)=   X(1)^2+X(1)*X(4)   -45
361 FOR J44=1 TO 2
362 IF (PS(J44))   >0   THEN PS(J44)=(PS(J44) ) ELSE PS(J44)=0
363 NEXT J44
441 POB1A=X( 1 ) -X( 2 )  +X(3)-X(4)+X(1)*X(2)-X(1)*X(4)+X(4)^2-X(1)^2
459 POB1=POB1A
460 POB3=   -  999999999#*(PS(1)+PS(2)   )
463 P1NEWMAY=POB1+POB3
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<140 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),A(5),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=-31851 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   0   18   12   40
2   150   -31976

0   0   18   12   40
2   150   -31974

2   26   9   12   14
0   141   -31953

6   49   0   0   3
32   215   -31851

The candidate solution at JJJJ=-31851 is not acceptable because X(2)'s upper bound is 30.

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=-31851 was ten 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.  New York/Princeton: Petrocelli Books, Inc., 1980.

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

The Domino Method of General Integer Nonlinear Programming Applied to an Oil Refinery Problem with Nonlinear Objective Function, Equality Constraints, and Continuous Variables

Jsun Yui Wong

The computer program listed below tries to find solutions to the nonlinear programming formulation on page 196 of Conley [2] plus the objective function on page 198 of Conley [2].  This objective function is expressed in line 441, which is 441 POB1A=-3.58*X( 1 )^.88-5.92*X( 2 )^1.04-2.95*X(3)^.98-4.01*X(4)^1.02-5.02*X(5)^1.08.  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 200 through line 363 of the computer program below are illustrative.

Line 362, which is 362 IF ABS(PS(J44))   >.00001 THEN PS(J44)=ABS(PS(J44) ) ELSE PS(J44)=0, is noteworthy.

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 5
42 A(J44)=FIX(RND*1000)
43 NEXT J44
126 IMAR=10+FIX(RND*5000)
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)
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
187 REM   X(J)=A(J)+(RND^3)*R
189 X(J)=A(J)+PA
190 REM X(J)=A(J)+FIX(RND*2  )-FIX( RND*2    )
192 NEXT IPP
200 X(1)=  ( -.25*X(2)-.3*X(3)-.25*X(4)-.35*X(5)  +400 ) /.3
261 FOR J44=1 TO 5
262 IF X(J44)<0 THEN 1670
263 NEXT J44
264 IF X(1)>600    THEN 1670
265 IF X(2)>1500   THEN 1670
266 IF X(3)>600   THEN 1670
267 IF X(4)>200   THEN 1670
268 IF X(5)>400   THEN 1670
290     PS(1)=.35*X(1)  +.3*X(2)+.25*X(3)+.25*X(4)+.25*X(5)   -450
291     PS(2)=.3*X(1)  +.4*X(2)+.4*X(3)+.4*X(4)+.3*X(5)   -550
361 FOR J44=0 TO 2
362 IF ABS(PS(J44))   >.00001 THEN PS(J44)=ABS(PS(J44) ) ELSE PS(J44)=0
363 NEXT J44
441 POB1A=-3.58*X( 1 )^.88-5.92*X( 2 )^1.04-2.95*X(3)^.98-4.01*X(4)^1.02-5.02*X(5)^1.08
459 POB1=POB1A
460 POB3=   -  99999999#*(PS(0)+PS(1)+PS(2)   )
463 P1NEWMAY=POB1+POB3
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<-7453 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),A(5)
1922 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=-29753 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.

436.84   705.2691   142.1094   199.9914   1.891935E-04
-7452.895   -31490

436.8422   705.2634   142.1055   199.9995   3.05963E-05
-7452.878   -31146

436.8316   705.291   142.1112   199.9701   5.363598E-03
-7452.983   -29753

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=-29753 was seventeen 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, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

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

The Domino Method of Nonlinear Discrete Programming Applied to a Transportation Problem with Nonlinear Objective Function, Eight Equality Constraints, and General Integer Variables

Jsun Yui Wong

The computer program listed below tries to find integer solutions to the mathematical formulation on page 183 of Conley [2], including the additional constraints of X(8)+X(9)=30 and X(5)+X(6)=60.  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 201 through line 363 of the computer program below are illustrative.

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*20)
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
201 X(5)=60-X(6)
211 X(4)=70  -   X(5)    -  X(6)
213 X(8)=30-X(9)
222 X(3)=47  -   X(6)    -  X(9)
223 X(7)=40  -   X(8)    -  X(9)
224 X(1)=41  -   X(4)    -  X(7)
225 X(2)=52  -   X(5)    -  X(8)
261 FOR J44=1 TO 9
262 IF X(J44)<0 THEN 1670
263 NEXT J44
352 PS(1)=    X(1)  +X(2)   +X(3)     -30
361 FOR J44=1 TO 1
362 IF ABS(PS(J44))   >0   THEN PS(J44)=ABS(PS(J44) ) ELSE PS(J44)=0
363 NEXT J44
441 POB1A=-110*X( 1 ) -158*X( 2 )  -92*X(3)- 118*X(4)   - 103*X(5)
442 POB1B=-88*X(6 ) -135*X( 7 )  -116*X(8)   -130*X(9)^1.5
459 POB1=POB1A+POB1B
460 POB3=   -  999999999#*(+PS(1)   )
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<-15710 THEN 1999
1900 PRINT A(1),A(2),A(3),A(4),A(5)
1912 PRINT A(6),A(7),A(8),A(9)
1922 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=-31327 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.

21   0   9   10   22
38   10   30   0
-14758   -31568

21   0   9   10   22
38   10   30   0
-14758   -31495

21   0   9   10   27
33   10   25   5
-15706.44   -31411

21   0   9   10   22
38   10   30   0
-14758   -31327

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=-31327 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] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

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

A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Small Example with Nonlinear Objective Function, One Nonlinear Constraint, and Large Integer Variables

Jsun Yui Wong

The computer program listed below tries to find integer solutions to Example 5.1 on page 119 of Conley {1].

0 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 3
42 A(J44)=FIX(RND*999)
43 NEXT J44
126 IMAR=10+FIX(RND*500)
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 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
201 FOR J44=1 TO 3
202 IF X(J44)<0 THEN 1670
203 NEXT J44
211 FOR J44=1 TO 3
212 IF X(J44)>999 THEN 1670
213 NEXT J44
311 PS(1)=   X(1)  +  X(2)+ 2* X(3)   -2000
312 PS(2)=   X(1)  +17* X(2)    -8000
313 PS(3)=   X(2)  + 5* X(3)    -4000
314 PS(4)= -X(1)  -7*  X(2) -2*X(3) +200
315 PS(5)=-X(1)- X(2)-    X(3)  +200
316 PS(6)=-  X(1)^2 -   X(2)*X(3) +900
361 FOR J44=1 TO 6
362 IF PS(J44)>0 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
363 NEXT J44
459 POB1=-6*X(1)^2-18*X(2)^2-7*X(3)^2+2*X(1)+16*X(2)+31*X(3)+12*X(1)*X(2)*X(3)
460 POB3=-999999999#*(+PS(1)+PS(2)+PS(3)+PS(4)+PS(5)+PS(6)  )
463 P1NEWMAY=POB1+POB3
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<1573000000# THEN 1999
1900 PRINT A(1),A(2),A(3)
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=-29039 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.

758   426   408
1573099264   -31461

758   426   408
1573099264   -30669

775   425   400
1573045632   -30537

775   425   400
1573045632   -29547

758   426   408
1573099264   -29409

758   426   408
1573099264   -29039

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=-29039 was 31 minutes.

References

[1] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

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