Jsun Yui Wong
Based on an earlier computer program [4], the computer program listed below seeks to solve the air transport model of Markowitz and Manne [1, pages 95-100].
One important goal of the present paper is to demonstrate the importance of a good upper bound for the IPP of line 133 of the following computer program, which is 133 FOR IPP=1 TO (1+FIX(RND*47)).
The following computer program uses qb64v1000-win [2, 3], which was also used for the preceding paper. .
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
15 RANDOMIZE JJJJ
16 M=-1D+37
41 FOR J44=1 TO 48
42 A(J44)=FIX(RND*3)
43 NEXT J44
51 FOR J44=37 TO 48
52 A(J44)=FIX(RND*3)
53 NEXT J44
126 IMAR=10+FIX(RND*5000)
128 FOR I=1 TO 1000
129 FOR KKQQ=1 TO 48
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*47))
181 J=1+FIX(RND*48)
183 R=(1-RND*2)*A(J)
187 X(J)=A(J)+(RND^3)*R
192 NEXT IPP
201 FOR J88=37 TO 48
203 X(J88)=CINT(X(J88) )
204 NEXT J88
211 X(43)=5-X(44)-X(45)
212 X(48)=X(43)+X(44)+X(45)-X(38)-X(41)
266 X(46)=X(37)+X(38)+X(39)-X(40)-X(43)
267 X(47)=X(40)+X(41)+X(42)-X(37)-X(44)
301 X(1)=X(20)+X(29)-X(4)-X(7)+6
302 X(5)=X(11)+X(30)-X(8)+6 -X(2)
303 X(9)=X(12)+X(21)-X(6)+6 -X(3)
304 X(10)=X(22)+X(31)-X(13)-X(16)+5
305 X(14) =X(2)-X(11)-X(17)+20 +X(33)
306 X(18) =X(24)+X(3)-X(12)-X(15)+31
307 X(19) =X(34)+X(13)-X(22)-X(25)+2
308 X(23)=X(4)+X(35)-X(20)-X(26)+24
309 X(27)=X(6)+X(15)-X(21)-X(24)+11
310 X(28)=X(16)+X(25)-X(31)-X(34)+14
311 X(32) = X(7)+X(26)-X(29)-X(35)+36
312 X(36) =X(8)+X(17)-X(30)-X(33)+7
371 FOR J44=1 TO 48
372 IF X(J44)<0 THEN 1670
373 NEXT J44
431 PS(21)=-7.5*X(37) +X(1) +X(2)+X(3)
432 PS(22)=-7.2*X(38)+X(4) +X(5) +X(6)
433 PS(23)=-7.5*X(39)+X(7)+X(8) +X(9)
434 PS(24)=-7.5*X(40) +X(10) +X(11)+X(12)
435 PS(25)=-7.5*X(41)+X(13) +X(14) +X(15)
436 PS(26)=-7.5*X(42)+X(16)+X(17) +X(18)
437 PS(27)=-7.2*X(43) +X(19) +X(20)+X(21)
438 PS(28)=-7.5*X(44)+X(22) +X(23) +X(24)
439 PS(29)=-5.6*X(45)+X(25)+X(26) +X(27)
440 PS(30)=-7.5*X(46) +X(28) +X(29)+X(30)
441 PS(31)=-7.5*X(47)+X(31) +X(32) +X(33)
442 PS(32)=-5.6*X(48)+X(34)+X(35) +X(36)
454 FOR J44=21 TO 32
455 IF PS(J44)>.00001 THEN PS(J44)=PS(J44) ELSE PS(J44)=0
456 NEXT J44
459 POB1=-4.5*X(37)- 8.3*X(38)- 2.9*X(39)- 4.5*X(40)- 4.2*X(41)- 6.9*X(42)- 8.3*X(43)-4.2*X(44)-10.9*X(45)- 2.9*X(46)- 6.9*X(47)- 10.9*X(48)
461 POB3=-999999999#*(PS(21)^4+PS(22)^4+PS(23)^4+PS(24)^4+PS(25)^4+PS(26)^4+PS(27)^4+PS(28)^4 +PS(29)^4+PS(30)^4+PS(31)^4+PS(32)^4 )
463 P1NEWMAY=POB1+POB3
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 48
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-153.6 THEN 1999
1900 GOTO 1945
1911 PRINT A(1),A(2),A(3),A(4),A(5)
1912 PRINT A(6),A(7),A(8),A(9),A(10)
1913 PRINT A(11),A(12),A(13),A(14),A(15)
1914 PRINT A(16),A(17),A(18),A(19),A(20)
1915 PRINT A(21),A(22),A(23),A(24),A(25)
1916 PRINT A(26),A(27),A(28),A(29),A(30)
1917 PRINT A(31),A(32),A(33),A(34),A(35)
1945 PRINT A(36),A(37),A(38),A(39),A(40)
1946 PRINT A(41),A(42),A(43),A(44),A(45)
1947 PRINT A(46),A(47),A(48),M,JJJJ
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [2, 3]. The complete output through JJJJ=32000 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
1.206398E-04 1 1 1
1
4 7 0 5 0
2 6 0 -153.5 -31813
5.514534 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -24022
5.319738 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -14995
5.566916 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 1616
5.520392 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 3032
5.572524 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 3391
4.567156 1 1 2 1
3 6 1 4 0
2 5 1 -153.4042 4833
5.430542 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 9738
9.421259E-06 1 1 2
1
4 6 1 4 0
2 6 0 -153.6 22722
5.342381 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 27450
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
At JJJJ=1616–and elsewhere–M=-153.3 is optimal. See Markowitz and Manne [1].
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [2, 3], the wall-clock time for obtaining the output through JJJJ=32000 was one hour.
The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*37)).
5.589005 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -31401
5.589306 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -29669
5.346732 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -18153
5.202597 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 -2954
4.632438 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 2903
5.489368 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 19948
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [2, 3], the wall-clock time for obtaining the output through JJJJ=32000 was 50 minutes.
The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*27)).
5.464866 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -19384
5.42462 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -18445
5.595021 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -7397
5.094746 1 1 1 1
3 7 0 5 0
2 5 1 -153.3001 3767
3.443135E-04 1 1 1
1
4 7 0 5 0
2 6 0 -153.5 23220
5.343966 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 23868
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [2, 3], the wall-clock time for obtaining the output through JJJJ=32000 was 42 minutes.
The following output was obtained by using the above computer program with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*17)).
5.315485 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -18672
4.69842 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 1011
4.99794 1 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 2446
4.990879 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 3451
5.560705 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 4059
5.028902 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 10682
4.923874 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 14955
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [2, 3], the wall-clock time for obtaining the output through JJJJ=32000 was 38 minutes.
The following output was obtained by using the above computer program with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*7)).
3.261672E-04 1 1 1
1
4 7 0 5 0
2 6 0 -153.5066 -16926
5.441607 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -5836
5.166392 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 4692
5.494189 1 1 2 1
3 6 1 4 0
2 5 1 -153.4 9590
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [2, 3], the wall-clock time for obtaining the output through JJJJ=32000 was 35 minutes.
The following output was obtained by using the above computer program with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*3)).
4.992488 1 1 1 1
3 7 0 5 0
2 5 1 -153.3034 6305
5.374687 1 1 1 1
3 7 0 5 0
2 5 1 -153.3001 11871
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [2, 3], the wall-clock time for obtaining the output through JJJJ=32000 was 38 minutes.
The following output was obtained by using the computer program above with its 133 FOR IPP=1 TO (1+FIX(RND*47)) replaced by 133 FOR IPP=1 TO (1+FIX(RND*.3)).
5.361702 1 1 2 1
3 6 1 4 0
2 5 1 -153.4011 -825
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [2, 3], the wall-clock time for obtaining the output through JJJJ=32000 was 48 minutes.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Harry M. Markowitz and Alan S. Mann. On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957) pp. 84-110.
[2] E.K. Virtanen (2008-05-26). “Interview With Galleon”,
http://www.basicprogramming.org/pcopy/issue70/#galleoninterview
[3] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[4] Jsun Yui Wong (2013, August 1). The Domino Method of General Integer Nonlinear Programming Applied to the Air Transport Model of Markowitz and Manne, Third Edition. http://myblogsubstance.typepad.com/substance/2013/08/
computerprogramsandresults 