Jsun Yui Wong
The following computer program tries to solve the problem on pp. 516-519 of Land and Doig [3]. Their article can also be found in Junger et al. [2, pp.105-132]. Line 181 through line 1111 partly describe the problem. One notes that line 402 is 402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0. Line 187 is noteworthy.
This problem is a modified version of Markowitz and Manne's production problem [4, pp. 91-95].
Here line 42 is 42 A(J44)=FIX(RND*20) while line 42 of the preceding paper is 42 A(J44)=FIX(RND*2).
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),PP(22)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
41 FOR J44=2 TO 22
42 A(J44)=FIX(RND*20)
43 NEXT J44
126 IMAR=10+FIX(RND*4000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=2 TO 22
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*20))
181 J=2+FIX(RND*21)
187 X(J)=A(J)+FIX(RND*2)-FIX(RND*2)
192 NEXT IPP
196 FOR J88=2 TO 22
197 IF (X(J88)) <0 THEN 1670
198 IF (X(J88)) >20 THEN 1670
199 NEXT J88
381 PS(1)=97*X(2)+74*X(3)+24*X(4)+67*X(5)+62*X(6)+42*X(7)+81*X(8)+14*X(9)+57*X(10)+20*X(11)+42*X(12)+53*X(13)+32*X(14)+37*X(15)+32*X(16)+27*X(17)+7*X(18)+36*X(19)+7*X(20)+51*X(21)+24*X(22)-400
382 PS(2)=16*X(2)+76*X(3)+62*X(4)+27*X(5)+66*X(6)+56*X(7)+50*X(8)+26*X(9)+71*X(10)+7*X(11)+32*X(12)+90*X(13)+79*X(14)+78*X(15)+53*X(16)+13*X(17)+55*X(18)+38*X(19)+58*X(20)+59*X(21)+88*X(22)-400
383 PS(3)=12*X(2)+56*X(3)+85*X(4)+99*X(5)+26*X(6)+96*X(7)+96*X(8)+68*X(9)+27*X(10)+31*X(11)+5*X(12)+3*X(13)+72*X(14)+93*X(15)+15*X(16)+57*X(17)+12*X(18)+10*X(19)+14*X(20)+21*X(21)+88*X(22)-350
384 PS(4)=55*X(2)+59*X(3)+56*X(4)+35*X(5)+64*X(6)+38*X(7)+54*X(8)+82*X(9)+46*X(10)+22*X(11)+31*X(12)+62*X(13)+43*X(14)+9*X(15)+90*X(16)+6*X(17)+18*X(18)+44*X(19)+32*X(20)+53*X(21)+23*X(22)-320
385 PS(5)=16*X(2)+22*X(3)+77*X(4)+94*X(5)+39*X(6)+49*X(7)+54*X(8)+43*X(9)+54*X(10)+82*X(11)+17*X(12)+37*X(13)+93*X(14)+23*X(15)+78*X(16)+87*X(17)+35*X(18)+20*X(19)+96*X(20)+43*X(21)+84*X(22)-420
386 PS(6)=84*X(2)+42*X(3)+17*X(4)+53*X(5)+31*X(6)+57*X(7)+24*X(8)+55*X(9)+6*X(10)+88*X(11)+77*X(12)+4*X(13)+74*X(14)+47*X(15)+67*X(16)+21*X(17)+76*X(18)+33*X(19)+15*X(20)+25*X(21)+83*X(22)-400
401 FOR J44=1 TO 6
402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
403 NEXT J44
459 POB1=3*X(2)+47*X(3)+43*X(4)+73*X(5)+86*X(6)+36*X(7)+96*X(8)+47*X(9)+36*X(10)+61*X(11)+46*X(12)+98*X(13)+63*X(14)+71*X(15)+62*X(16)+33*X(17)+26*X(18)+16*X(19)+80*X(20)+45*X(21)+60*X(22)
460 POB2=-999999999#*(PS(1)^2+PS(2)^2+PS(3)^2+PS(4)^2+PS(5)^2+PS(6)^2)
462 P1NEWMAY= POB1+POB2
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=2 TO 22
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<594 THEN 1999
1933 PRINT A(2),A(3),A(4),A(5),A(6)
1934 PRINT A(7),A(8),A(9),A(10),A(11)
1935 PRINT A(12),A(13),A(14),A(15),A(16)
1936 PRINT A(17),A(18),A(19),A(20),A(21)
1937 PRINT A(22),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31778 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 0 1 1
0 0 0 0 2
1 2 0 1 0
0 0 0 0 0
0 594 -31982
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31973
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31960
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31835
0 0 0 1 1
0 0 0 0 2
1 2 0 1 0
0 0 0 0 0
0 594 -31813
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31803
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31792
0 0 0 1 1
0 0 0 0 2
1 2 0 1 0
0 0 0 0 0
0 594 -31787
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31778
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=-31778 was six minutes, total time.
References
[1] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[2] 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, 2009.
[3] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[4] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[5] 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.
« November 2011 | Main | January 2012 »
December 2011
12/10/2011
A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the "Any Integer" Problem of Land and Doig, Third Edition
Posted at 10:12 AM | Permalink | Comments (0)
12/07/2011
A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the "Any Integer" Problem of Land and Doig, Second Edition
Jsun Yui Wong
The following computer program tries to solve the problem on pp. 516-519 of Land and Doig [3], which can also be found in Junger et al. [2, pp.105-132]. Line 181 through line 1111 partly describe the problem. One notes that line 402 is 402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0. Line 187 is noteworthy.
This problem is a modified version of Markowitz and Manne's production problem [4, pp. 91-95].
Here line 198 is 198 IF (X(J88)) >20 THEN 1670 while in the earlier edition line 198 is
198 IF (X(J88)) >10 THEN 1670. Also, here line 126 is 126 IMAR=10+FIX(RND*4000) while in the earlier edition line 126 is 126 IMAR=10+FIX(RND*2000).
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),PP(22)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
41 FOR J44=2 TO 22
42 A(J44)=FIX(RND*2)
43 NEXT J44
126 IMAR=10+FIX(RND*4000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=2 TO 22
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*20))
181 J=2+FIX(RND*21)
187 X(J)=A(J)+FIX(RND*2)-FIX(RND*2)
192 NEXT IPP
196 FOR J88=2 TO 22
197 IF (X(J88)) <0 THEN 1670
198 IF (X(J88)) >20 THEN 1670
199 NEXT J88
381 PS(1)=97*X(2)+74*X(3)+24*X(4)+67*X(5)+62*X(6)+42*X(7)+81*X(8)+14*X(9)+57*X(10)+20*X(11)+42*X(12)+53*X(13)+32*X(14)+37*X(15)+32*X(16)+27*X(17)+7*X(18)+36*X(19)+7*X(20)+51*X(21)+24*X(22)-400
382 PS(2)=16*X(2)+76*X(3)+62*X(4)+27*X(5)+66*X(6)+56*X(7)+50*X(8)+26*X(9)+71*X(10)+7*X(11)+32*X(12)+90*X(13)+79*X(14)+78*X(15)+53*X(16)+13*X(17)+55*X(18)+38*X(19)+58*X(20)+59*X(21)+88*X(22)-400
383 PS(3)=12*X(2)+56*X(3)+85*X(4)+99*X(5)+26*X(6)+96*X(7)+96*X(8)+68*X(9)+27*X(10)+31*X(11)+5*X(12)+3*X(13)+72*X(14)+93*X(15)+15*X(16)+57*X(17)+12*X(18)+10*X(19)+14*X(20)+21*X(21)+88*X(22)-350
384 PS(4)=55*X(2)+59*X(3)+56*X(4)+35*X(5)+64*X(6)+38*X(7)+54*X(8)+82*X(9)+46*X(10)+22*X(11)+31*X(12)+62*X(13)+43*X(14)+9*X(15)+90*X(16)+6*X(17)+18*X(18)+44*X(19)+32*X(20)+53*X(21)+23*X(22)-320
385 PS(5)=16*X(2)+22*X(3)+77*X(4)+94*X(5)+39*X(6)+49*X(7)+54*X(8)+43*X(9)+54*X(10)+82*X(11)+17*X(12)+37*X(13)+93*X(14)+23*X(15)+78*X(16)+87*X(17)+35*X(18)+20*X(19)+96*X(20)+43*X(21)+84*X(22)-420
386 PS(6)=84*X(2)+42*X(3)+17*X(4)+53*X(5)+31*X(6)+57*X(7)+24*X(8)+55*X(9)+6*X(10)+88*X(11)+77*X(12)+4*X(13)+74*X(14)+47*X(15)+67*X(16)+21*X(17)+76*X(18)+33*X(19)+15*X(20)+25*X(21)+83*X(22)-400
401 FOR J44=1 TO 6
402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
403 NEXT J44
459 POB1=3*X(2)+47*X(3)+43*X(4)+73*X(5)+86*X(6)+36*X(7)+96*X(8)+47*X(9)+36*X(10)+61*X(11)+46*X(12)+98*X(13)+63*X(14)+71*X(15)+62*X(16)+33*X(17)+26*X(18)+16*X(19)+80*X(20)+45*X(21)+60*X(22)
460 POB2=-999999999#*(PS(1)^2+PS(2)^2+PS(3)^2+PS(4)^2+PS(5)^2+PS(6)^2)
462 P1NEWMAY= POB1+POB2
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=2 TO 22
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<594 THEN 1999
1933 PRINT A(2),A(3),A(4),A(5),A(6)
1934 PRINT A(7),A(8),A(9),A(10),A(11)
1935 PRINT A(12),A(13),A(14),A(15),A(16)
1936 PRINT A(17),A(18),A(19),A(20),A(21)
1937 PRINT A(22),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31461 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 0 1 1
0 0 0 0 2
1 2 0 1 0
0 0 0 0 0
0 594 -31934
0 0 0 1 1
0 0 0 0 2
1 2 0 1 0
0 0 0 0 0
0 594 -31916
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31914
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31889
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31863
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31839
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31797
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31794
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31777
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31758
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31745
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31671
0 0 0 1 1
0 0 0 0 2
1 2 0 1 0
0 0 0 0 0
0 594 -31579
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31543
0 0 0 1 1
0 0 0 0 2
1 2 0 1 0
0 0 0 0 0
0 594 -31461
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=-31461 was six minutes, total time.
References
[1] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[2] 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, 2009.
[3] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[4] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[5] 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.
Posted at 04:59 AM | Permalink | Comments (0)
12/06/2011
A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to Land and Doig's Problems
Jsun Yui Wong
The three computer programs below try to solve the three problems in Land and Doig [3], which can also be found in Junger et al. [2, pp.105-132].
1. Land and Doig's Numerical Example Involving Continuous Variables and General Integer Variables
The computer program listed below tries to solve the numerical example on pp. 507-511 of Land and Doig [3]. Also see Example 6.2 on pp. 175-178 of Salkin [6]. Line 181 through line 1111 partly describe the original problem. One notes that line 402 is 402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0.
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),PP(22)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
41 FOR J44=1 TO 5
42 A(J44)=RND*5
43 NEXT J44
126 IMAR=10+FIX(RND*500)
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
189 X(J)=A(J)+PA
192 NEXT IPP
193 FOR J44=1 TO 3
194 X(J44)=CINT(X(J44))
195 NEXT J44
196 FOR J44=1 TO 5
197 IF X(J44)<0 THEN 1670
198 NEXT J44
381 PS(1)=10.9*X(1)+3.6*X(2)-40.8*X(3)+43.9*X(4)+7.1*X(5)-82.3
382 PS(2)=-86.8*X(1)+32.7*X(2)+24.3*X(3)+13.8*X(4)-12.6*X(5)-77.3
383 PS(3)=60.9*X(1)+68.9*X(2)+69*X(3)-56.9*X(4)+22.5*X(5)-86.5
401 FOR J44=1 TO 3
402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
403 NEXT J44
459 POB1=77.9*X(1)+76.8*X(2)+89.6*X(3)+97.1*X(4)+31.3*X(5)
460 POB2=-999999999#*(PS(1)^2+PS(2)^2+PS(3)^2)
461 P1NEWMAY= POB1+POB2
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<981.6 THEN 1999
1933 PRINT A(1),A(2),A(3),A(4),A(5)
1937 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=-27634 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 0 4 5.070169 1.692887
981.6008 -31155
1 0 4 5.070163 1.692937
981.6018 -30406
1 0 4 5.070158 1.692969
981.6022 -27634
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=-27634 was twelve minutes, real time.
2. "Any Integer" Problem of Land and Doig
The following computer program tries to solve the problem on pp. 516-519 of Land and Doig [3]. Line 181 through line 1111 partly describe the problem. One notes that line 402 is 402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0. Line 187 is noteworthy.
This problem is a modified version of Markowitz and Manne's production problem [4, pp. 91-95].
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),PP(22)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
41 FOR J44=2 TO 22
42 A(J44)=FIX(RND*2)
43 NEXT J44
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=2 TO 22
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*20))
181 J=2+FIX(RND*21)
187 X(J)=A(J)+FIX(RND*2)-FIX(RND*2)
192 NEXT IPP
196 FOR J88=2 TO 22
197 IF (X(J88)) <0 THEN 1670
198 IF (X(J88)) >10 THEN 1670
199 NEXT J88
381 PS(1)=97*X(2)+74*X(3)+24*X(4)+67*X(5)+62*X(6)+42*X(7)+81*X(8)+14*X(9)+57*X(10)+20*X(11)+42*X(12)+53*X(13)+32*X(14)+37*X(15)+32*X(16)+27*X(17)+7*X(18)+36*X(19)+7*X(20)+51*X(21)+24*X(22)-400
382 PS(2)=16*X(2)+76*X(3)+62*X(4)+27*X(5)+66*X(6)+56*X(7)+50*X(8)+26*X(9)+71*X(10)+7*X(11)+32*X(12)+90*X(13)+79*X(14)+78*X(15)+53*X(16)+13*X(17)+55*X(18)+38*X(19)+58*X(20)+59*X(21)+88*X(22)-400
383 PS(3)=12*X(2)+56*X(3)+85*X(4)+99*X(5)+26*X(6)+96*X(7)+96*X(8)+68*X(9)+27*X(10)+31*X(11)+5*X(12)+3*X(13)+72*X(14)+93*X(15)+15*X(16)+57*X(17)+12*X(18)+10*X(19)+14*X(20)+21*X(21)+88*X(22)-350
384 PS(4)=55*X(2)+59*X(3)+56*X(4)+35*X(5)+64*X(6)+38*X(7)+54*X(8)+82*X(9)+46*X(10)+22*X(11)+31*X(12)+62*X(13)+43*X(14)+9*X(15)+90*X(16)+6*X(17)+18*X(18)+44*X(19)+32*X(20)+53*X(21)+23*X(22)-320
385 PS(5)=16*X(2)+22*X(3)+77*X(4)+94*X(5)+39*X(6)+49*X(7)+54*X(8)+43*X(9)+54*X(10)+82*X(11)+17*X(12)+37*X(13)+93*X(14)+23*X(15)+78*X(16)+87*X(17)+35*X(18)+20*X(19)+96*X(20)+43*X(21)+84*X(22)-420
386 PS(6)=84*X(2)+42*X(3)+17*X(4)+53*X(5)+31*X(6)+57*X(7)+24*X(8)+55*X(9)+6*X(10)+88*X(11)+77*X(12)+4*X(13)+74*X(14)+47*X(15)+67*X(16)+21*X(17)+76*X(18)+33*X(19)+15*X(20)+25*X(21)+83*X(22)-400
401 FOR J44=1 TO 6
402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
403 NEXT J44
459 POB1=3*X(2)+47*X(3)+43*X(4)+73*X(5)+86*X(6)+36*X(7)+96*X(8)+47*X(9)+36*X(10)+61*X(11)+46*X(12)+98*X(13)+63*X(14)+71*X(15)+62*X(16)+33*X(17)+26*X(18)+16*X(19)+80*X(20)+45*X(21)+60*X(22)
460 POB2=-999999999#*(PS(1)^2+PS(2)^2+PS(3)^2+PS(4)^2+PS(5)^2+PS(6)^2)
462 P1NEWMAY= POB1+POB2
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=2 TO 22
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<592 THEN 1999
1933 PRINT A(2),A(3),A(4),A(5),A(6)
1934 PRINT A(7),A(8),A(9),A(10),A(11)
1935 PRINT A(12),A(13),A(14),A(15),A(16)
1936 PRINT A(17),A(18),A(19),A(20),A(21)
1937 PRINT A(22),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-26893 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 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -30879
0 0 0 0 0
0 3 0 0 0
1 1 0 0 0
0 0 0 2 0
0 592 -30855
0 0 0 0 0
0 3 0 0 0
1 1 0 0 0
0 0 0 2 0
0 592 -29338
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -28468
0 0 0 1 1
0 0 0 0 2
1 2 0 1 0
0 0 0 0 0
0 594 -26893
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=-26893 was ten minutes, real time.
3. "0 Or 1" Problem of Land and Doig
The computer program listed below tries to solve the problem on pp. 519-520 of Land and Doig [3]. Line 181 through line 1111 partly describe the original problem. One notes that line 402 is 402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0.
The source of this problem is Markowitz and Manne [4, pp. 91-95].
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),PP(22)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
41 FOR J44=2 TO 22
42 A(J44)=FIX(RND*2)
43 NEXT J44
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=2 TO 22
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*20))
181 J=2+FIX(RND*21)
187 REM X(J)=A(J)+FIX(RND*2)-FIX(RND*2)
188 X(J)=FIX(RND*2)
192 NEXT IPP
196 FOR J88=2 TO 22
197 IF (X(J88)) <0 THEN 1670
198 IF (X(J88)) >10 THEN 1670
199 NEXT J88
381 PS(1)=97*X(2)+74*X(3)+24*X(4)+67*X(5)+62*X(6)+42*X(7)+81*X(8)+14*X(9)+57*X(10)+20*X(11)+42*X(12)+53*X(13)+32*X(14)+37*X(15)+32*X(16)+27*X(17)+7*X(18)+36*X(19)+7*X(20)+51*X(21)+24*X(22)-400
382 PS(2)=16*X(2)+76*X(3)+62*X(4)+27*X(5)+66*X(6)+56*X(7)+50*X(8)+26*X(9)+71*X(10)+7*X(11)+32*X(12)+90*X(13)+79*X(14)+78*X(15)+53*X(16)+13*X(17)+55*X(18)+38*X(19)+58*X(20)+59*X(21)+88*X(22)-400
383 PS(3)=12*X(2)+56*X(3)+85*X(4)+99*X(5)+26*X(6)+96*X(7)+96*X(8)+68*X(9)+27*X(10)+31*X(11)+5*X(12)+3*X(13)+72*X(14)+93*X(15)+15*X(16)+57*X(17)+12*X(18)+10*X(19)+14*X(20)+21*X(21)+88*X(22)-350
384 PS(4)=55*X(2)+59*X(3)+56*X(4)+35*X(5)+64*X(6)+38*X(7)+54*X(8)+82*X(9)+46*X(10)+22*X(11)+31*X(12)+62*X(13)+43*X(14)+9*X(15)+90*X(16)+6*X(17)+18*X(18)+44*X(19)+32*X(20)+53*X(21)+23*X(22)-320
385 PS(5)=16*X(2)+22*X(3)+77*X(4)+94*X(5)+39*X(6)+49*X(7)+54*X(8)+43*X(9)+54*X(10)+82*X(11)+17*X(12)+37*X(13)+93*X(14)+23*X(15)+78*X(16)+87*X(17)+35*X(18)+20*X(19)+96*X(20)+43*X(21)+84*X(22)-420
386 PS(6)=84*X(2)+42*X(3)+17*X(4)+53*X(5)+31*X(6)+57*X(7)+24*X(8)+55*X(9)+6*X(10)+88*X(11)+77*X(12)+4*X(13)+74*X(14)+47*X(15)+67*X(16)+21*X(17)+76*X(18)+33*X(19)+15*X(20)+25*X(21)+83*X(22)-400
401 FOR J44=1 TO 6
402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
403 NEXT J44
459 POB1=3*X(2)+47*X(3)+43*X(4)+73*X(5)+86*X(6)+36*X(7)+96*X(8)+47*X(9)+36*X(10)+61*X(11)+46*X(12)+98*X(13)+63*X(14)+71*X(15)+62*X(16)+33*X(17)+26*X(18)+16*X(19)+80*X(20)+45*X(21)+60*X(22)
460 POB2=-999999999#*(PS(1)^2+PS(2)^2+PS(3)^2+PS(4)^2+PS(5)^2+PS(6)^2)
462 P1NEWMAY= POB1+POB2
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=2 TO 22
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<538 THEN 1999
1933 PRINT A(2),A(3),A(4),A(5),A(6)
1934 PRINT A(7),A(8),A(9),A(10),A(11)
1935 PRINT A(12),A(13),A(14),A(15),A(16)
1936 PRINT A(17),A(18),A(19),A(20),A(21)
1937 PRINT A(22),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31967 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 0 0 1
0 1 0 0 1
1 1 0 1 0
0 0 0 1 0
0 538 -31998
0 0 0 1 1
0 1 0 0 1
1 1 0 0 0
0 0 0 1 0
0 540 -31995
0 0 0 1 1
0 1 0 0 1
1 1 0 0 0
0 0 0 1 0
0 540 -31980
0 0 0 1 1
0 1 0 0 1
1 1 0 0 0
0 0 0 1 0
0 540 -31976
0 0 0 1 1
0 1 0 0 1
1 1 0 0 0
0 0 0 1 0
0 540 -31975
0 0 0 0 1
0 1 0 0 1
1 1 0 1 0
0 0 0 1 0
0 538 -31970
0 0 0 0 1
0 1 0 0 1
1 1 0 1 0
0 0 0 1 0
0 538 -31967
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=-31967 was seven seconds, real time.
References
[1] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[2] 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, 2009.
[3] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[4] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[5] 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.
[6] Harvey M. Salkin, Integer Programming. Reading, Massachusetts: Addison-Wesley Publishing Company, 1975.
Posted at 03:39 AM | Permalink | Comments (0)
12/05/2011
A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the "Any Integer" Problem of Land and Doig
Jsun Yui Wong
The computer program listed below tries to solve the "ány integer" problem of Land and Doig [2, pp. 516-519]. This problem is a modified version of the production problem of Markowitz and Manne [3, pp. 91-95]. Line 181 through line 1111 partly describe the newer problem. Line 187 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),PP(22)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
41 FOR J44=2 TO 22
42 A(J44)=FIX(RND*2)
43 NEXT J44
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=2 TO 22
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*20))
181 J=2+FIX(RND*21)
187 X(J)=A(J)+FIX(RND*2)-FIX(RND*2)
192 NEXT IPP
196 FOR J88=2 TO 22
197 IF (X(J88)) <0 THEN 1670
198 IF (X(J88)) >10 THEN 1670
199 NEXT J88
381 PS(1)=97*X(2)+74*X(3)+24*X(4)+67*X(5)+62*X(6)+42*X(7)+81*X(8)+14*X(9)+57*X(10)+20*X(11)+42*X(12)+53*X(13)+32*X(14)+37*X(15)+32*X(16)+27*X(17)+7*X(18)+36*X(19)+7*X(20)+51*X(21)+24*X(22)-400
382 PS(2)=16*X(2)+76*X(3)+62*X(4)+27*X(5)+66*X(6)+56*X(7)+50*X(8)+26*X(9)+71*X(10)+7*X(11)+32*X(12)+90*X(13)+79*X(14)+78*X(15)+53*X(16)+13*X(17)+55*X(18)+38*X(19)+58*X(20)+59*X(21)+88*X(22)-400
383 PS(3)=12*X(2)+56*X(3)+85*X(4)+99*X(5)+26*X(6)+96*X(7)+96*X(8)+68*X(9)+27*X(10)+31*X(11)+5*X(12)+3*X(13)+72*X(14)+93*X(15)+15*X(16)+57*X(17)+12*X(18)+10*X(19)+14*X(20)+21*X(21)+88*X(22)-350
384 PS(4)=55*X(2)+59*X(3)+56*X(4)+35*X(5)+64*X(6)+38*X(7)+54*X(8)+82*X(9)+46*X(10)+22*X(11)+31*X(12)+62*X(13)+43*X(14)+9*X(15)+90*X(16)+6*X(17)+18*X(18)+44*X(19)+32*X(20)+53*X(21)+23*X(22)-320
385 PS(5)=16*X(2)+22*X(3)+77*X(4)+94*X(5)+39*X(6)+49*X(7)+54*X(8)+43*X(9)+54*X(10)+82*X(11)+17*X(12)+37*X(13)+93*X(14)+23*X(15)+78*X(16)+87*X(17)+35*X(18)+20*X(19)+96*X(20)+43*X(21)+84*X(22)-420
386 PS(6)=84*X(2)+42*X(3)+17*X(4)+53*X(5)+31*X(6)+57*X(7)+24*X(8)+55*X(9)+6*X(10)+88*X(11)+77*X(12)+4*X(13)+74*X(14)+47*X(15)+67*X(16)+21*X(17)+76*X(18)+33*X(19)+15*X(20)+25*X(21)+83*X(22)-400
401 FOR J44=1 TO 6
402 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
403 NEXT J44
459 POB1=3*X(2)+47*X(3)+43*X(4)+73*X(5)+86*X(6)+36*X(7)+96*X(8)+47*X(9)+36*X(10)+61*X(11)+46*X(12)+98*X(13)+63*X(14)+71*X(15)+62*X(16)+33*X(17)+26*X(18)+16*X(19)+80*X(20)+45*X(21)+60*X(22)
461 POB2=-1000*(PS(1)^2+PS(2)^2+PS(3)^2+PS(4)^2+PS(5)^2+PS(6)^2)
462 P1NEWMAY= POB1+POB2
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=2 TO 22
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<590 THEN 1999
1933 PRINT A(2),A(3),A(4),A(5),A(6)
1934 PRINT A(7),A(8),A(9),A(10),A(11)
1935 PRINT A(12),A(13),A(14),A(15),A(16)
1936 PRINT A(17),A(18),A(19),A(20),A(21)
1937 PRINT A(22),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31794 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 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31903
0 0 0 0 0
0 2 0 0 1
2 1 0 1 0
0 0 0 1 0
0 594 -31820
0 0 0 1 1
0 0 0 0 2
1 2 0 1 0
0 0 0 0 0
0 594 -31794
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=-31794 was ninety seconds, real time.
References
[1] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[2] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[3] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[4] 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.
Posted at 05:43 AM | Permalink | Comments (0)
