Jsun Yui Wong
Based on an earlier computer program in Wong [4], the computer program listed below seeks to solve the air transport model of Markowitz and Manne [1, pages 95-100].
While the older paper [4] has 211 X(43) = 5 – X(44) – X(45), here line 211 is 211 REM X(43) = 5 – X(44) – X(45). That means X(43) = 5 – X(44) – X(45) from the extra analysis of Markowitz and Manne [1, p. 99] is not used in the present paper.
While the older paper [4] has 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), here line 461 is
461 POB3 = -999999999# * (1000 * PS(21) ^ 4 + 1000 * PS(22) ^ 4 + 1000 * PS(23) ^ 4 + 1000 * 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); the intent of this change is to get additional domino effect.
The following computer program uses qb64v1000-win [2, 3], which was also used for the older paper [4].
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
202 IF X(J88) > 100 THEN X(J88) = A(J88)
203 X(J88) = CINT(X(J88))
204 NEXT J88
211 REM 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 X(J44) = A(J44)
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)) > 0 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# * (1000 * PS(21) ^ 4 + 1000 * PS(22) ^ 4 + 1000 * PS(23) ^ 4 + 1000 * 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.
4.982793 1 1 1 1
3 7 0 5 0
2 5 1 -153.3 -10359
5.559741 1 1 1 1
3 7 0 5 0
2 5 1 -153.3046 11251
5.550361 1 1 1 1
3 7 0 5 0
2 5 1 -153.3034 24252
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
At JJJJ=-10359, 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 qb64v1000-win [2, 3], the wall-clock time for obtaining the output through JJJJ=32000 was 46 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 (2015, August 27). The Domino Method of General Integer Nonlinear Programming Applied to the Air Transport Model of Markowitz and Manne, Third Edition Extended. https://computerprogramsandresults.wordpress.com/2015/08/27/the-domino-method-of-general-integer-nonlinear-programming-applied-to-the-air-transport-model-of-markowitz-and-manne-third-edition-extended/
computerprogramsandresults 