Wong's LLLL Blog: August 2009

Sunday, August 30, 2009

Scheduling Thirty Activities among Seven Facilities

Jsun Yui Wong

The complete computer program listed below illustrates an algorithm for solving the Carlson and Nemhauser (1966) scheduling problem. The interaction costs in line 51 through line 195 are from Nugent, Vollmann, and Ruml (1968, p. 170); this illustration has thirty activities and seven facilities.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(466)
6 DIM TBM(33,33),TZ(33,33)
51 TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=4:TBM(1,6)=5:TBM(1,7)=1:TBM(1,8)=2:TBM(1,9)=3:TBM(1,10)=4
52 TBM(1,11)=5:TBM(1,12)=6:TBM(1,13)=2:TBM(1,14)=3:TBM(1,15)=4:TBM(1,16)=5:TBM(1,17)=6:TBM(1,18)=7:TBM(1,19)=3:TBM(1,20)=4
53 TBM(1,21)=5:TBM(1,22)=6:TBM(1,23)=7:TBM(1,24)=8:TBM(1,25)=4:TBM(1,26)=5:TBM(1,27)=6:TBM(1,28)=7:TBM(1,29)=8:TBM(1,30)=9
63 TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=3:TBM(2,6)=4:TBM(2,7)=2:TBM(2,8)=1:TBM(2,9)=2:TBM(2,10)=3
64 TBM(2,11)=4:TBM(2,12)=5:TBM(2,13)=3:TBM(2,14)=2:TBM(2,15)=3:TBM(2,16)=4:TBM(2,17)=5:TBM(2,18)=6:TBM(2,19)=4:TBM(2,20)=3
65 TBM(2,21)=4:TBM(2,22)=5:TBM(2,23)=6:TBM(2,24)=7:TBM(2,25)=5:TBM(2,26)=4:TBM(2,27)=5:TBM(2,28)=6:TBM(2,29)=7:TBM(2,30)=8
67 TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=3:TBM(3,7)=3:TBM(3,8)=2:TBM(3,9)=1:TBM(3,10)=2
68 TBM(3,11)=3:TBM(3,12)=4:TBM(3,13)=4:TBM(3,14)=3:TBM(3,15)=2:TBM(3,16)=3:TBM(3,17)=4:TBM(3,18)=5:TBM(3,19)=5:TBM(3,20)=4
69 TBM(3,21)=3:TBM(3,22)=4:TBM(3,23)=5:TBM(3,24)=6:TBM(3,25)=6:TBM(3,26)=5:TBM(3,27)=4:TBM(3,28)=5:TBM(3,29)=6:TBM(3,30)=7
77 TBM(4,5)=1:TBM(4,6)=2:TBM(4,7)=4:TBM(4,8)=3:TBM(4,9)=2:TBM(4,10)=1
78 TBM(4,11)=2:TBM(4,12)=3:TBM(4,13)=5:TBM(4,14)=4:TBM(4,15)=3:TBM(4,16)=2:TBM(4,17)=3:TBM(4,18)=4:TBM(4,19)=6:TBM(4,20)=5
79 TBM(4,21)=4:TBM(4,22)=3:TBM(4,23)=4:TBM(4,24)=5:TBM(4,25)=7:TBM(4,26)=6:TBM(4,27)=5:TBM(4,28)=4:TBM(4,29)=5:TBM(4,30)=6
81 TBM(5,1)=4:TBM(5,2)=3:TBM(5,3)=2:TBM(5,4)=1:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=5:TBM(5,8)=4:TBM(5,9)=3:TBM(5,10)=2
82 TBM(5,11)=1:TBM(5,12)=2:TBM(5,13)=6:TBM(5,14)=5:TBM(5,15)=4:TBM(5,16)=3:TBM(5,17)=2:TBM(5,18)=3:TBM(5,19)=7:TBM(5,20)=6
83 TBM(5,21)=5:TBM(5,22)=4:TBM(5,23)=3:TBM(5,24)=4:TBM(5,25)=8:TBM(5,26)=7:TBM(5,27)=6:TBM(5,28)=5:TBM(5,29)=4:TBM(5,30)=5
93 TBM(6,7)=6:TBM(6,8)=5:TBM(6,9)=4:TBM(6,10)=3
94 TBM(6,11)=2:TBM(6,12)=1:TBM(6,13)=7:TBM(6,14)=6:TBM(6,15)=5:TBM(6,16)=4:TBM(6,17)=3:TBM(6,18)=2:TBM(6,19)=8:TBM(6,20)=7
95 TBM(6,21)=6:TBM(6,22)=5:TBM(6,23)=4:TBM(6,24)=3:TBM(6,25)=9:TBM(6,26)=8:TBM(6,27)=7:TBM(6,28)=6:TBM(6,29)=5:TBM(6,30)=4
97 TBM(7,8)=1:TBM(7,9)=2:TBM(7,10)=3
98 TBM(7,11)=4:TBM(7,12)=5:TBM(7,13)=1:TBM(7,14)=2:TBM(7,15)=3:TBM(7,16)=4:TBM(7,17)=5:TBM(7,18)=6:TBM(7,19)=2:TBM(7,20)=3
99 TBM(7,21)=4:TBM(7,22)=5:TBM(7,23)=6:TBM(7,24)=7:TBM(7,25)=3:TBM(7,26)=4:TBM(7,27)=5:TBM(7,28)=6:TBM(7,29)=7:TBM(7,30)=8
101 TBM(8,9)=1:TBM(8,10)=2
102 TBM(8,11)=3:TBM(8,12)=4:TBM(8,13)=2:TBM(8,14)=1:TBM(8,15)=2:TBM(8,16)=3:TBM(8,17)=4:TBM(8,18)=5:TBM(8,19)=3:TBM(8,20)=2
103 TBM(8,21)=3:TBM(8,22)=4:TBM(8,23)=5:TBM(8,24)=6:TBM(8,25)=4:TBM(8,26)=3:TBM(8,27)=4:TBM(8,28)=5:TBM(8,29)=6:TBM(8,30)=7
105 TBM(9,10)=1
106 TBM(9,11)=2:TBM(9,12)=3:TBM(9,13)=3:TBM(9,14)=2:TBM(9,15)=1:TBM(9,16)=2:TBM(9,17)=3:TBM(9,18)=4:TBM(9,19)=4:TBM(9,20)=3
107 TBM(9,21)=2:TBM(9,22)=3:TBM(9,23)=4:TBM(9,24)=5:TBM(9,25)=5:TBM(9,26)=4:TBM(9,27)=3:TBM(9,28)=4:TBM(9,29)=5:TBM(9,30)=6
110 TBM(10,11)=1:TBM(10,12)=2:TBM(10,13)=4:TBM(10,14)=3:TBM(10,15)=2:TBM(10,16)=1:TBM(10,17)=2:TBM(10,18)=3:TBM(10,19)=5:TBM(10,20)=4
111 TBM(10,21)=3:TBM(10,22)=2:TBM(10,23)=3:TBM(10,24)=4:TBM(10,25)=6:TBM(10,26)=5:TBM(10,27)=4:TBM(10,28)=3:TBM(10,29)=4:TBM(10,30)=5
114 TBM(11,12)=1:TBM(11,13)=5:TBM(11,14)=4:TBM(11,15)=3:TBM(11,16)=2:TBM(11,17)=1:TBM(11,18)=2:TBM(11,19)=6:TBM(11,20)=5
115 TBM(11,21)=4:TBM(11,22)=3:TBM(11,23)=2:TBM(11,24)=3:TBM(11,25)=7:TBM(11,26)=6:TBM(11,27)=5:TBM(11,28)=4:TBM(11,29)=3:TBM(11,30)=4
118 TBM(12,13)=6:TBM(12,14)=5:TBM(12,15)=4:TBM(12,16)=3:TBM(12,17)=2:TBM(12,18)=1:TBM(12,19)=7:TBM(12,20)=6
119 TBM(12,21)=5:TBM(12,22)=4:TBM(12,23)=3:TBM(12,24)=2:TBM(12,25)=8:TBM(12,26)=7:TBM(12,27)=6:TBM(12,28)=5:TBM(12,29)=4:TBM(12,30)=3
122 TBM(13,14)=1:TBM(13,15)=2:TBM(13,16)=3:TBM(13,17)=4:TBM(13,18)=5:TBM(13,19)=1:TBM(13,20)=2
123 TBM(13,21)=3:TBM(13,22)=4:TBM(13,23)=5:TBM(13,24)=6:TBM(13,25)=2:TBM(13,26)=3:TBM(13,27)=4:TBM(13,28)=5:TBM(13,29)=6:TBM(13,30)=7
126 TBM(14,15)=1:TBM(14,16)=2:TBM(14,17)=3:TBM(14,18)=4:TBM(14,19)=2:TBM(14,20)=1
127 TBM(14,21)=2:TBM(14,22)=3:TBM(14,23)=4:TBM(14,24)=5:TBM(14,25)=3:TBM(14,26)=2:TBM(14,27)=3:TBM(14,28)=4:TBM(14,29)=5:TBM(14,30)=6
136 TBM(15,16)=1:TBM(15,17)=2:TBM(15,18)=3:TBM(15,19)=3:TBM(15,20)=2
137 TBM(15,21)=1:TBM(15,22)=2:TBM(15,23)=3:TBM(15,24)=4:TBM(15,25)=4:TBM(15,26)=3:TBM(15,27)=2:TBM(15,28)=3:TBM(15,29)=4:TBM(15,30)=5
140 TBM(16,17)=1:TBM(16,18)=2:TBM(16,19)=4:TBM(16,20)=3
141 TBM(16,21)=2:TBM(16,22)=1:TBM(16,23)=2:TBM(16,24)=3:TBM(16,25)=5:TBM(16,26)=4:TBM(16,27)=3:TBM(16,28)=2:TBM(16,29)=3:TBM(16,30)=4
144 TBM(17,18)=1:TBM(17,19)=5:TBM(17,20)=4
145 TBM(17,21)=3:TBM(17,22)=2:TBM(17,23)=1:TBM(17,24)=2:TBM(17,25)=6:TBM(17,26)=5:TBM(17,27)=4:TBM(17,28)=3:TBM(17,29)=2:TBM(17,30)=3
148 TBM(18,19)=6:TBM(18,20)=5
149 TBM(18,21)=4:TBM(18,22)=3:TBM(18,23)=2:TBM(18,24)=1:TBM(18,25)=7:TBM(18,26)=6:TBM(18,27)=5:TBM(18,28)=4:TBM(18,29)=3:TBM(18,30)=2
152 TBM(19,20)=1
153 TBM(19,21)=2:TBM(19,22)=3:TBM(19,23)=4:TBM(19,24)=5:TBM(19,25)=1:TBM(19,26)=2:TBM(19,27)=3:TBM(19,28)=4:TBM(19,29)=5:TBM(19,30)=6
157 TBM(20,21)=1:TBM(20,22)=2:TBM(20,23)=3:TBM(20,24)=4:TBM(20,25)=2:TBM(20,26)=1:TBM(20,27)=2:TBM(20,28)=3:TBM(20,29)=4:TBM(20,30)=5
163 TBM(21,22)=1:TBM(21,23)=2:TBM(21,24)=3:TBM(21,25)=3:TBM(21,26)=2:TBM(21,27)=1:TBM(21,28)=2:TBM(21,29)=3:TBM(21,30)=4
167 TBM(22,23)=1:TBM(22,24)=2:TBM(22,25)=4:TBM(22,26)=3:TBM(22,27)=2:TBM(22,28)=1:TBM(22,29)=2:TBM(22,30)=3
171 TBM(23,24)=1:TBM(23,25)=5:TBM(23,26)=4:TBM(23,27)=3:TBM(23,28)=2:TBM(23,29)=1:TBM(23,30)=2
175 TBM(24,25)=6:TBM(24,26)=5:TBM(24,27)=4:TBM(24,28)=3:TBM(24,29)=2:TBM(24,30)=1
179 TBM(25,26)=1:TBM(25,27)=2:TBM(25,28)=3:TBM(25,29)=4:TBM(25,30)=5
183 TBM(26,27)=1:TBM(26,28)=2:TBM(26,29)=3:TBM(26,30)=4
187 TBM(27,28)=1:TBM(27,29)=2:TBM(27,30)=3
191 TBM(28,29)=1:TBM(28,30)=2
195 TBM(29,30)=1
220 FOR JJJJ=-32000 TO 32000
221 RANDOMIZE JJJJ
222 M=-1D+17
223 FOR I=1 TO 30
224 A(I)=1+FIX(RND*7)
225 NEXT I
226 IMAR=10+FIX(RND*1000)
228 FOR I=1 TO IMAR
229 FOR KK=1 TO 30
231 X(KK)=A(KK)
232 NEXT KK
330 IJM=1+FIX(RND*30)
331 IJN=1+FIX(RND*30)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 30
361 FOR J=K+1 TO 30
363 IF X(K)=X(J) THEN TZ(K,J)=TBM(K,J) ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 30
1594 FOR J=K+1 TO 30
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1609 P=-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 30
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 228
1670 NEXT I
1890 IF M>-80 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1927 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solution produced during the first four hours of running is presented below. What immediately follows is a manual copy from the computer screen.

2 2 2 2 1
1 7 7 3 3
1 1 7 7 3
3 3 1 4 4
5 5 6 6 4
4 5 5 6 6
-74 -30740

74 may or may not be optimal. Interpreted in accordance with line 1912 through line 1927, the candidate solution presented above was produced during the first four hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Carlson, R. C., and G. L. Nemhauser, "Scheduling to Minimize Interaction Cost," Operations Research 14, 52-58 (Jan.-Feb., 1966).

Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).

Nugent, C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1968).

Vredeveld, T., and J. K. Lenstra, "On Local Search for the Generalized Graph Coloring Problem," Operations Research Letters 31, 28-34 (2003).

Saturday, August 29, 2009

A Computer Program for Solving a Scheduling Problem

A Computer Program for Scheduling To Minimize Interaction Cost

Jsun Yui Wong

The complete computer program listed below uses the example in Carlson and Nemhauser (1966) to illustrate an algorithm for its scheduling problem.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM TBM(33,33),TZ(33,33)
11 TBM(1,1)=0:TBM(1,2)=0:TBM(1,3)=2:TBM(1,4)=4:TBM(1,5)=3
12 TBM(2,1)=0:TBM(2,2)=0:TBM(2,3)=6:TBM(2,4)=2:TBM(2,5)=3
13 TBM(3,1)=2:TBM(3,2)=6:TBM(3,3)=0:TBM(3,4)=5:TBM(3,5)=3
14 TBM(4,1)=4:TBM(4,2)=2:TBM(4,3)=5:TBM(4,4)=0:TBM(4,5)=3
15 TBM(5,1)=3:TBM(5,2)=3:TBM(5,3)=3:TBM(5,4)=3:TBM(5,5)=0
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 5
87 A(I)=1+FIX(RND*3)
89 NEXT I
126 IMAR=10+FIX(RND*0)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
151 JK=1+FIX(RND*5)
153 X(JK)=1+FIX(RND*3)
330 IJM=1+FIX(RND*5)
331 IJN=1+FIX(RND*5)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 5
361 FOR J=1 TO 5
363 IF X(K)=X(J) THEN TZ(K,J)=TBM(K,J) ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 13
1594 FOR J=1 TO 13
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1609 P=-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-10 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1927 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first second of running is presented below. What immediately follows is a manual copy from the computer screen.

1 1 3 2 2
-6 -32000

2 2 1 3 3
-6 -31999

1 1 2 3 2
-6 -31998

3 3 1 2 2
-6 -31997

1 1 3 2 3
-6 -31996

1 3 1 3 2
-8 -31995

Interpreted in accordance with line 1912 and line 1927, the output through JJJJ=-31995 was produced during the first second of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

Carlson, R. C. and G. L. Nemhauser, "Scheduling to Minimize Interaction Cost," Operations Research 14, 52-58 (Jan.-Feb., 1966).

Friday, August 28, 2009

A Computer Program for Solving Integer Programs, Second Edition

Jsun Yui Wong

The computer program listed below seeks to solve the 30-department problem in Nugent, Vollmann, and Ruml (1968).

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(466)
6 DIM TBM(33,33)
51 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=4:TBM(1,6)=5:TBM(1,7)=1:TBM(1,8)=2:TBM(1,9)=3:TBM(1,10)=4
52 TBM(1,11)=5:TBM(1,12)=6:TBM(1,13)=2:TBM(1,14)=3:TBM(1,15)=4:TBM(1,16)=5:TBM(1,17)=6:TBM(1,18)=7:TBM(1,19)=3:TBM(1,20)=4
53 TBM(1,21)=5:TBM(1,22)=6:TBM(1,23)=7:TBM(1,24)=8:TBM(1,25)=4:TBM(1,26)=5:TBM(1,27)=6:TBM(1,28)=7:TBM(1,29)=8:TBM(1,30)=9
63 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=3:TBM(2,6)=4:TBM(2,7)=2:TBM(2,8)=1:TBM(2,9)=2:TBM(2,10)=3
64 TBM(2,11)=4:TBM(2,12)=5:TBM(2,13)=3:TBM(2,14)=2:TBM(2,15)=3:TBM(2,16)=4:TBM(2,17)=5:TBM(2,18)=6:TBM(2,19)=4:TBM(2,20)=3
65 TBM(2,21)=4:TBM(2,22)=5:TBM(2,23)=6:TBM(2,24)=7:TBM(2,25)=5:TBM(2,26)=4:TBM(2,27)=5:TBM(2,28)=6:TBM(2,29)=7:TBM(2,30)=8
67 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=3:TBM(3,7)=3:TBM(3,8)=2:TBM(3,9)=1:TBM(3,10)=2
68 TBM(3,11)=3:TBM(3,12)=4:TBM(3,13)=4:TBM(3,14)=3:TBM(3,15)=2:TBM(3,16)=3:TBM(3,17)=4:TBM(3,18)=5:TBM(3,19)=5:TBM(3,20)=4
69 TBM(3,21)=3:TBM(3,22)=4:TBM(3,23)=5:TBM(3,24)=6:TBM(3,25)=6:TBM(3,26)=5:TBM(3,27)=4:TBM(3,28)=5:TBM(3,29)=6:TBM(3,30)=7
77 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=1:TBM(4,6)=2:TBM(4,7)=4:TBM(4,8)=3:TBM(4,9)=2:TBM(4,10)=1
78 TBM(4,11)=2:TBM(4,12)=3:TBM(4,13)=5:TBM(4,14)=4:TBM(4,15)=3:TBM(4,16)=2:TBM(4,17)=3:TBM(4,18)=4:TBM(4,19)=6:TBM(4,20)=5
79 TBM(4,21)=4:TBM(4,22)=3:TBM(4,23)=4:TBM(4,24)=5:TBM(4,25)=7:TBM(4,26)=6:TBM(4,27)=5:TBM(4,28)=4:TBM(4,29)=5:TBM(4,30)=6
81 TBM(5,1)=4:TBM(5,2)=3:TBM(5,3)=2:TBM(5,4)=1:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=5:TBM(5,8)=4:TBM(5,9)=3:TBM(5,10)=2
82 TBM(5,11)=1:TBM(5,12)=2:TBM(5,13)=6:TBM(5,14)=5:TBM(5,15)=4:TBM(5,16)=3:TBM(5,17)=2:TBM(5,18)=3:TBM(5,19)=7:TBM(5,20)=6
83 TBM(5,21)=5:TBM(5,22)=4:TBM(5,23)=3:TBM(5,24)=4:TBM(5,25)=8:TBM(5,26)=7:TBM(5,27)=6:TBM(5,28)=5:TBM(5,29)=4:TBM(5,30)=5
93 TBM(6,1)=5:TBM(6,2)=4:TBM(6,3)=3:TBM(6,4)=2:TBM(6,5)=1:TBM(6,6)=999:TBM(6,7)=6:TBM(6,8)=5:TBM(6,9)=4:TBM(6,10)=3
94 TBM(6,11)=2:TBM(6,12)=1:TBM(6,13)=7:TBM(6,14)=6:TBM(6,15)=5:TBM(6,16)=4:TBM(6,17)=3:TBM(6,18)=2:TBM(6,19)=8:TBM(6,20)=7
95 TBM(6,21)=6:TBM(6,22)=5:TBM(6,23)=4:TBM(6,24)=3:TBM(6,25)=9:TBM(6,26)=8:TBM(6,27)=7:TBM(6,28)=6:TBM(6,29)=5:TBM(6,30)=4
97 TBM(7,1)=1:TBM(7,2)=2:TBM(7,3)=3:TBM(7,4)=4:TBM(7,5)=5:TBM(7,6)=6:TBM(7,7)=999:TBM(7,8)=1:TBM(7,9)=2:TBM(7,10)=3
98 TBM(7,11)=4:TBM(7,12)=5:TBM(7,13)=1:TBM(7,14)=2:TBM(7,15)=3:TBM(7,16)=4:TBM(7,17)=5:TBM(7,18)=6:TBM(7,19)=2:TBM(7,20)=3
99 TBM(7,21)=4:TBM(7,22)=5:TBM(7,23)=6:TBM(7,24)=7:TBM(7,25)=3:TBM(7,26)=4:TBM(7,27)=5:TBM(7,28)=6:TBM(7,29)=7:TBM(7,30)=8
101 TBM(8,1)=2:TBM(8,2)=1:TBM(8,3)=2:TBM(8,4)=3:TBM(8,5)=4:TBM(8,6)=5:TBM(8,7)=1:TBM(8,8)=999:TBM(8,9)=1:TBM(8,10)=2
102 TBM(8,11)=3:TBM(8,12)=4:TBM(8,13)=2:TBM(8,14)=1:TBM(8,15)=2:TBM(8,16)=3:TBM(8,17)=4:TBM(8,18)=5:TBM(8,19)=3:TBM(8,20)=2
103 TBM(8,21)=3:TBM(8,22)=4:TBM(8,23)=5:TBM(8,24)=6:TBM(8,25)=4:TBM(8,26)=3:TBM(8,27)=4:TBM(8,28)=5:TBM(8,29)=6:TBM(8,30)=7
105 TBM(9,1)=3:TBM(9,2)=2:TBM(9,3)=1:TBM(9,4)=2:TBM(9,5)=3:TBM(9,6)=4:TBM(9,7)=2:TBM(9,8)=1:TBM(9,9)=999:TBM(9,10)=1
106 TBM(9,11)=2:TBM(9,12)=3:TBM(9,13)=3:TBM(9,14)=2:TBM(9,15)=1:TBM(9,16)=2:TBM(9,17)=3:TBM(9,18)=4:TBM(9,19)=4:TBM(9,20)=3
107 TBM(9,21)=2:TBM(9,22)=3:TBM(9,23)=4:TBM(9,24)=5:TBM(9,25)=5:TBM(9,26)=4:TBM(9,27)=3:TBM(9,28)=4:TBM(9,29)=5:TBM(9,30)=6
109 TBM(10,1)=4:TBM(10,2)=3:TBM(10,3)=2:TBM(10,4)=1:TBM(10,5)=2:TBM(10,6)=3:TBM(10,7)=3:TBM(10,8)=2:TBM(10,9)=1:TBM(10,10)=999
110 TBM(10,11)=1:TBM(10,12)=2:TBM(10,13)=4:TBM(10,14)=3:TBM(10,15)=2:TBM(10,16)=1:TBM(10,17)=2:TBM(10,18)=3:TBM(10,19)=5:TBM(10,20)=4
111 TBM(10,21)=3:TBM(10,22)=2:TBM(10,23)=3:TBM(10,24)=4:TBM(10,25)=6:TBM(10,26)=5:TBM(10,27)=4:TBM(10,28)=3:TBM(10,29)=4:TBM(10,30)=5
113 TBM(11,1)=5:TBM(11,2)=4:TBM(11,3)=3:TBM(11,4)=2:TBM(11,5)=1:TBM(11,6)=2:TBM(11,7)=4:TBM(11,8)=3:TBM(11,9)=2:TBM(11,10)=1
114 TBM(11,11)=999:TBM(11,12)=1:TBM(11,13)=5:TBM(11,14)=4:TBM(11,15)=3:TBM(11,16)=2:TBM(11,17)=1:TBM(11,18)=2:TBM(11,19)=6:TBM(11,20)=5
115 TBM(11,21)=4:TBM(11,22)=3:TBM(11,23)=2:TBM(11,24)=3:TBM(11,25)=7:TBM(11,26)=6:TBM(11,27)=5:TBM(11,28)=4:TBM(11,29)=3:TBM(11,30)=4
117 TBM(12,1)=6:TBM(12,2)=5:TBM(12,3)=4:TBM(12,4)=3:TBM(12,5)=2:TBM(12,6)=1:TBM(12,7)=5:TBM(12,8)=4:TBM(12,9)=3:TBM(12,10)=2
118 TBM(12,11)=1:TBM(12,12)=999:TBM(12,13)=6:TBM(12,14)=5:TBM(12,15)=4:TBM(12,16)=3:TBM(12,17)=2:TBM(12,18)=1:TBM(12,19)=7:TBM(12,20)=6
119 TBM(12,21)=5:TBM(12,22)=4:TBM(12,23)=3:TBM(12,24)=2:TBM(12,25)=8:TBM(12,26)=7:TBM(12,27)=6:TBM(12,28)=5:TBM(12,29)=4:TBM(12,30)=3
121 TBM(13,1)=2:TBM(13,2)=3:TBM(13,3)=4:TBM(13,4)=5:TBM(13,5)=6:TBM(13,6)=7:TBM(13,7)=1:TBM(13,8)=2:TBM(13,9)=3:TBM(13,10)=4
122 TBM(13,11)=5:TBM(13,12)=6:TBM(13,13)=999:TBM(13,14)=1:TBM(13,15)=2:TBM(13,16)=3:TBM(13,17)=4:TBM(13,18)=5:TBM(13,19)=1:TBM(13,20)=2
123 TBM(13,21)=3:TBM(13,22)=4:TBM(13,23)=5:TBM(13,24)=6:TBM(13,25)=2:TBM(13,26)=3:TBM(13,27)=4:TBM(13,28)=5:TBM(13,29)=6:TBM(13,30)=7
125 TBM(14,1)=3:TBM(14,2)=2:TBM(14,3)=3:TBM(14,4)=4:TBM(14,5)=5:TBM(14,6)=6:TBM(14,7)=2:TBM(14,8)=1:TBM(14,9)=2:TBM(14,10)=3
126 TBM(14,11)=4:TBM(14,12)=5:TBM(14,13)=1:TBM(14,14)=999:TBM(14,15)=1:TBM(14,16)=2:TBM(14,17)=3:TBM(14,18)=4:TBM(14,19)=2:TBM(14,20)=1
127 TBM(14,21)=2:TBM(14,22)=3:TBM(14,23)=4:TBM(14,24)=5:TBM(14,25)=3:TBM(14,26)=2:TBM(14,27)=3:TBM(14,28)=4:TBM(14,29)=5:TBM(14,30)=6
135 TBM(15,1)=4:TBM(15,2)=3:TBM(15,3)=2:TBM(15,4)=3:TBM(15,5)=4:TBM(15,6)=5:TBM(15,7)=3:TBM(15,8)=2:TBM(15,9)=1:TBM(15,10)=2
136 TBM(15,11)=3:TBM(15,12)=4:TBM(15,13)=2:TBM(15,14)=1:TBM(15,15)=999:TBM(15,16)=1:TBM(15,17)=2:TBM(15,18)=3:TBM(15,19)=3:TBM(15,20)=2
137 TBM(15,21)=1:TBM(15,22)=2:TBM(15,23)=3:TBM(15,24)=4:TBM(15,25)=4:TBM(15,26)=3:TBM(15,27)=2:TBM(15,28)=3:TBM(15,29)=4:TBM(15,30)=5
139 TBM(16,1)=5:TBM(16,2)=4:TBM(16,3)=3:TBM(16,4)=2:TBM(16,5)=3:TBM(16,6)=4:TBM(16,7)=4:TBM(16,8)=3:TBM(16,9)=2:TBM(16,10)=1
140 TBM(16,11)=2:TBM(16,12)=3:TBM(16,13)=3:TBM(16,14)=2:TBM(16,15)=1:TBM(16,16)=999:TBM(16,17)=1:TBM(16,18)=2:TBM(16,19)=4:TBM(16,20)=3
141 TBM(16,21)=2:TBM(16,22)=1:TBM(16,23)=2:TBM(16,24)=3:TBM(16,25)=5:TBM(16,26)=4:TBM(16,27)=3:TBM(16,28)=2:TBM(16,29)=3:TBM(16,30)=4
143 TBM(17,1)=6:TBM(17,2)=5:TBM(17,3)=4:TBM(17,4)=3:TBM(17,5)=2:TBM(17,6)=3:TBM(17,7)=5:TBM(17,8)=4:TBM(17,9)=3:TBM(17,10)=2
144 TBM(17,11)=1:TBM(17,12)=2:TBM(17,13)=4:TBM(17,14)=3:TBM(17,15)=2:TBM(17,16)=1:TBM(17,17)=999:TBM(17,18)=1:TBM(17,19)=5:TBM(17,20)=4
145 TBM(17,21)=3:TBM(17,22)=2:TBM(17,23)=1:TBM(17,24)=2:TBM(17,25)=6:TBM(17,26)=5:TBM(17,27)=4:TBM(17,28)=3:TBM(17,29)=2:TBM(17,30)=3
147 TBM(18,1)=7:TBM(18,2)=6:TBM(18,3)=5:TBM(18,4)=4:TBM(18,5)=3:TBM(18,6)=2:TBM(18,7)=6:TBM(18,8)=5:TBM(18,9)=4:TBM(18,10)=3
148 TBM(18,11)=2:TBM(18,12)=1:TBM(18,13)=5:TBM(18,14)=4:TBM(18,15)=3:TBM(18,16)=2:TBM(18,17)=1:TBM(18,18)=999:TBM(18,19)=6:TBM(18,20)=5
149 TBM(18,21)=4:TBM(18,22)=3:TBM(18,23)=2:TBM(18,24)=1:TBM(18,25)=7:TBM(18,26)=6:TBM(18,27)=5:TBM(18,28)=4:TBM(18,29)=3:TBM(18,30)=2
151 TBM(19,1)=3:TBM(19,2)=4:TBM(19,3)=5:TBM(19,4)=6:TBM(19,5)=7:TBM(19,6)=8:TBM(19,7)=2:TBM(19,8)=3:TBM(19,9)=4:TBM(19,10)=5
152 TBM(19,11)=6:TBM(19,12)=7:TBM(19,13)=1:TBM(19,14)=2:TBM(19,15)=3:TBM(19,16)=4:TBM(19,17)=5:TBM(19,18)=6:TBM(19,19)=999:TBM(19,20)=1
153 TBM(19,21)=2:TBM(19,22)=3:TBM(19,23)=4:TBM(19,24)=5:TBM(19,25)=1:TBM(19,26)=2:TBM(19,27)=3:TBM(19,28)=4:TBM(19,29)=5:TBM(19,30)=6
155 TBM(20,1)=4:TBM(20,2)=3:TBM(20,3)=4:TBM(20,4)=5:TBM(20,5)=6:TBM(20,6)=7:TBM(20,7)=3:TBM(20,8)=2:TBM(20,9)=3:TBM(20,10)=4
156 TBM(20,11)=5:TBM(20,12)=6:TBM(20,13)=2:TBM(20,14)=1:TBM(20,15)=2:TBM(20,16)=3:TBM(20,17)=4:TBM(20,18)=5:TBM(20,19)=1:TBM(20,20)=999
157 TBM(20,21)=1:TBM(20,22)=2:TBM(20,23)=3:TBM(20,24)=4:TBM(20,25)=2:TBM(20,26)=1:TBM(20,27)=2:TBM(20,28)=3:TBM(20,29)=4:TBM(20,30)=5
161 TBM(21,1)=5:TBM(21,2)=4:TBM(21,3)=3:TBM(21,4)=4:TBM(21,5)=5:TBM(21,6)=6:TBM(21,7)=4:TBM(21,8)=3:TBM(21,9)=2:TBM(21,10)=3
162 TBM(21,11)=4:TBM(21,12)=5:TBM(21,13)=3:TBM(21,14)=2:TBM(21,15)=1:TBM(21,16)=2:TBM(21,17)=3:TBM(21,18)=4:TBM(21,19)=2:TBM(21,20)=1
163 TBM(21,21)=999:TBM(21,22)=1:TBM(21,23)=2:TBM(21,24)=3:TBM(21,25)=3:TBM(21,26)=2:TBM(21,27)=1:TBM(21,28)=2:TBM(21,29)=3:TBM(21,30)=4
165 TBM(22,1)=6:TBM(22,2)=5:TBM(22,3)=4:TBM(22,4)=3:TBM(22,5)=4:TBM(22,6)=5:TBM(22,7)=5:TBM(22,8)=4:TBM(22,9)=3:TBM(22,10)=2
166 TBM(22,11)=3:TBM(22,12)=4:TBM(22,13)=4:TBM(22,14)=3:TBM(22,15)=2:TBM(22,16)=1:TBM(22,17)=2:TBM(22,18)=3:TBM(22,19)=3:TBM(22,20)=2
167 TBM(22,21)=1:TBM(22,22)=999:TBM(22,23)=1:TBM(22,24)=2:TBM(22,25)=4:TBM(22,26)=3:TBM(22,27)=2:TBM(22,28)=1:TBM(22,29)=2:TBM(22,30)=3
169 TBM(23,1)=7:TBM(23,2)=6:TBM(23,3)=5:TBM(23,4)=4:TBM(23,5)=3:TBM(23,6)=4:TBM(23,7)=6:TBM(23,8)=5:TBM(23,9)=4:TBM(23,10)=3
170 TBM(23,11)=2:TBM(23,12)=3:TBM(23,13)=5:TBM(23,14)=4:TBM(23,15)=3:TBM(23,16)=2:TBM(23,17)=1:TBM(23,18)=2:TBM(23,19)=4:TBM(23,20)=3
171 TBM(23,21)=2:TBM(23,22)=1:TBM(23,23)=999:TBM(23,24)=1:TBM(23,25)=5:TBM(23,26)=4:TBM(23,27)=3:TBM(23,28)=2:TBM(23,29)=1:TBM(23,30)=2
173 TBM(24,1)=8:TBM(24,2)=7:TBM(24,3)=6:TBM(24,4)=5:TBM(24,5)=4:TBM(24,6)=3:TBM(24,7)=7:TBM(24,8)=6:TBM(24,9)=5:TBM(24,10)=4
174 TBM(24,11)=3:TBM(24,12)=2:TBM(24,13)=6:TBM(24,14)=5:TBM(24,15)=4:TBM(24,16)=3:TBM(24,17)=2:TBM(24,18)=1:TBM(24,19)=5:TBM(24,20)=4
175 TBM(24,21)=3:TBM(24,22)=2:TBM(24,23)=1:TBM(24,24)=999:TBM(24,25)=6:TBM(24,26)=5:TBM(24,27)=4:TBM(24,28)=3:TBM(24,29)=2:TBM(24,30)=1
177 TBM(25,1)=4:TBM(25,2)=5:TBM(25,3)=6:TBM(25,4)=7:TBM(25,5)=8:TBM(25,6)=9:TBM(25,7)=3:TBM(25,8)=4:TBM(25,9)=5:TBM(25,10)=6
178 TBM(25,11)=7:TBM(25,12)=8:TBM(25,13)=2:TBM(25,14)=3:TBM(25,15)=4:TBM(25,16)=5:TBM(25,17)=6:TBM(25,18)=7:TBM(25,19)=1:TBM(25,20)=2
179 TBM(25,21)=3:TBM(25,22)=4:TBM(25,23)=5:TBM(25,24)=6:TBM(25,25)=999:TBM(25,26)=1:TBM(25,27)=2:TBM(25,28)=3:TBM(25,29)=4:TBM(25,30)=5
181 TBM(26,1)=5:TBM(26,2)=4:TBM(26,3)=5:TBM(26,4)=6:TBM(26,5)=7:TBM(26,6)=8:TBM(26,7)=4:TBM(26,8)=3:TBM(26,9)=4:TBM(26,10)=5
182 TBM(26,11)=6:TBM(26,12)=7:TBM(26,13)=3:TBM(26,14)=2:TBM(26,15)=3:TBM(26,16)=4:TBM(26,17)=5:TBM(26,18)=6:TBM(26,19)=2:TBM(26,20)=1
183 TBM(26,21)=2:TBM(26,22)=3:TBM(26,23)=4:TBM(26,24)=5:TBM(26,25)=1:TBM(26,26)=999:TBM(26,27)=1:TBM(26,28)=2:TBM(26,29)=3:TBM(26,30)=4
185 TBM(27,1)=6:TBM(27,2)=5:TBM(27,3)=4:TBM(27,4)=5:TBM(27,5)=6:TBM(27,6)=7:TBM(27,7)=5:TBM(27,8)=4:TBM(27,9)=3:TBM(27,10)=4
186 TBM(27,11)=5:TBM(27,12)=6:TBM(27,13)=4:TBM(27,14)=3:TBM(27,15)=2:TBM(27,16)=3:TBM(27,17)=4:TBM(27,18)=5:TBM(27,19)=3:TBM(27,20)=2
187 TBM(27,21)=1:TBM(27,22)=2:TBM(27,23)=3:TBM(27,24)=4:TBM(27,25)=2:TBM(27,26)=1:TBM(27,27)=999:TBM(27,28)=1:TBM(27,29)=2:TBM(27,30)=3
189 TBM(28,1)=7:TBM(28,2)=6:TBM(28,3)=5:TBM(28,4)=4:TBM(28,5)=5:TBM(28,6)=6:TBM(28,7)=6:TBM(28,8)=5:TBM(28,9)=4:TBM(28,10)=3
190 TBM(28,11)=4:TBM(28,12)=5:TBM(28,13)=5:TBM(28,14)=4:TBM(28,15)=3:TBM(28,16)=2:TBM(28,17)=3:TBM(28,18)=4:TBM(28,19)=4:TBM(28,20)=3
191 TBM(28,21)=2:TBM(28,22)=1:TBM(28,23)=2:TBM(28,24)=3:TBM(28,25)=3:TBM(28,26)=2:TBM(28,27)=1:TBM(28,28)=999:TBM(28,29)=1:TBM(28,30)=2
193 TBM(29,1)=8:TBM(29,2)=7:TBM(29,3)=6:TBM(29,4)=5:TBM(29,5)=4:TBM(29,6)=5:TBM(29,7)=7:TBM(29,8)=6:TBM(29,9)=5:TBM(29,10)=4
194 TBM(29,11)=3:TBM(29,12)=4:TBM(29,13)=6:TBM(29,14)=5:TBM(29,15)=4:TBM(29,16)=3:TBM(29,17)=2:TBM(29,18)=3:TBM(29,19)=5:TBM(29,20)=4
195 TBM(29,21)=3:TBM(29,22)=2:TBM(29,23)=1:TBM(29,24)=2:TBM(29,25)=4:TBM(29,26)=3:TBM(29,27)=2:TBM(29,28)=1:TBM(29,29)=999:TBM(29,30)=1
197 TBM(30,1)=9:TBM(30,2)=8:TBM(30,3)=7:TBM(30,4)=6:TBM(30,5)=5:TBM(30,6)=4:TBM(30,7)=8:TBM(30,8)=7:TBM(30,9)=6:TBM(30,10)=5
198 TBM(30,11)=4:TBM(30,12)=3:TBM(30,13)=7:TBM(30,14)=6:TBM(30,15)=5:TBM(30,16)=4:TBM(30,17)=3:TBM(30,18)=2:TBM(30,19)=6:TBM(30,20)=5
199 TBM(30,21)=4:TBM(30,22)=3:TBM(30,23)=2:TBM(30,24)=1:TBM(30,25)=5:TBM(30,26)=4:TBM(30,27)=3:TBM(30,28)=2:TBM(30,29)=1:TBM(30,30)=999
220 FOR JJJJ=-32000 TO 32000
221 RANDOMIZE JJJJ
222 M=-1D+17
223 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
224 A(11)=11:A(12)=12:A(13)=13:A(14)=14:A(15)=15:A(16)=16:A(17)=17:A(18)=18:A(19)=19:A(20)=20
225 A(21)=21:A(22)=22:A(23)=23:A(24)=24:A(25)=25:A(26)=26:A(27)=27:A(28)=28:A(29)=29:A(30)=30
226 IMAR=10+FIX(RND*5000)
228 FOR I=1 TO IMAR
229 FOR KK=1 TO 30
231 X(KK)=A(KK)
232 NEXT KK
330 IJM=1+FIX(RND*30)
331 IJN=1+FIX(RND*30)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=3*TBM(X(1),X(2))
402 T(2)=2*TBM(X(1),X(3))
403 T(3)=0*TBM(X(1),X(4))
404 T(4)=0*TBM(X(1),X(5))
405 T(5)=2*TBM(X(1),X(6))
406 T(6)=10*TBM(X(1),X(7))
407 T(7)=5*TBM(X(1),X(8))
408 T(8)=0*TBM(X(1),X(9))
409 T(9)=5*TBM(X(1),X(10))
410 T(10)=2*TBM(X(1),X(11))
411 T(11)=5*TBM(X(1),X(12))
412 T(12)=0*TBM(X(1),X(13))
413 T(13)=0*TBM(X(1),X(14))
414 T(14)=2*TBM(X(1),X(15))
415 T(15)=0*TBM(X(1),X(16))
416 T(16)=5*TBM(X(1),X(17))
417 T(17)=6*TBM(X(1),X(18))
418 T(18)=3*TBM(X(1),X(19))
419 T(19)=0*TBM(X(1),X(20))
420 T(20)=1*TBM(X(1),X(21))
421 T(21)=10*TBM(X(1),X(22))
422 T(22)=0*TBM(X(1),X(23))
423 T(23)=10*TBM(X(1),X(24))
424 T(24)=2*TBM(X(1),X(25))
425 T(25)=1*TBM(X(1),X(26))
426 T(26)=1*TBM(X(1),X(27))
427 T(27)=1*TBM(X(1),X(28))
428 T(28)=0*TBM(X(1),X(29))
429 T(29)=1*TBM(X(1),X(30))
615 T(30)=4*TBM(X(2),X(3))
616 T(31)=0*TBM(X(2),X(4))
617 T(32)=10*TBM(X(2),X(5))
618 T(33)=4*TBM(X(2),X(6))
619 T(34)=0*TBM(X(2),X(7))
620 T(35)=0*TBM(X(2),X(8))
621 T(36)=2*TBM(X(2),X(9))
622 T(37)=2*TBM(X(2),X(10))
623 T(38)=1*TBM(X(2),X(11))
624 T(39)=0*TBM(X(2),X(12))
625 T(40)=5*TBM(X(2),X(13))
626 T(41)=0*TBM(X(2),X(14))
627 T(42)=0*TBM(X(2),X(15))
628 T(43)=0*TBM(X(2),X(16))
629 T(44)=0*TBM(X(2),X(17))
630 T(45)=2*TBM(X(2),X(18))
631 T(46)=0*TBM(X(2),X(19))
632 T(47)=1*TBM(X(2),X(20))
633 T(48)=6*TBM(X(2),X(21))
634 T(49)=1*TBM(X(2),X(22))
635 T(50)=0*TBM(X(2),X(23))
636 T(51)=1*TBM(X(2),X(24))
637 T(52)=2*TBM(X(2),X(25))
638 T(53)=2*TBM(X(2),X(26))
639 T(54)=5*TBM(X(2),X(27))
640 T(55)=1*TBM(X(2),X(28))
641 T(56)=10*TBM(X(2),X(29))
642 T(57)=5*TBM(X(2),X(30))
648 T(58)=3*TBM(X(3),X(4))
649 T(59)=4*TBM(X(3),X(5))
650 T(60)=0*TBM(X(3),X(6))
651 T(61)=5*TBM(X(3),X(7))
652 T(62)=5*TBM(X(3),X(8))
653 T(63)=5*TBM(X(3),X(9))
654 T(64)=1*TBM(X(3),X(10))
655 T(65)=4*TBM(X(3),X(11))
656 T(66)=1*TBM(X(3),X(12))
657 T(67)=0*TBM(X(3),X(13))
658 T(68)=4*TBM(X(3),X(14))
659 T(69)=0*TBM(X(3),X(15))
660 T(70)=4*TBM(X(3),X(16))
661 T(71)=0*TBM(X(3),X(17))
662 T(72)=6*TBM(X(3),X(18))
663 T(73)=3*TBM(X(3),X(19))
664 T(74)=2*TBM(X(3),X(20))
665 T(75)=5*TBM(X(3),X(21))
666 T(76)=5*TBM(X(3),X(22))
667 T(77)=2*TBM(X(3),X(23))
668 T(78)=1*TBM(X(3),X(24))
669 T(79)=0*TBM(X(3),X(25))
670 T(80)=0*TBM(X(3),X(26))
671 T(81)=3*TBM(X(3),X(27))
678 T(82)=1*TBM(X(3),X(28))
679 T(83)=0*TBM(X(3),X(29))
680 T(84)=2*TBM(X(3),X(30))
740 T(85)=0*TBM(X(4),X(5))
741 T(86)=0*TBM(X(4),X(6))
742 T(87)=0*TBM(X(4),X(7))
743 T(88)=2*TBM(X(4),X(8))
744 T(89)=2*TBM(X(4),X(9))
745 T(90)=0*TBM(X(4),X(10))
746 T(91)=6*TBM(X(4),X(11))
747 T(92)=0*TBM(X(4),X(12))
748 T(93)=2*TBM(X(4),X(13))
749 T(94)=5*TBM(X(4),X(14))
750 T(95)=2*TBM(X(4),X(15))
751 T(96)=5*TBM(X(4),X(16))
752 T(97)=1*TBM(X(4),X(17))
753 T(98)=1*TBM(X(4),X(18))
754 T(99)=1*TBM(X(4),X(19))
755 T(100)=1*TBM(X(4),X(20))
756 T(101)=2*TBM(X(4),X(21))
757 T(102)=2*TBM(X(4),X(22))
758 T(103)=4*TBM(X(4),X(23))
759 T(104)=0*TBM(X(4),X(24))
760 T(105)=2*TBM(X(4),X(25))
761 T(106)=0*TBM(X(4),X(26))
762 T(107)=2*TBM(X(4),X(27))
763 T(108)=2*TBM(X(4),X(28))
764 T(109)=5*TBM(X(4),X(29))
765 T(110)=5*TBM(X(4),X(30))
851 T(111)=5*TBM(X(5),X(6))
852 T(112)=2*TBM(X(5),X(7))
853 T(113)=0*TBM(X(5),X(8))
854 T(114)=0*TBM(X(5),X(9))
855 T(115)=0*TBM(X(5),X(10))
856 T(116)=0*TBM(X(5),X(11))
857 T(117)=2*TBM(X(5),X(12))
858 T(118)=0*TBM(X(5),X(13))
859 T(119)=0*TBM(X(5),X(14))
860 T(120)=0*TBM(X(5),X(15))
861 T(121)=0*TBM(X(5),X(16))
862 T(122)=2*TBM(X(5),X(17))
863 T(123)=1*TBM(X(5),X(18))
864 T(124)=0*TBM(X(5),X(19))
865 T(125)=0*TBM(X(5),X(20))
866 T(126)=2*TBM(X(5),X(21))
867 T(127)=0*TBM(X(5),X(22))
868 T(128)=5*TBM(X(5),X(23))
869 T(129)=1*TBM(X(5),X(24))
870 T(130)=0*TBM(X(5),X(25))
871 T(131)=2*TBM(X(5),X(26))
872 T(132)=1*TBM(X(5),X(27))
873 T(133)=0*TBM(X(5),X(28))
874 T(134)=2*TBM(X(5),X(29))
875 T(135)=1*TBM(X(5),X(30))
961 T(136)=1*TBM(X(6),X(7))
962 T(137)=2*TBM(X(6),X(8))
963 T(138)=2*TBM(X(6),X(9))
964 T(139)=1*TBM(X(6),X(10))
965 T(140)=4*TBM(X(6),X(11))
966 T(141)=10*TBM(X(6),X(12))
967 T(142)=10*TBM(X(6),X(13))
968 T(143)=2*TBM(X(6),X(14))
969 T(144)=5*TBM(X(6),X(15))
970 T(145)=5*TBM(X(6),X(16))
971 T(146)=0*TBM(X(6),X(17))
972 T(147)=5*TBM(X(6),X(18))
973 T(148)=0*TBM(X(6),X(19))
974 T(149)=0*TBM(X(6),X(20))
975 T(150)=0*TBM(X(6),X(21))
976 T(151)=10*TBM(X(6),X(22))
977 T(152)=0*TBM(X(6),X(23))
978 T(153)=0*TBM(X(6),X(24))
979 T(154)=0*TBM(X(6),X(25))
980 T(155)=4*TBM(X(6),X(26))
981 T(156)=0*TBM(X(6),X(27))
982 T(157)=10*TBM(X(6),X(28))
983 T(158)=1*TBM(X(6),X(29))
984 T(159)=1*TBM(X(6),X(30))
1047 T(160)=10*TBM(X(7),X(8))
1048 T(161)=10*TBM(X(7),X(9))
1051 T(162)=5*TBM(X(7),X(10))
1052 T(163)=10*TBM(X(7),X(11))
1053 T(164)=10*TBM(X(7),X(12))
1054 T(165)=6*TBM(X(7),X(13))
1055 T(166)=0*TBM(X(7),X(14))
1056 T(167)=0*TBM(X(7),X(15))
1057 T(168)=10*TBM(X(7),X(16))
1058 T(169)=2*TBM(X(7),X(17))
1059 T(170)=1*TBM(X(7),X(18))
1060 T(171)=10*TBM(X(7),X(19))
1061 T(172)=1*TBM(X(7),X(20))
1062 T(173)=5*TBM(X(7),X(21))
1063 T(174)=5*TBM(X(7),X(22))
1064 T(175)=2*TBM(X(7),X(23))
1065 T(176)=3*TBM(X(7),X(24))
1066 T(177)=5*TBM(X(7),X(25))
1067 T(178)=0*TBM(X(7),X(26))
1068 T(179)=2*TBM(X(7),X(27))
1069 T(180)=0*TBM(X(7),X(28))
1070 T(181)=1*TBM(X(7),X(29))
1071 T(182)=3*TBM(X(7),X(30))
1077 T(183)=1*TBM(X(8),X(9))
1078 T(184)=3*TBM(X(8),X(10))
1079 T(185)=5*TBM(X(8),X(11))
1080 T(186)=0*TBM(X(8),X(12))
1081 T(187)=0*TBM(X(8),X(13))
1082 T(188)=0*TBM(X(8),X(14))
1083 T(189)=2*TBM(X(8),X(15))
1084 T(190)=4*TBM(X(8),X(16))
1085 T(191)=5*TBM(X(8),X(17))
1086 T(192)=2*TBM(X(8),X(18))
1087 T(193)=10*TBM(X(8),X(19))
1088 T(194)=6*TBM(X(8),X(20))
1089 T(195)=0*TBM(X(8),X(21))
1090 T(196)=5*TBM(X(8),X(22))
1091 T(197)=5*TBM(X(8),X(23))
1092 T(198)=2*TBM(X(8),X(24))
1093 T(199)=5*TBM(X(8),X(25))
1094 T(200)=0*TBM(X(8),X(26))
1095 T(201)=5*TBM(X(8),X(27))
1096 T(202)=5*TBM(X(8),X(28))
1097 T(203)=0*TBM(X(8),X(29))
1098 T(204)=2*TBM(X(8),X(30))
1114 T(205)=10*TBM(X(9),X(10))
1115 T(206)=2*TBM(X(9),X(11))
1116 T(207)=1*TBM(X(9),X(12))
1117 T(208)=5*TBM(X(9),X(13))
1118 T(209)=2*TBM(X(9),X(14))
1119 T(210)=0*TBM(X(9),X(15))
1120 T(211)=3*TBM(X(9),X(16))
1121 T(212)=0*TBM(X(9),X(17))
1122 T(213)=2*TBM(X(9),X(18))
1123 T(214)=0*TBM(X(9),X(19))
1124 T(215)=0*TBM(X(9),X(20))
1125 T(216)=4*TBM(X(9),X(21))
1126 T(217)=0*TBM(X(9),X(22))
1127 T(218)=5*TBM(X(9),X(23))
1128 T(219)=2*TBM(X(9),X(24))
1129 T(220)=0*TBM(X(9),X(25))
1130 T(221)=5*TBM(X(9),X(26))
1131 T(222)=2*TBM(X(9),X(27))
1132 T(223)=2*TBM(X(9),X(28))
1133 T(224)=5*TBM(X(9),X(29))
1134 T(225)=2*TBM(X(9),X(30))
1140 T(226)=5*TBM(X(10),X(11))
1141 T(227)=5*TBM(X(10),X(12))
1142 T(228)=6*TBM(X(10),X(13))
1143 T(229)=0*TBM(X(10),X(14))
1144 T(230)=1*TBM(X(10),X(15))
1145 T(231)=5*TBM(X(10),X(16))
1146 T(232)=5*TBM(X(10),X(17))
1147 T(233)=0*TBM(X(10),X(18))
1148 T(234)=5*TBM(X(10),X(19))
1149 T(235)=2*TBM(X(10),X(20))
1150 T(236)=3*TBM(X(10),X(21))
1151 T(237)=5*TBM(X(10),X(22))
1152 T(238)=0*TBM(X(10),X(23))
1153 T(239)=5*TBM(X(10),X(24))
1154 T(240)=2*TBM(X(10),X(25))
1155 T(241)=10*TBM(X(10),X(26))
1156 T(242)=10*TBM(X(10),X(27))
1157 T(243)=1*TBM(X(10),X(28))
1158 T(244)=5*TBM(X(10),X(29))
1159 T(245)=2*TBM(X(10),X(30))
1165 T(246)=0*TBM(X(11),X(12))
1166 T(247)=0*TBM(X(11),X(13))
1167 T(248)=1*TBM(X(11),X(14))
1168 T(249)=2*TBM(X(11),X(15))
1169 T(250)=1*TBM(X(11),X(16))
1170 T(251)=0*TBM(X(11),X(17))
1171 T(252)=2*TBM(X(11),X(18))
1172 T(253)=0*TBM(X(11),X(19))
1173 T(254)=0*TBM(X(11),X(20))
1174 T(255)=0*TBM(X(11),X(21))
1175 T(256)=6*TBM(X(11),X(22))
1176 T(257)=6*TBM(X(11),X(23))
1177 T(258)=0*TBM(X(11),X(24))
1178 T(259)=4*TBM(X(11),X(25))
1179 T(260)=5*TBM(X(11),X(26))
1180 T(261)=3*TBM(X(11),X(27))
1181 T(262)=2*TBM(X(11),X(28))
1182 T(263)=2*TBM(X(11),X(29))
1183 T(264)=10*TBM(X(11),X(30))
1189 T(265)=5*TBM(X(12),X(13))
1190 T(266)=5*TBM(X(12),X(14))
1191 T(267)=2*TBM(X(12),X(15))
1192 T(268)=0*TBM(X(12),X(16))
1193 T(269)=0*TBM(X(12),X(17))
1194 T(270)=0*TBM(X(12),X(18))
1195 T(271)=0*TBM(X(12),X(19))
1196 T(272)=2*TBM(X(12),X(20))
1197 T(273)=0*TBM(X(12),X(21))
1198 T(274)=4*TBM(X(12),X(22))
1199 T(275)=5*TBM(X(12),X(23))
1200 T(276)=10*TBM(X(12),X(24))
1201 T(277)=1*TBM(X(12),X(25))
1202 T(278)=0*TBM(X(12),X(26))
1203 T(279)=0*TBM(X(12),X(27))
1204 T(280)=0*TBM(X(12),X(28))
1205 T(281)=0*TBM(X(12),X(29))
1206 T(282)=1*TBM(X(12),X(30))
1282 T(283)=2*TBM(X(13),X(14))
1283 T(284)=0*TBM(X(13),X(15))
1284 T(285)=4*TBM(X(13),X(16))
1285 T(286)=2*TBM(X(13),X(17))
1286 T(287)=2*TBM(X(13),X(18))
1287 T(288)=1*TBM(X(13),X(19))
1288 T(289)=0*TBM(X(13),X(20))
1289 T(290)=6*TBM(X(13),X(21))
1290 T(291)=2*TBM(X(13),X(22))
1291 T(292)=1*TBM(X(13),X(23))
1292 T(293)=5*TBM(X(13),X(24))
1293 T(294)=5*TBM(X(13),X(25))
1294 T(295)=0*TBM(X(13),X(26))
1295 T(296)=0*TBM(X(13),X(27))
1296 T(297)=1*TBM(X(13),X(28))
1297 T(298)=5*TBM(X(13),X(29))
1298 T(299)=5*TBM(X(13),X(30))
1384 T(300)=2*TBM(X(14),X(15))
1385 T(301)=1*TBM(X(14),X(16))
1386 T(302)=0*TBM(X(14),X(17))
1387 T(303)=5*TBM(X(14),X(18))
1388 T(304)=3*TBM(X(14),X(19))
1389 T(305)=10*TBM(X(14),X(20))
1390 T(306)=0*TBM(X(14),X(21))
1391 T(307)=0*TBM(X(14),X(22))
1392 T(308)=4*TBM(X(14),X(23))
1393 T(309)=2*TBM(X(14),X(24))
1394 T(310)=0*TBM(X(14),X(25))
1395 T(311)=0*TBM(X(14),X(26))
1396 T(312)=4*TBM(X(14),X(27))
1397 T(313)=2*TBM(X(14),X(28))
1398 T(314)=5*TBM(X(14),X(29))
1399 T(315)=5*TBM(X(14),X(30))
1411 T(316)=4*TBM(X(15),X(16))
1412 T(317)=5*TBM(X(15),X(17))
1413 T(318)=1*TBM(X(15),X(18))
1414 T(319)=0*TBM(X(15),X(19))
1415 T(320)=1*TBM(X(15),X(20))
1416 T(321)=0*TBM(X(15),X(21))
1417 T(322)=5*TBM(X(15),X(22))
1418 T(323)=0*TBM(X(15),X(23))
1419 T(324)=2*TBM(X(15),X(24))
1420 T(325)=0*TBM(X(15),X(25))
1421 T(326)=0*TBM(X(15),X(26))
1422 T(327)=5*TBM(X(15),X(27))
1423 T(328)=1*TBM(X(15),X(28))
1424 T(329)=1*TBM(X(15),X(29))
1425 T(330)=0*TBM(X(15),X(30))
1435 T(331)=0*TBM(X(16),X(17))
1436 T(332)=3*TBM(X(16),X(18))
1437 T(333)=0*TBM(X(16),X(19))
1438 T(334)=2*TBM(X(16),X(20))
1439 T(335)=2*TBM(X(16),X(21))
1440 T(336)=0*TBM(X(16),X(22))
1441 T(337)=2*TBM(X(16),X(23))
1442 T(338)=0*TBM(X(16),X(24))
1443 T(339)=5*TBM(X(16),X(25))
1444 T(340)=0*TBM(X(16),X(26))
1445 T(341)=5*TBM(X(16),X(27))
1446 T(342)=2*TBM(X(16),X(28))
1447 T(343)=5*TBM(X(16),X(29))
1448 T(344)=10*TBM(X(16),X(30))
1458 T(345)=2*TBM(X(17),X(18))
1459 T(346)=2*TBM(X(17),X(19))
1460 T(347)=0*TBM(X(17),X(20))
1461 T(348)=0*TBM(X(17),X(21))
1462 T(349)=0*TBM(X(17),X(22))
1463 T(350)=6*TBM(X(17),X(23))
1464 T(351)=5*TBM(X(17),X(24))
1465 T(352)=3*TBM(X(17),X(25))
1466 T(353)=5*TBM(X(17),X(26))
1467 T(354)=0*TBM(X(17),X(27))
1468 T(355)=0*TBM(X(17),X(28))
1469 T(356)=5*TBM(X(17),X(29))
1470 T(357)=1*TBM(X(17),X(30))
1480 T(358)=5*TBM(X(18),X(19))
1481 T(359)=1*TBM(X(18),X(20))
1482 T(360)=2*TBM(X(18),X(21))
1483 T(361)=10*TBM(X(18),X(22))
1484 T(362)=10*TBM(X(18),X(23))
1485 T(363)=4*TBM(X(18),X(24))
1486 T(364)=0*TBM(X(18),X(25))
1487 T(365)=0*TBM(X(18),X(26))
1488 T(366)=5*TBM(X(18),X(27))
1489 T(367)=0*TBM(X(18),X(28))
1490 T(368)=0*TBM(X(18),X(29))
1491 T(369)=0*TBM(X(18),X(30))
1501 T(370)=0*TBM(X(19),X(20))
1502 T(371)=5*TBM(X(19),X(21))
1503 T(372)=5*TBM(X(19),X(22))
1504 T(373)=1*TBM(X(19),X(23))
1505 T(374)=0*TBM(X(19),X(24))
1506 T(375)=5*TBM(X(19),X(25))
1507 T(376)=2*TBM(X(19),X(26))
1508 T(377)=1*TBM(X(19),X(27))
1509 T(378)=2*TBM(X(19),X(28))
1510 T(379)=10*TBM(X(19),X(29))
1511 T(380)=10*TBM(X(19),X(30))
1513 T(381)=5*TBM(X(20),X(21))
1514 T(382)=2*TBM(X(20),X(22))
1515 T(383)=1*TBM(X(20),X(23))
1516 T(384)=3*TBM(X(20),X(24))
1517 T(385)=1*TBM(X(20),X(25))
1518 T(386)=5*TBM(X(20),X(26))
1519 T(387)=6*TBM(X(20),X(27))
1520 T(388)=5*TBM(X(20),X(28))
1521 T(389)=5*TBM(X(20),X(29))
1522 T(390)=3*TBM(X(20),X(30))
1524 T(391)=4*TBM(X(21),X(22))
1525 T(392)=0*TBM(X(21),X(23))
1526 T(393)=1*TBM(X(21),X(24))
1527 T(394)=0*TBM(X(21),X(25))
1528 T(395)=0*TBM(X(21),X(26))
1529 T(396)=0*TBM(X(21),X(27))
1530 T(397)=5*TBM(X(21),X(28))
1531 T(398)=0*TBM(X(21),X(29))
1532 T(399)=0*TBM(X(21),X(30))
1534 T(400)=5*TBM(X(22),X(23))
1535 T(401)=0*TBM(X(22),X(24))
1536 T(402)=4*TBM(X(22),X(25))
1537 T(403)=4*TBM(X(22),X(26))
1538 T(404)=5*TBM(X(22),X(27))
1539 T(405)=0*TBM(X(22),X(28))
1540 T(406)=2*TBM(X(22),X(29))
1541 T(407)=5*TBM(X(22),X(30))
1543 T(408)=0*TBM(X(23),X(24))
1544 T(409)=4*TBM(X(23),X(25))
1545 T(410)=4*TBM(X(23),X(26))
1546 T(411)=1*TBM(X(23),X(27))
1547 T(412)=0*TBM(X(23),X(28))
1548 T(413)=2*TBM(X(23),X(29))
1549 T(414)=2*TBM(X(23),X(30))
1551 T(415)=5*TBM(X(24),X(25))
1552 T(416)=5*TBM(X(24),X(26))
1553 T(417)=0*TBM(X(24),X(27))
1554 T(418)=1*TBM(X(24),X(28))
1555 T(419)=0*TBM(X(24),X(29))
1556 T(420)=0*TBM(X(24),X(30))
1558 T(421)=1*TBM(X(25),X(26))
1559 T(422)=0*TBM(X(25),X(27))
1560 T(423)=10*TBM(X(25),X(28))
1561 T(424)=1*TBM(X(25),X(29))
1562 T(425)=0*TBM(X(25),X(30))
1564 T(426)=0*TBM(X(26),X(27))
1565 T(427)=0*TBM(X(26),X(28))
1566 T(428)=0*TBM(X(26),X(29))
1567 T(429)=0*TBM(X(26),X(30))
1570 T(430)=0*TBM(X(27),X(28))
1571 T(431)=0*TBM(X(27),X(29))
1572 T(432)=10*TBM(X(27),X(30))
1573 T(433)=2*TBM(X(28),X(29))
1574 T(434)=2*TBM(X(28),X(30))
1577 T(435)=2*TBM(X(29),X(30))
1651 P1NEW=0
1652 FOR KAU7=1 TO 435
1653 P1NEW=P1NEW+T(KAU7)
1654 NEXT KAU7
1655 P=-P1NEW
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 30
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 228
1670 NEXT I
1890 IF M>-3066 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1927 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 8.3 hours of running is presented below. What immediately follows is a manual copy from the computer screen.

17 2 27 19 6
4 15 16 9 10
22 5 3 26 30
21 18 29 14 25
1 23 24 11 13
12 28 7 8 20
-3062 -29395

17 2 27 26 6
4 15 16 9 10
22 5 3 25 30
21 18 29 14 19
1 23 24 11 13
12 28 7 8 20
-3065 -28145

17 2 27 19 6
4 15 16 9 10
22 5 3 26 30
21 18 29 14 25
1 23 24 11 13
12 28 7 8 20
-3062 -27947

3062 is optimal, Loiola et al. (2007, p. 668). Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-27947 was produced during the first 8.3 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).

Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).

Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).

Loiola, E. M., N. M. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido, "A Survey for the Quadratic Assignment Problem," European Journal of Operational Research 176, 657-690 (2007).

Nugent,C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1966).

Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly 18, 1-36 (1971).

A Computer Program for Solving Integer Programs

Jsun Yui Wong

The computer program listed below seeks to solve the 30-department problem in Nugent, Vollmann, and Ruml (1968).

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(466)
6 DIM TBM(33,33)
51 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=4:TBM(1,6)=5:TBM(1,7)=1:TBM(1,8)=2:TBM(1,9)=3:TBM(1,10)=4
52 TBM(1,11)=5:TBM(1,12)=6:TBM(1,13)=2:TBM(1,14)=3:TBM(1,15)=4:TBM(1,16)=5:TBM(1,17)=6:TBM(1,18)=7:TBM(1,19)=3:TBM(1,20)=4
53 TBM(1,21)=5:TBM(1,22)=6:TBM(1,23)=7:TBM(1,24)=8:TBM(1,25)=4:TBM(1,26)=5:TBM(1,27)=6:TBM(1,28)=7:TBM(1,29)=8:TBM(1,30)=9
63 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=3:TBM(2,6)=4:TBM(2,7)=2:TBM(2,8)=1:TBM(2,9)=2:TBM(2,10)=3
64 TBM(2,11)=4:TBM(2,12)=5:TBM(2,13)=3:TBM(2,14)=2:TBM(2,15)=3:TBM(2,16)=4:TBM(2,17)=5:TBM(2,18)=6:TBM(2,19)=4:TBM(2,20)=3
65 TBM(2,21)=4:TBM(2,22)=5:TBM(2,23)=6:TBM(2,24)=7:TBM(2,25)=5:TBM(2,26)=4:TBM(2,27)=5:TBM(2,28)=6:TBM(2,29)=7:TBM(2,30)=8
67 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=3:TBM(3,7)=3:TBM(3,8)=2:TBM(3,9)=1:TBM(3,10)=2
68 TBM(3,11)=3:TBM(3,12)=4:TBM(3,13)=4:TBM(3,14)=3:TBM(3,15)=2:TBM(3,16)=3:TBM(3,17)=4:TBM(3,18)=5:TBM(3,19)=5:TBM(3,20)=4
69 TBM(3,21)=3:TBM(3,22)=4:TBM(3,23)=5:TBM(3,24)=6:TBM(3,25)=6:TBM(3,26)=5:TBM(3,27)=4:TBM(3,28)=5:TBM(3,29)=6:TBM(3,30)=7
77 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=1:TBM(4,6)=2:TBM(4,7)=4:TBM(4,8)=3:TBM(4,9)=2:TBM(4,10)=1
78 TBM(4,11)=2:TBM(4,12)=3:TBM(4,13)=5:TBM(4,14)=4:TBM(4,15)=3:TBM(4,16)=2:TBM(4,17)=3:TBM(4,18)=4:TBM(4,19)=6:TBM(4,20)=5
79 TBM(4,21)=4:TBM(4,22)=3:TBM(4,23)=4:TBM(4,24)=5:TBM(4,25)=7:TBM(4,26)=6:TBM(4,27)=5:TBM(4,28)=4:TBM(4,29)=5:TBM(4,30)=6
81 TBM(5,1)=4:TBM(5,2)=3:TBM(5,3)=2:TBM(5,4)=1:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=5:TBM(5,8)=4:TBM(5,9)=3:TBM(5,10)=2
82 TBM(5,11)=1:TBM(5,12)=2:TBM(5,13)=6:TBM(5,14)=5:TBM(5,15)=4:TBM(5,16)=3:TBM(5,17)=2:TBM(5,18)=3:TBM(5,19)=7:TBM(5,20)=6
83 TBM(5,21)=5:TBM(5,22)=4:TBM(5,23)=3:TBM(5,24)=4:TBM(5,25)=8:TBM(5,26)=7:TBM(5,27)=6:TBM(5,28)=5:TBM(5,29)=4:TBM(5,30)=5
93 TBM(6,1)=5:TBM(6,2)=4:TBM(6,3)=3:TBM(6,4)=2:TBM(6,5)=1:TBM(6,6)=999:TBM(6,7)=6:TBM(6,8)=5:TBM(6,9)=4:TBM(6,10)=3
94 TBM(6,11)=2:TBM(6,12)=1:TBM(6,13)=7:TBM(6,14)=6:TBM(6,15)=5:TBM(6,16)=4:TBM(6,17)=3:TBM(6,18)=2:TBM(6,19)=8:TBM(6,20)=7
95 TBM(6,21)=6:TBM(6,22)=5:TBM(6,23)=4:TBM(6,24)=3:TBM(6,25)=9:TBM(6,26)=8:TBM(6,27)=7:TBM(6,28)=6:TBM(6,29)=5:TBM(6,30)=4
97 TBM(7,1)=1:TBM(7,2)=2:TBM(7,3)=3:TBM(7,4)=4:TBM(7,5)=5:TBM(7,6)=6:TBM(7,7)=999:TBM(7,8)=1:TBM(7,9)=2:TBM(7,10)=3
98 TBM(7,11)=4:TBM(7,12)=5:TBM(7,13)=1:TBM(7,14)=2:TBM(7,15)=3:TBM(7,16)=4:TBM(7,17)=5:TBM(7,18)=6:TBM(7,19)=2:TBM(7,20)=3
99 TBM(7,21)=4:TBM(7,22)=5:TBM(7,23)=6:TBM(7,24)=7:TBM(7,25)=3:TBM(7,26)=4:TBM(7,27)=5:TBM(7,28)=6:TBM(7,29)=7:TBM(7,30)=8
101 TBM(8,1)=2:TBM(8,2)=1:TBM(8,3)=2:TBM(8,4)=3:TBM(8,5)=4:TBM(8,6)=5:TBM(8,7)=1:TBM(8,8)=999:TBM(8,9)=1:TBM(8,10)=2
102 TBM(8,11)=3:TBM(8,12)=4:TBM(8,13)=2:TBM(8,14)=1:TBM(8,15)=2:TBM(8,16)=3:TBM(8,17)=4:TBM(8,18)=5:TBM(8,19)=3:TBM(8,20)=2
103 TBM(8,21)=3:TBM(8,22)=4:TBM(8,23)=5:TBM(8,24)=6:TBM(8,25)=4:TBM(8,26)=3:TBM(8,27)=4:TBM(8,28)=5:TBM(8,29)=6:TBM(8,30)=7
105 TBM(9,1)=3:TBM(9,2)=2:TBM(9,3)=1:TBM(9,4)=2:TBM(9,5)=3:TBM(9,6)=4:TBM(9,7)=2:TBM(9,8)=1:TBM(9,9)=999:TBM(9,10)=1
106 TBM(9,11)=2:TBM(9,12)=3:TBM(9,13)=3:TBM(9,14)=2:TBM(9,15)=1:TBM(9,16)=2:TBM(9,17)=3:TBM(9,18)=4:TBM(9,19)=4:TBM(9,20)=3
107 TBM(9,21)=2:TBM(9,22)=3:TBM(9,23)=4:TBM(9,24)=5:TBM(9,25)=5:TBM(9,26)=4:TBM(9,27)=3:TBM(9,28)=4:TBM(9,29)=5:TBM(9,30)=6
109 TBM(10,1)=4:TBM(10,2)=3:TBM(10,3)=2:TBM(10,4)=1:TBM(10,5)=2:TBM(10,6)=3:TBM(10,7)=3:TBM(10,8)=2:TBM(10,9)=1:TBM(10,10)=999
110 TBM(10,11)=1:TBM(10,12)=2:TBM(10,13)=4:TBM(10,14)=3:TBM(10,15)=2:TBM(10,16)=1:TBM(10,17)=2:TBM(10,18)=3:TBM(10,19)=5:TBM(10,20)=4
111 TBM(10,21)=3:TBM(10,22)=2:TBM(10,23)=3:TBM(10,24)=4:TBM(10,25)=6:TBM(10,26)=5:TBM(10,27)=4:TBM(10,28)=3:TBM(10,29)=4:TBM(10,30)=5
113 TBM(11,1)=5:TBM(11,2)=4:TBM(11,3)=3:TBM(11,4)=2:TBM(11,5)=1:TBM(11,6)=2:TBM(11,7)=4:TBM(11,8)=3:TBM(11,9)=2:TBM(11,10)=1
114 TBM(11,11)=999:TBM(11,12)=1:TBM(11,13)=5:TBM(11,14)=4:TBM(11,15)=3:TBM(11,16)=2:TBM(11,17)=1:TBM(11,18)=2:TBM(11,19)=6:TBM(11,20)=5
115 TBM(11,21)=4:TBM(11,22)=3:TBM(11,23)=2:TBM(11,24)=3:TBM(11,25)=7:TBM(11,26)=6:TBM(11,27)=5:TBM(11,28)=4:TBM(11,29)=3:TBM(11,30)=4
117 TBM(12,1)=6:TBM(12,2)=5:TBM(12,3)=4:TBM(12,4)=3:TBM(12,5)=2:TBM(12,6)=1:TBM(12,7)=5:TBM(12,8)=4:TBM(12,9)=3:TBM(12,10)=2
118 TBM(12,11)=1:TBM(12,12)=999:TBM(12,13)=6:TBM(12,14)=5:TBM(12,15)=4:TBM(12,16)=3:TBM(12,17)=2:TBM(12,18)=1:TBM(12,19)=7:TBM(12,20)=6
119 TBM(12,21)=5:TBM(12,22)=4:TBM(12,23)=3:TBM(12,24)=2:TBM(12,25)=8:TBM(12,26)=7:TBM(12,27)=6:TBM(12,28)=5:TBM(12,29)=4:TBM(12,30)=3
121 TBM(13,1)=2:TBM(13,2)=3:TBM(13,3)=4:TBM(13,4)=5:TBM(13,5)=6:TBM(13,6)=7:TBM(13,7)=1:TBM(13,8)=2:TBM(13,9)=3:TBM(13,10)=4
122 TBM(13,11)=5:TBM(13,12)=6:TBM(13,13)=999:TBM(13,14)=1:TBM(13,15)=2:TBM(13,16)=3:TBM(13,17)=4:TBM(13,18)=5:TBM(13,19)=1:TBM(13,20)=2
123 TBM(13,21)=3:TBM(13,22)=4:TBM(13,23)=5:TBM(13,24)=6:TBM(13,25)=2:TBM(13,26)=3:TBM(13,27)=4:TBM(13,28)=5:TBM(13,29)=6:TBM(13,30)=7
125 TBM(14,1)=3:TBM(14,2)=2:TBM(14,3)=3:TBM(14,4)=4:TBM(14,5)=5:TBM(14,6)=6:TBM(14,7)=2:TBM(14,8)=1:TBM(14,9)=2:TBM(14,10)=3
126 TBM(14,11)=4:TBM(14,12)=5:TBM(14,13)=1:TBM(14,14)=999:TBM(14,15)=1:TBM(14,16)=2:TBM(14,17)=3:TBM(14,18)=4:TBM(14,19)=2:TBM(14,20)=1
127 TBM(14,21)=2:TBM(14,22)=3:TBM(14,23)=4:TBM(14,24)=5:TBM(14,25)=3:TBM(14,26)=2:TBM(14,27)=3:TBM(14,28)=4:TBM(14,29)=5:TBM(14,30)=6
135 TBM(15,1)=4:TBM(15,2)=3:TBM(15,3)=2:TBM(15,4)=3:TBM(15,5)=4:TBM(15,6)=5:TBM(15,7)=3:TBM(15,8)=2:TBM(15,9)=1:TBM(15,10)=2
136 TBM(15,11)=3:TBM(15,12)=4:TBM(15,13)=2:TBM(15,14)=1:TBM(15,15)=999:TBM(15,16)=1:TBM(15,17)=2:TBM(15,18)=3:TBM(15,19)=3:TBM(15,20)=2
137 TBM(15,21)=1:TBM(15,22)=2:TBM(15,23)=3:TBM(15,24)=4:TBM(15,25)=4:TBM(15,26)=3:TBM(15,27)=2:TBM(15,28)=3:TBM(15,29)=4:TBM(15,30)=5
139 TBM(16,1)=5:TBM(16,2)=4:TBM(16,3)=3:TBM(16,4)=2:TBM(16,5)=3:TBM(16,6)=4:TBM(16,7)=4:TBM(16,8)=3:TBM(16,9)=2:TBM(16,10)=1
140 TBM(16,11)=2:TBM(16,12)=3:TBM(16,13)=3:TBM(16,14)=2:TBM(16,15)=1:TBM(16,16)=999:TBM(16,17)=1:TBM(16,18)=2:TBM(16,19)=4:TBM(16,20)=3
141 TBM(16,21)=2:TBM(16,22)=1:TBM(16,23)=2:TBM(16,24)=3:TBM(16,25)=5:TBM(16,26)=4:TBM(16,27)=3:TBM(16,28)=2:TBM(16,29)=3:TBM(16,30)=4
143 TBM(17,1)=6:TBM(17,2)=5:TBM(17,3)=4:TBM(17,4)=3:TBM(17,5)=2:TBM(17,6)=3:TBM(17,7)=5:TBM(17,8)=4:TBM(17,9)=3:TBM(17,10)=2
144 TBM(17,11)=1:TBM(17,12)=2:TBM(17,13)=4:TBM(17,14)=3:TBM(17,15)=2:TBM(17,16)=1:TBM(17,17)=999:TBM(17,18)=1:TBM(17,19)=5:TBM(17,20)=4
145 TBM(17,21)=3:TBM(17,22)=2:TBM(17,23)=1:TBM(17,24)=2:TBM(17,25)=6:TBM(17,26)=5:TBM(17,27)=4:TBM(17,28)=3:TBM(17,29)=2:TBM(17,30)=3
147 TBM(18,1)=7:TBM(18,2)=6:TBM(18,3)=5:TBM(18,4)=4:TBM(18,5)=3:TBM(18,6)=2:TBM(18,7)=6:TBM(18,8)=5:TBM(18,9)=4:TBM(18,10)=3
148 TBM(18,11)=2:TBM(18,12)=1:TBM(18,13)=5:TBM(18,14)=4:TBM(18,15)=3:TBM(18,16)=2:TBM(18,17)=1:TBM(18,18)=999:TBM(18,19)=6:TBM(18,20)=5
149 TBM(18,21)=4:TBM(18,22)=3:TBM(18,23)=2:TBM(18,24)=1:TBM(18,25)=7:TBM(18,26)=6:TBM(18,27)=5:TBM(18,28)=4:TBM(18,29)=3:TBM(18,30)=2
151 TBM(19,1)=3:TBM(19,2)=4:TBM(19,3)=5:TBM(19,4)=6:TBM(19,5)=7:TBM(19,6)=8:TBM(19,7)=2:TBM(19,8)=3:TBM(19,9)=4:TBM(19,10)=5
152 TBM(19,11)=6:TBM(19,12)=7:TBM(19,13)=1:TBM(19,14)=2:TBM(19,15)=3:TBM(19,16)=4:TBM(19,17)=5:TBM(19,18)=6:TBM(19,19)=999:TBM(19,20)=1
153 TBM(19,21)=2:TBM(19,22)=3:TBM(19,23)=4:TBM(19,24)=5:TBM(19,25)=1:TBM(19,26)=2:TBM(19,27)=3:TBM(19,28)=4:TBM(19,29)=5:TBM(19,30)=6
155 TBM(20,1)=4:TBM(20,2)=3:TBM(20,3)=4:TBM(20,4)=5:TBM(20,5)=6:TBM(20,6)=7:TBM(20,7)=3:TBM(20,8)=2:TBM(20,9)=3:TBM(20,10)=4
156 TBM(20,11)=5:TBM(20,12)=6:TBM(20,13)=2:TBM(20,14)=1:TBM(20,15)=2:TBM(20,16)=3:TBM(20,17)=4:TBM(20,18)=5:TBM(20,19)=1:TBM(20,20)=999
157 TBM(20,21)=1:TBM(20,22)=2:TBM(20,23)=3:TBM(20,24)=4:TBM(20,25)=2:TBM(20,26)=1:TBM(20,27)=2:TBM(20,28)=3:TBM(20,29)=4:TBM(20,30)=5
161 TBM(21,1)=5:TBM(21,2)=4:TBM(21,3)=3:TBM(21,4)=4:TBM(21,5)=5:TBM(21,6)=6:TBM(21,7)=4:TBM(21,8)=3:TBM(21,9)=2:TBM(21,10)=3
162 TBM(21,11)=4:TBM(21,12)=5:TBM(21,13)=3:TBM(21,14)=2:TBM(21,15)=1:TBM(21,16)=2:TBM(21,17)=3:TBM(21,18)=4:TBM(21,19)=2:TBM(21,20)=1
163 TBM(21,21)=999:TBM(21,22)=1:TBM(21,23)=2:TBM(21,24)=3:TBM(21,25)=3:TBM(21,26)=2:TBM(21,27)=1:TBM(21,28)=2:TBM(21,29)=3:TBM(21,30)=4
165 TBM(22,1)=6:TBM(22,2)=5:TBM(22,3)=4:TBM(22,4)=3:TBM(22,5)=4:TBM(22,6)=5:TBM(22,7)=5:TBM(22,8)=4:TBM(22,9)=3:TBM(22,10)=2
166 TBM(22,11)=3:TBM(22,12)=4:TBM(22,13)=4:TBM(22,14)=3:TBM(22,15)=2:TBM(22,16)=1:TBM(22,17)=2:TBM(22,18)=3:TBM(22,19)=3:TBM(22,20)=2
167 TBM(22,21)=1:TBM(22,22)=999:TBM(22,23)=1:TBM(22,24)=2:TBM(22,25)=4:TBM(22,26)=3:TBM(22,27)=2:TBM(22,28)=1:TBM(22,29)=2:TBM(22,30)=3
169 TBM(23,1)=7:TBM(23,2)=6:TBM(23,3)=5:TBM(23,4)=4:TBM(23,5)=3:TBM(23,6)=4:TBM(23,7)=6:TBM(23,8)=5:TBM(23,9)=4:TBM(23,10)=3
170 TBM(23,11)=2:TBM(23,12)=3:TBM(23,13)=5:TBM(23,14)=4:TBM(23,15)=3:TBM(23,16)=2:TBM(23,17)=1:TBM(23,18)=2:TBM(23,19)=4:TBM(23,20)=3
171 TBM(23,21)=2:TBM(23,22)=1:TBM(23,23)=999:TBM(23,24)=1:TBM(23,25)=5:TBM(23,26)=4:TBM(23,27)=3:TBM(23,28)=2:TBM(23,29)=1:TBM(23,30)=2
173 TBM(24,1)=8:TBM(24,2)=7:TBM(24,3)=6:TBM(24,4)=5:TBM(24,5)=4:TBM(24,6)=3:TBM(24,7)=7:TBM(24,8)=6:TBM(24,9)=5:TBM(24,10)=4
174 TBM(24,11)=3:TBM(24,12)=2:TBM(24,13)=6:TBM(24,14)=5:TBM(24,15)=4:TBM(24,16)=3:TBM(24,17)=2:TBM(24,18)=1:TBM(24,19)=5:TBM(24,20)=4
175 TBM(24,21)=3:TBM(24,22)=2:TBM(24,23)=1:TBM(24,24)=999:TBM(24,25)=6:TBM(24,26)=5:TBM(24,27)=4:TBM(24,28)=3:TBM(24,29)=2:TBM(24,30)=1
177 TBM(25,1)=4:TBM(25,2)=5:TBM(25,3)=6:TBM(25,4)=7:TBM(25,5)=8:TBM(25,6)=9:TBM(25,7)=3:TBM(25,8)=4:TBM(25,9)=5:TBM(25,10)=6
178 TBM(25,11)=7:TBM(25,12)=8:TBM(25,13)=2:TBM(25,14)=3:TBM(25,15)=4:TBM(25,16)=5:TBM(25,17)=6:TBM(25,18)=7:TBM(25,19)=1:TBM(25,20)=2
179 TBM(25,21)=3:TBM(25,22)=4:TBM(25,23)=5:TBM(25,24)=6:TBM(25,25)=999:TBM(25,26)=1:TBM(25,27)=2:TBM(25,28)=3:TBM(25,29)=4:TBM(25,30)=5
181 TBM(26,1)=5:TBM(26,2)=4:TBM(26,3)=5:TBM(26,4)=6:TBM(26,5)=7:TBM(26,6)=8:TBM(26,7)=4:TBM(26,8)=3:TBM(26,9)=4:TBM(26,10)=5
182 TBM(26,11)=6:TBM(26,12)=7:TBM(26,13)=3:TBM(26,14)=2:TBM(26,15)=3:TBM(26,16)=4:TBM(26,17)=5:TBM(26,18)=6:TBM(26,19)=2:TBM(26,20)=1
183 TBM(26,21)=2:TBM(26,22)=3:TBM(26,23)=4:TBM(26,24)=5:TBM(26,25)=1:TBM(26,26)=999:TBM(26,27)=1:TBM(26,28)=2:TBM(26,29)=3:TBM(26,30)=4
185 TBM(27,1)=6:TBM(27,2)=5:TBM(27,3)=4:TBM(27,4)=5:TBM(27,5)=6:TBM(27,6)=7:TBM(27,7)=5:TBM(27,8)=4:TBM(27,9)=3:TBM(27,10)=4
186 TBM(27,11)=5:TBM(27,12)=6:TBM(27,13)=4:TBM(27,14)=3:TBM(27,15)=2:TBM(27,16)=3:TBM(27,17)=4:TBM(27,18)=5:TBM(27,19)=3:TBM(27,20)=2
187 TBM(27,21)=1:TBM(27,22)=2:TBM(27,23)=3:TBM(27,24)=4:TBM(27,25)=2:TBM(27,26)=1:TBM(27,27)=999:TBM(27,28)=1:TBM(27,29)=2:TBM(27,30)=3
189 TBM(28,1)=7:TBM(28,2)=6:TBM(28,3)=5:TBM(28,4)=4:TBM(28,5)=5:TBM(28,6)=6:TBM(28,7)=6:TBM(28,8)=5:TBM(28,9)=4:TBM(28,10)=3
190 TBM(28,11)=4:TBM(28,12)=5:TBM(28,13)=5:TBM(28,14)=4:TBM(28,15)=3:TBM(28,16)=2:TBM(28,17)=3:TBM(28,18)=4:TBM(28,19)=4:TBM(28,20)=3
191 TBM(28,21)=2:TBM(28,22)=1:TBM(28,23)=2:TBM(28,24)=3:TBM(28,25)=3:TBM(28,26)=2:TBM(28,27)=1:TBM(28,28)=999:TBM(28,29)=1:TBM(28,30)=2
193 TBM(29,1)=8:TBM(29,2)=7:TBM(29,3)=6:TBM(29,4)=5:TBM(29,5)=4:TBM(29,6)=5:TBM(29,7)=7:TBM(29,8)=6:TBM(29,9)=5:TBM(29,10)=4
194 TBM(29,11)=3:TBM(29,12)=4:TBM(29,13)=6:TBM(29,14)=5:TBM(29,15)=4:TBM(29,16)=3:TBM(29,17)=2:TBM(29,18)=3:TBM(29,19)=5:TBM(29,20)=4
195 TBM(29,21)=3:TBM(29,22)=2:TBM(29,23)=1:TBM(29,24)=2:TBM(29,25)=4:TBM(29,26)=3:TBM(29,27)=2:TBM(29,28)=1:TBM(29,29)=999:TBM(29,30)=1
197 TBM(30,1)=9:TBM(30,2)=8:TBM(30,3)=7:TBM(30,4)=6:TBM(30,5)=5:TBM(30,6)=4:TBM(30,7)=8:TBM(30,8)=7:TBM(30,9)=6:TBM(30,10)=5
198 TBM(30,11)=4:TBM(30,12)=3:TBM(30,13)=7:TBM(30,14)=6:TBM(30,15)=5:TBM(30,16)=4:TBM(30,17)=3:TBM(30,18)=2:TBM(30,19)=6:TBM(30,20)=5
199 TBM(30,21)=4:TBM(30,22)=3:TBM(30,23)=2:TBM(30,24)=1:TBM(30,25)=5:TBM(30,26)=4:TBM(30,27)=3:TBM(30,28)=2:TBM(30,29)=1:TBM(30,30)=999
220 FOR JJJJ=-32000 TO 32000
221 RANDOMIZE JJJJ
222 M=-1D+17
223 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
224 A(11)=11:A(12)=12:A(13)=13:A(14)=14:A(15)=15:A(16)=16:A(17)=17:A(18)=18:A(19)=19:A(20)=20
225 A(21)=21:A(22)=22:A(23)=23:A(24)=24:A(25)=25:A(26)=26:A(27)=27:A(28)=28:A(29)=29:A(30)=30
226 IMAR=10+FIX(RND*5000)
228 FOR I=1 TO IMAR
229 FOR KK=1 TO 30
231 X(KK)=A(KK)
232 NEXT KK
330 IJM=1+FIX(RND*30)
331 IJN=1+FIX(RND*30)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=3*TBM(X(1),X(2))
402 T(2)=2*TBM(X(1),X(3))
403 T(3)=0*TBM(X(1),X(4))
404 T(4)=0*TBM(X(1),X(5))
405 T(5)=2*TBM(X(1),X(6))
406 T(6)=10*TBM(X(1),X(7))
407 T(7)=5*TBM(X(1),X(8))
408 T(8)=0*TBM(X(1),X(9))
409 T(9)=5*TBM(X(1),X(10))
410 T(10)=2*TBM(X(1),X(11))
411 T(11)=5*TBM(X(1),X(12))
412 T(12)=0*TBM(X(1),X(13))
413 T(13)=0*TBM(X(1),X(14))
414 T(14)=2*TBM(X(1),X(15))
415 T(15)=0*TBM(X(1),X(16))
416 T(16)=5*TBM(X(1),X(17))
417 T(17)=6*TBM(X(1),X(18))
418 T(18)=3*TBM(X(1),X(19))
419 T(19)=0*TBM(X(1),X(20))
420 T(20)=1*TBM(X(1),X(21))
421 T(21)=10*TBM(X(1),X(22))
422 T(22)=0*TBM(X(1),X(23))
423 T(23)=10*TBM(X(1),X(24))
424 T(24)=2*TBM(X(1),X(25))
425 T(25)=1*TBM(X(1),X(26))
426 T(26)=1*TBM(X(1),X(27))
427 T(27)=1*TBM(X(1),X(28))
428 T(28)=0*TBM(X(1),X(29))
429 T(29)=1*TBM(X(1),X(30))
615 T(30)=4*TBM(X(2),X(3))
616 T(31)=0*TBM(X(2),X(4))
617 T(32)=10*TBM(X(2),X(5))
618 T(33)=4*TBM(X(2),X(6))
619 T(34)=0*TBM(X(2),X(7))
620 T(35)=0*TBM(X(2),X(8))
621 T(36)=2*TBM(X(2),X(9))
622 T(37)=2*TBM(X(2),X(10))
623 T(38)=1*TBM(X(2),X(11))
624 T(39)=0*TBM(X(2),X(12))
625 T(40)=5*TBM(X(2),X(13))
626 T(41)=0*TBM(X(2),X(14))
627 T(42)=0*TBM(X(2),X(15))
628 T(43)=0*TBM(X(2),X(16))
629 T(44)=0*TBM(X(2),X(17))
630 T(45)=2*TBM(X(2),X(18))
631 T(46)=0*TBM(X(2),X(19))
632 T(47)=1*TBM(X(2),X(20))
633 T(48)=6*TBM(X(2),X(21))
634 T(49)=1*TBM(X(2),X(22))
635 T(50)=0*TBM(X(2),X(23))
636 T(51)=1*TBM(X(2),X(24))
637 T(52)=2*TBM(X(2),X(25))
638 T(53)=2*TBM(X(2),X(26))
639 T(54)=5*TBM(X(2),X(27))
640 T(55)=1*TBM(X(2),X(28))
641 T(56)=10*TBM(X(2),X(29))
642 T(57)=5*TBM(X(2),X(30))
648 T(58)=3*TBM(X(3),X(4))
649 T(59)=4*TBM(X(3),X(5))
650 T(60)=0*TBM(X(3),X(6))
651 T(61)=5*TBM(X(3),X(7))
652 T(62)=5*TBM(X(3),X(8))
653 T(63)=5*TBM(X(3),X(9))
654 T(64)=1*TBM(X(3),X(10))
655 T(65)=4*TBM(X(3),X(11))
656 T(66)=1*TBM(X(3),X(12))
657 T(67)=0*TBM(X(3),X(13))
658 T(68)=4*TBM(X(3),X(14))
659 T(69)=0*TBM(X(3),X(15))
660 T(70)=4*TBM(X(3),X(16))
661 T(71)=0*TBM(X(3),X(17))
662 T(72)=6*TBM(X(3),X(18))
663 T(73)=3*TBM(X(3),X(19))
664 T(74)=2*TBM(X(3),X(20))
665 T(75)=5*TBM(X(3),X(21))
666 T(76)=5*TBM(X(3),X(22))
667 T(77)=2*TBM(X(3),X(23))
668 T(78)=1*TBM(X(3),X(24))
669 T(79)=0*TBM(X(3),X(25))
670 T(80)=0*TBM(X(3),X(26))
671 T(81)=3*TBM(X(3),X(27))
678 T(82)=1*TBM(X(3),X(28))
679 T(83)=0*TBM(X(3),X(29))
680 T(84)=2*TBM(X(3),X(30))
740 T(85)=0*TBM(X(4),X(5))
741 T(86)=0*TBM(X(4),X(6))
742 T(87)=0*TBM(X(4),X(7))
743 T(88)=2*TBM(X(4),X(8))
744 T(89)=2*TBM(X(4),X(9))
745 T(90)=0*TBM(X(4),X(10))
746 T(91)=6*TBM(X(4),X(11))
747 T(92)=0*TBM(X(4),X(12))
748 T(93)=2*TBM(X(4),X(13))
749 T(94)=5*TBM(X(4),X(14))
750 T(95)=2*TBM(X(4),X(15))
751 T(96)=5*TBM(X(4),X(16))
752 T(97)=1*TBM(X(4),X(17))
753 T(98)=1*TBM(X(4),X(18))
754 T(99)=1*TBM(X(4),X(19))
755 T(100)=1*TBM(X(4),X(20))
756 T(101)=2*TBM(X(4),X(21))
757 T(102)=2*TBM(X(4),X(22))
758 T(103)=4*TBM(X(4),X(23))
759 T(104)=0*TBM(X(4),X(24))
760 T(105)=2*TBM(X(4),X(25))
761 T(106)=0*TBM(X(4),X(26))
762 T(107)=2*TBM(X(4),X(27))
763 T(108)=2*TBM(X(4),X(28))
764 T(109)=5*TBM(X(4),X(29))
765 T(110)=5*TBM(X(4),X(30))
851 T(111)=5*TBM(X(5),X(6))
852 T(112)=2*TBM(X(5),X(7))
853 T(113)=0*TBM(X(5),X(8))
854 T(114)=0*TBM(X(5),X(9))
855 T(115)=0*TBM(X(5),X(10))
856 T(116)=0*TBM(X(5),X(11))
857 T(117)=2*TBM(X(5),X(12))
858 T(118)=0*TBM(X(5),X(13))
859 T(119)=0*TBM(X(5),X(14))
860 T(120)=0*TBM(X(5),X(15))
861 T(121)=0*TBM(X(5),X(16))
862 T(122)=2*TBM(X(5),X(17))
863 T(123)=1*TBM(X(5),X(18))
864 T(124)=0*TBM(X(5),X(19))
865 T(125)=0*TBM(X(5),X(20))
866 T(126)=2*TBM(X(5),X(21))
867 T(127)=0*TBM(X(5),X(22))
868 T(128)=5*TBM(X(5),X(23))
869 T(129)=1*TBM(X(5),X(24))
870 T(130)=0*TBM(X(5),X(25))
871 T(131)=2*TBM(X(5),X(26))
872 T(132)=1*TBM(X(5),X(27))
873 T(133)=0*TBM(X(5),X(28))
874 T(134)=2*TBM(X(5),X(29))
875 T(135)=1*TBM(X(5),X(30))
961 T(136)=1*TBM(X(6),X(7))
962 T(137)=2*TBM(X(6),X(8))
963 T(138)=2*TBM(X(6),X(9))
964 T(139)=1*TBM(X(6),X(10))
965 T(140)=4*TBM(X(6),X(11))
966 T(141)=10*TBM(X(6),X(12))
967 T(142)=10*TBM(X(6),X(13))
968 T(143)=2*TBM(X(6),X(14))
969 T(144)=5*TBM(X(6),X(15))
970 T(145)=5*TBM(X(6),X(16))
971 T(146)=0*TBM(X(6),X(17))
972 T(147)=5*TBM(X(6),X(18))
973 T(148)=0*TBM(X(6),X(19))
974 T(149)=0*TBM(X(6),X(20))
975 T(150)=0*TBM(X(6),X(21))
976 T(151)=10*TBM(X(6),X(22))
977 T(152)=0*TBM(X(6),X(23))
978 T(153)=0*TBM(X(6),X(24))
979 T(154)=0*TBM(X(6),X(25))
980 T(155)=4*TBM(X(6),X(26))
981 T(156)=0*TBM(X(6),X(27))
982 T(157)=10*TBM(X(6),X(28))
983 T(158)=1*TBM(X(6),X(29))
984 T(159)=1*TBM(X(6),X(30))
1047 T(160)=10*TBM(X(7),X(8))
1048 T(161)=10*TBM(X(7),X(9))
1051 T(162)=5*TBM(X(7),X(10))
1052 T(163)=10*TBM(X(7),X(11))
1053 T(164)=10*TBM(X(7),X(12))
1054 T(165)=6*TBM(X(7),X(13))
1055 T(166)=0*TBM(X(7),X(14))
1056 T(167)=0*TBM(X(7),X(15))
1057 T(168)=10*TBM(X(7),X(16))
1058 T(169)=2*TBM(X(7),X(17))
1059 T(170)=1*TBM(X(7),X(18))
1060 T(171)=10*TBM(X(7),X(19))
1061 T(172)=1*TBM(X(7),X(20))
1062 T(173)=5*TBM(X(7),X(21))
1063 T(174)=5*TBM(X(7),X(22))
1064 T(175)=2*TBM(X(7),X(23))
1065 T(176)=3*TBM(X(7),X(24))
1066 T(177)=5*TBM(X(7),X(25))
1067 T(178)=0*TBM(X(7),X(26))
1068 T(179)=2*TBM(X(7),X(27))
1069 T(180)=0*TBM(X(7),X(28))
1070 T(181)=1*TBM(X(7),X(29))
1071 T(182)=3*TBM(X(7),X(30))
1077 T(183)=1*TBM(X(8),X(9))
1078 T(184)=3*TBM(X(8),X(10))
1079 T(185)=5*TBM(X(8),X(11))
1080 T(186)=0*TBM(X(8),X(12))
1081 T(187)=0*TBM(X(8),X(13))
1082 T(188)=0*TBM(X(8),X(14))
1083 T(189)=2*TBM(X(8),X(15))
1084 T(190)=4*TBM(X(8),X(16))
1085 T(191)=5*TBM(X(8),X(17))
1086 T(192)=2*TBM(X(8),X(18))
1087 T(193)=10*TBM(X(8),X(19))
1088 T(194)=6*TBM(X(8),X(20))
1089 T(195)=0*TBM(X(8),X(21))
1090 T(196)=5*TBM(X(8),X(22))
1091 T(197)=5*TBM(X(8),X(23))
1092 T(198)=2*TBM(X(8),X(24))
1093 T(199)=5*TBM(X(8),X(25))
1094 T(200)=0*TBM(X(8),X(26))
1095 T(201)=5*TBM(X(8),X(27))
1096 T(202)=5*TBM(X(8),X(28))
1097 T(203)=0*TBM(X(8),X(29))
1098 T(204)=2*TBM(X(8),X(30))
1114 T(205)=10*TBM(X(9),X(10))
1115 T(206)=2*TBM(X(9),X(11))
1116 T(207)=1*TBM(X(9),X(12))
1117 T(208)=5*TBM(X(9),X(13))
1118 T(209)=2*TBM(X(9),X(14))
1119 T(210)=0*TBM(X(9),X(15))
1120 T(211)=3*TBM(X(9),X(16))
1121 T(212)=0*TBM(X(9),X(17))
1122 T(213)=2*TBM(X(9),X(18))
1123 T(214)=0*TBM(X(9),X(19))
1124 T(215)=0*TBM(X(9),X(20))
1125 T(216)=4*TBM(X(9),X(21))
1126 T(217)=0*TBM(X(9),X(22))
1127 T(218)=5*TBM(X(9),X(23))
1128 T(219)=2*TBM(X(9),X(24))
1129 T(220)=0*TBM(X(9),X(25))
1130 T(221)=5*TBM(X(9),X(26))
1131 T(222)=2*TBM(X(9),X(27))
1132 T(223)=2*TBM(X(9),X(28))
1133 T(224)=5*TBM(X(9),X(29))
1134 T(225)=2*TBM(X(9),X(30))
1140 T(226)=5*TBM(X(10),X(11))
1141 T(227)=5*TBM(X(10),X(12))
1142 T(228)=6*TBM(X(10),X(13))
1143 T(229)=0*TBM(X(10),X(14))
1144 T(230)=1*TBM(X(10),X(15))
1145 T(231)=5*TBM(X(10),X(16))
1146 T(232)=5*TBM(X(10),X(17))
1147 T(233)=0*TBM(X(10),X(18))
1148 T(234)=5*TBM(X(10),X(19))
1149 T(235)=2*TBM(X(10),X(20))
1150 T(236)=3*TBM(X(10),X(21))
1151 T(237)=5*TBM(X(10),X(22))
1152 T(238)=0*TBM(X(10),X(23))
1153 T(239)=5*TBM(X(10),X(24))
1154 T(240)=2*TBM(X(10),X(25))
1155 T(241)=10*TBM(X(10),X(26))
1156 T(242)=10*TBM(X(10),X(27))
1157 T(243)=1*TBM(X(10),X(28))
1158 T(244)=5*TBM(X(10),X(29))
1159 T(245)=2*TBM(X(10),X(30))
1165 T(246)=0*TBM(X(11),X(12))
1166 T(247)=0*TBM(X(11),X(13))
1167 T(248)=1*TBM(X(11),X(14))
1168 T(249)=2*TBM(X(11),X(15))
1169 T(250)=1*TBM(X(11),X(16))
1170 T(251)=0*TBM(X(11),X(17))
1171 T(252)=2*TBM(X(11),X(18))
1172 T(253)=0*TBM(X(11),X(19))
1173 T(254)=0*TBM(X(11),X(20))
1174 T(255)=0*TBM(X(11),X(21))
1175 T(256)=6*TBM(X(11),X(22))
1176 T(257)=6*TBM(X(11),X(23))
1177 T(258)=0*TBM(X(11),X(24))
1178 T(259)=4*TBM(X(11),X(25))
1179 T(260)=5*TBM(X(11),X(26))
1180 T(261)=3*TBM(X(11),X(27))
1181 T(262)=2*TBM(X(11),X(28))
1182 T(263)=2*TBM(X(11),X(29))
1183 T(264)=10*TBM(X(11),X(30))
1189 T(265)=5*TBM(X(12),X(13))
1190 T(266)=5*TBM(X(12),X(14))
1191 T(267)=2*TBM(X(12),X(15))
1192 T(268)=0*TBM(X(12),X(16))
1193 T(269)=0*TBM(X(12),X(17))
1194 T(270)=0*TBM(X(12),X(18))
1195 T(271)=0*TBM(X(12),X(19))
1196 T(272)=2*TBM(X(12),X(20))
1197 T(273)=0*TBM(X(12),X(21))
1198 T(274)=4*TBM(X(12),X(22))
1199 T(275)=5*TBM(X(12),X(23))
1200 T(276)=10*TBM(X(12),X(24))
1201 T(277)=1*TBM(X(12),X(25))
1202 T(278)=0*TBM(X(12),X(26))
1203 T(279)=0*TBM(X(12),X(27))
1204 T(280)=0*TBM(X(12),X(28))
1205 T(281)=0*TBM(X(12),X(29))
1206 T(282)=1*TBM(X(12),X(30))
1282 T(283)=2*TBM(X(13),X(14))
1283 T(284)=0*TBM(X(13),X(15))
1284 T(285)=4*TBM(X(13),X(16))
1285 T(286)=2*TBM(X(13),X(17))
1286 T(287)=2*TBM(X(13),X(18))
1287 T(288)=1*TBM(X(13),X(19))
1288 T(289)=0*TBM(X(13),X(20))
1289 T(290)=6*TBM(X(13),X(21))
1290 T(291)=2*TBM(X(13),X(22))
1291 T(292)=1*TBM(X(13),X(23))
1292 T(293)=5*TBM(X(13),X(24))
1293 T(294)=5*TBM(X(13),X(25))
1294 T(295)=0*TBM(X(13),X(26))
1295 T(296)=0*TBM(X(13),X(27))
1296 T(297)=1*TBM(X(13),X(28))
1297 T(298)=5*TBM(X(13),X(29))
1298 T(299)=5*TBM(X(13),X(30))
1384 T(300)=2*TBM(X(14),X(15))
1385 T(301)=1*TBM(X(14),X(16))
1386 T(302)=0*TBM(X(14),X(17))
1387 T(303)=5*TBM(X(14),X(18))
1388 T(304)=3*TBM(X(14),X(19))
1389 T(305)=10*TBM(X(14),X(20))
1390 T(306)=0*TBM(X(14),X(21))
1391 T(307)=0*TBM(X(14),X(22))
1392 T(308)=4*TBM(X(14),X(23))
1393 T(309)=2*TBM(X(14),X(24))
1394 T(310)=0*TBM(X(14),X(25))
1395 T(311)=0*TBM(X(14),X(26))
1396 T(312)=4*TBM(X(14),X(27))
1397 T(313)=2*TBM(X(14),X(28))
1398 T(314)=5*TBM(X(14),X(29))
1399 T(315)=5*TBM(X(14),X(30))
1411 T(316)=4*TBM(X(15),X(16))
1412 T(317)=5*TBM(X(15),X(17))
1413 T(318)=1*TBM(X(15),X(18))
1414 T(319)=0*TBM(X(15),X(19))
1415 T(320)=1*TBM(X(15),X(20))
1416 T(321)=0*TBM(X(15),X(21))
1417 T(322)=5*TBM(X(15),X(22))
1418 T(323)=0*TBM(X(15),X(23))
1419 T(324)=2*TBM(X(15),X(24))
1420 T(325)=0*TBM(X(15),X(25))
1421 T(326)=0*TBM(X(15),X(26))
1422 T(327)=5*TBM(X(15),X(27))
1423 T(328)=1*TBM(X(15),X(28))
1424 T(329)=1*TBM(X(15),X(29))
1425 T(330)=0*TBM(X(15),X(30))
1435 T(331)=0*TBM(X(16),X(17))
1436 T(332)=3*TBM(X(16),X(18))
1437 T(333)=0*TBM(X(16),X(19))
1438 T(334)=2*TBM(X(16),X(20))
1439 T(335)=2*TBM(X(16),X(21))
1440 T(336)=0*TBM(X(16),X(22))
1441 T(337)=2*TBM(X(16),X(23))
1442 T(338)=0*TBM(X(16),X(24))
1443 T(339)=5*TBM(X(16),X(25))
1444 T(340)=0*TBM(X(16),X(26))
1445 T(341)=5*TBM(X(16),X(27))
1446 T(342)=2*TBM(X(16),X(28))
1447 T(343)=5*TBM(X(16),X(29))
1448 T(344)=10*TBM(X(16),X(30))
1458 T(345)=2*TBM(X(17),X(18))
1459 T(346)=2*TBM(X(17),X(19))
1460 T(347)=0*TBM(X(17),X(20))
1461 T(348)=0*TBM(X(17),X(21))
1462 T(349)=0*TBM(X(17),X(22))
1463 T(350)=6*TBM(X(17),X(23))
1464 T(351)=5*TBM(X(17),X(24))
1465 T(352)=3*TBM(X(17),X(25))
1466 T(353)=5*TBM(X(17),X(26))
1467 T(354)=0*TBM(X(17),X(27))
1468 T(355)=0*TBM(X(17),X(28))
1469 T(356)=5*TBM(X(17),X(29))
1470 T(357)=1*TBM(X(17),X(30))
1480 T(358)=5*TBM(X(18),X(19))
1481 T(359)=1*TBM(X(18),X(20))
1482 T(360)=2*TBM(X(18),X(21))
1483 T(361)=10*TBM(X(18),X(22))
1484 T(362)=10*TBM(X(18),X(23))
1485 T(363)=4*TBM(X(18),X(24))
1486 T(364)=0*TBM(X(18),X(25))
1487 T(365)=0*TBM(X(18),X(26))
1488 T(366)=5*TBM(X(18),X(27))
1489 T(367)=0*TBM(X(18),X(28))
1490 T(368)=0*TBM(X(18),X(29))
1491 T(369)=0*TBM(X(18),X(30))
1501 T(370)=0*TBM(X(19),X(20))
1502 T(371)=5*TBM(X(19),X(21))
1503 T(372)=5*TBM(X(19),X(22))
1504 T(373)=1*TBM(X(19),X(23))
1505 T(374)=0*TBM(X(19),X(24))
1506 T(375)=5*TBM(X(19),X(25))
1507 T(376)=2*TBM(X(19),X(26))
1508 T(377)=1*TBM(X(19),X(27))
1509 T(378)=2*TBM(X(19),X(28))
1510 T(379)=10*TBM(X(19),X(29))
1511 T(380)=10*TBM(X(19),X(30))
1513 T(381)=5*TBM(X(20),X(21))
1514 T(382)=2*TBM(X(20),X(22))
1515 T(383)=1*TBM(X(20),X(23))
1516 T(384)=3*TBM(X(20),X(24))
1517 T(385)=1*TBM(X(20),X(25))
1518 T(386)=5*TBM(X(20),X(26))
1519 T(387)=6*TBM(X(20),X(27))
1520 T(388)=5*TBM(X(20),X(28))
1521 T(389)=5*TBM(X(20),X(29))
1522 T(390)=3*TBM(X(20),X(30))
1524 T(391)=4*TBM(X(21),X(22))
1525 T(392)=0*TBM(X(21),X(23))
1526 T(393)=1*TBM(X(21),X(24))
1527 T(394)=0*TBM(X(21),X(25))
1528 T(395)=0*TBM(X(21),X(26))
1529 T(396)=0*TBM(X(21),X(27))
1530 T(397)=5*TBM(X(21),X(28))
1531 T(398)=0*TBM(X(21),X(29))
1532 T(399)=0*TBM(X(21),X(30))
1534 T(400)=5*TBM(X(22),X(23))
1535 T(401)=0*TBM(X(22),X(24))
1536 T(402)=4*TBM(X(22),X(25))
1537 T(403)=4*TBM(X(22),X(26))
1538 T(404)=5*TBM(X(22),X(27))
1539 T(405)=0*TBM(X(22),X(28))
1540 T(406)=2*TBM(X(22),X(29))
1541 T(407)=5*TBM(X(22),X(30))
1543 T(408)=0*TBM(X(23),X(24))
1544 T(409)=4*TBM(X(23),X(25))
1545 T(410)=4*TBM(X(23),X(26))
1546 T(411)=1*TBM(X(23),X(27))
1547 T(412)=0*TBM(X(23),X(28))
1548 T(413)=2*TBM(X(23),X(29))
1549 T(414)=2*TBM(X(23),X(30))
1551 T(415)=5*TBM(X(24),X(25))
1552 T(416)=5*TBM(X(24),X(26))
1553 T(417)=0*TBM(X(24),X(27))
1554 T(418)=1*TBM(X(24),X(28))
1555 T(419)=0*TBM(X(24),X(29))
1556 T(420)=0*TBM(X(24),X(30))
1558 T(421)=1*TBM(X(25),X(26))
1559 T(422)=0*TBM(X(25),X(27))
1560 T(423)=10*TBM(X(25),X(28))
1561 T(424)=1*TBM(X(25),X(29))
1562 T(425)=0*TBM(X(25),X(30))
1564 T(426)=0*TBM(X(26),X(27))
1565 T(427)=0*TBM(X(26),X(28))
1566 T(428)=0*TBM(X(26),X(29))
1567 T(429)=0*TBM(X(26),X(30))
1570 T(430)=0*TBM(X(27),X(28))
1571 T(431)=0*TBM(X(27),X(29))
1572 T(432)=10*TBM(X(27),X(30))
1573 T(433)=2*TBM(X(28),X(29))
1574 T(434)=2*TBM(X(28),X(30))
1577 T(435)=2*TBM(X(29),X(30))
1651 P1NEW=0
1652 FOR KAU7=1 TO 435
1653 P1NEW=P1NEW+T(KAU7)
1654 NEXT KAU7
1655 P=-P1NEW
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 30
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 228
1670 NEXT I
1890 IF M>-3066 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1927 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 5.3 hours of running is presented below. What immediately follows is a manual copy from the computer screen.

17 2 27 19 6
4 15 16 9 10
22 5 3 26 30
21 18 29 14 25
1 23 24 11 13
12 28 7 8 20
-3062 -29395

3062 is optimal, Loiola et al. (2007, p. 668). Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-29395 was produced during the first 5.3 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).

Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).

Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).

Loiola, E. M., N. M. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido, "A Survey for the Quadratic Assignment Problem," European Journal of Operational Research 176, 657-690 (2007).

Nugent,C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1966).

Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly 18, 1-36 (1971).

Wednesday, August 26, 2009

A Computer Program for Solving Integer Programs

Jsun Yui Wong

The computer program listed below seeks to solve the 20-department problem in Nugent, Vollmann, and Ruml (1968).

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(466)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=4:TBM(1,6)=1:TBM(1,7)=2:TBM(1,8)=3:TBM(1,9)=4:TBM(1,10)=5
12 TBM(1,11)=2:TBM(1,12)=3:TBM(1,13)=4:TBM(1,14)=5:TBM(1,15)=6:TBM(1,16)=3:TBM(1,17)=4:TBM(1,18)=5:TBM(1,19)=6:TBM(1,20)=7
13 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=3:TBM(2,6)=2:TBM(2,7)=1:TBM(2,8)=2:TBM(2,9)=3:TBM(2,10)=4
14 TBM(2,11)=3:TBM(2,12)=2:TBM(2,13)=3:TBM(2,14)=4:TBM(2,15)=5:TBM(2,16)=4:TBM(2,17)=3:TBM(2,18)=4:TBM(2,19)=5:TBM(2,20)=6
15 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=3:TBM(3,7)=2:TBM(3,8)=1:TBM(3,9)=2:TBM(3,10)=3
16 TBM(3,11)=4:TBM(3,12)=3:TBM(3,13)=2:TBM(3,14)=3:TBM(3,15)=4:TBM(3,16)=5:TBM(3,17)=4:TBM(3,18)=3:TBM(3,19)=4:TBM(3,20)=5
17 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=1:TBM(4,6)=4:TBM(4,7)=3:TBM(4,8)=2:TBM(4,9)=1:TBM(4,10)=2
18 TBM(4,11)=5:TBM(4,12)=4:TBM(4,13)=3:TBM(4,14)=2:TBM(4,15)=3:TBM(4,16)=6:TBM(4,17)=5:TBM(4,18)=4:TBM(4,19)=3:TBM(4,20)=4
19 TBM(5,1)=4:TBM(5,2)=3:TBM(5,3)=2:TBM(5,4)=1:TBM(5,5)=999:TBM(5,6)=5:TBM(5,7)=4:TBM(5,8)=3:TBM(5,9)=2:TBM(5,10)=1
20 TBM(5,11)=6:TBM(5,12)=5:TBM(5,13)=4:TBM(5,14)=3:TBM(5,15)=2:TBM(5,16)=7:TBM(5,17)=6:TBM(5,18)=5:TBM(5,19)=4:TBM(5,20)=3
21 TBM(6,1)=1:TBM(6,2)=2:TBM(6,3)=3:TBM(6,4)=4:TBM(6,5)=5:TBM(6,6)=999:TBM(6,7)=1:TBM(6,8)=2:TBM(6,9)=3:TBM(6,10)=4
22 TBM(6,11)=1:TBM(6,12)=2:TBM(6,13)=3:TBM(6,14)=4:TBM(6,15)=5:TBM(6,16)=2:TBM(6,17)=3:TBM(6,18)=4:TBM(6,19)=5:TBM(6,20)=6
23 TBM(7,1)=2:TBM(7,2)=1:TBM(7,3)=2:TBM(7,4)=3:TBM(7,5)=4:TBM(7,6)=1:TBM(7,7)=999:TBM(7,8)=1:TBM(7,9)=2:TBM(7,10)=3
24 TBM(7,11)=2:TBM(7,12)=1:TBM(7,13)=2:TBM(7,14)=3:TBM(7,15)=4:TBM(7,16)=3:TBM(7,17)=2:TBM(7,18)=3:TBM(7,19)=4:TBM(7,20)=5
25 TBM(8,1)=3:TBM(8,2)=2:TBM(8,3)=1:TBM(8,4)=2:TBM(8,5)=3:TBM(8,6)=2:TBM(8,7)=1:TBM(8,8)=999:TBM(8,9)=1:TBM(8,10)=2
26 TBM(8,11)=3:TBM(8,12)=2:TBM(8,13)=1:TBM(8,14)=2:TBM(8,15)=3:TBM(8,16)=4:TBM(8,17)=3:TBM(8,18)=2:TBM(8,19)=3:TBM(8,20)=4
27 TBM(9,1)=4:TBM(9,2)=3:TBM(9,3)=2:TBM(9,4)=1:TBM(9,5)=2:TBM(9,6)=3:TBM(9,7)=2:TBM(9,8)=1:TBM(9,9)=999:TBM(9,10)=1
28 TBM(9,11)=4:TBM(9,12)=3:TBM(9,13)=2:TBM(9,14)=1:TBM(9,15)=2:TBM(9,16)=5:TBM(9,17)=4:TBM(9,18)=3:TBM(9,19)=2:TBM(9,20)=3
29 TBM(10,1)=5:TBM(10,2)=4:TBM(10,3)=3:TBM(10,4)=2:TBM(10,5)=1:TBM(10,6)=4:TBM(10,7)=3:TBM(10,8)=2:TBM(10,9)=1:TBM(10,10)=999
30 TBM(10,11)=5:TBM(10,12)=4:TBM(10,13)=3:TBM(10,14)=2:TBM(10,15)=1:TBM(10,16)=6:TBM(10,17)=5:TBM(10,18)=4:TBM(10,19)=3:TBM(10,20)=2
31 TBM(11,1)=2:TBM(11,2)=3:TBM(11,3)=4:TBM(11,4)=5:TBM(11,5)=6:TBM(11,6)=1:TBM(11,7)=2:TBM(11,8)=3:TBM(11,9)=4:TBM(11,10)=5
32 TBM(11,11)=999:TBM(11,12)=1:TBM(11,13)=2:TBM(11,14)=3:TBM(11,15)=4:TBM(11,16)=1:TBM(11,17)=2:TBM(11,18)=3:TBM(11,19)=4:TBM(11,20)=5
33 TBM(12,1)=3:TBM(12,2)=2:TBM(12,3)=3:TBM(12,4)=4:TBM(12,5)=5:TBM(12,6)=2:TBM(12,7)=1:TBM(12,8)=2:TBM(12,9)=3:TBM(12,10)=4
34 TBM(12,11)=1:TBM(12,12)=999:TBM(12,13)=1:TBM(12,14)=2:TBM(12,15)=3:TBM(12,16)=2:TBM(12,17)=1:TBM(12,18)=2:TBM(12,19)=3:TBM(12,20)=4
35 TBM(13,1)=4:TBM(13,2)=3:TBM(13,3)=2:TBM(13,4)=3:TBM(13,5)=4:TBM(13,6)=3:TBM(13,7)=2:TBM(13,8)=1:TBM(13,9)=2:TBM(13,10)=3
36 TBM(13,11)=2:TBM(13,12)=1:TBM(13,13)=999:TBM(13,14)=1:TBM(13,15)=2:TBM(13,16)=3:TBM(13,17)=2:TBM(13,18)=1:TBM(13,19)=2:TBM(13,20)=3
37 TBM(14,1)=5:TBM(14,2)=4:TBM(14,3)=3:TBM(14,4)=2:TBM(14,5)=3:TBM(14,6)=4:TBM(14,7)=3:TBM(14,8)=2:TBM(14,9)=1:TBM(14,10)=2
38 TBM(14,11)=3:TBM(14,12)=2:TBM(14,13)=1:TBM(14,14)=999:TBM(14,15)=1:TBM(14,16)=4:TBM(14,17)=3:TBM(14,18)=2:TBM(14,19)=1:TBM(14,20)=2
39 TBM(15,1)=6:TBM(15,2)=5:TBM(15,3)=4:TBM(15,4)=3:TBM(15,5)=2:TBM(15,6)=5:TBM(15,7)=4:TBM(15,8)=3:TBM(15,9)=2:TBM(15,10)=1
40 TBM(15,11)=4:TBM(15,12)=3:TBM(15,13)=2:TBM(15,14)=1:TBM(15,15)=999:TBM(15,16)=5:TBM(15,17)=4:TBM(15,18)=3:TBM(15,19)=2:TBM(15,20)=1
41 TBM(16,1)=3:TBM(16,2)=4:TBM(16,3)=5:TBM(16,4)=6:TBM(16,5)=7:TBM(16,6)=2:TBM(16,7)=3:TBM(16,8)=4:TBM(16,9)=5:TBM(16,10)=6
42 TBM(16,11)=1:TBM(16,12)=2:TBM(16,13)=3:TBM(16,14)=4:TBM(16,15)=5:TBM(16,16)=999:TBM(16,17)=1:TBM(16,18)=2:TBM(16,19)=3:TBM(16,20)=4
43 TBM(17,1)=4:TBM(17,2)=3:TBM(17,3)=4:TBM(17,4)=5:TBM(17,5)=6:TBM(17,6)=3:TBM(17,7)=2:TBM(17,8)=3:TBM(17,9)=4:TBM(17,10)=5
44 TBM(17,11)=2:TBM(17,12)=1:TBM(17,13)=2:TBM(17,14)=3:TBM(17,15)=4:TBM(17,16)=1:TBM(17,17)=999:TBM(17,18)=1:TBM(17,19)=2:TBM(17,20)=3
45 TBM(18,1)=5:TBM(18,2)=4:TBM(18,3)=3:TBM(18,4)=4:TBM(18,5)=5:TBM(18,6)=4:TBM(18,7)=3:TBM(18,8)=2:TBM(18,9)=3:TBM(18,10)=4
46 TBM(18,11)=3:TBM(18,12)=2:TBM(18,13)=1:TBM(18,14)=2:TBM(18,15)=3:TBM(18,16)=2:TBM(18,17)=1:TBM(18,18)=999:TBM(18,19)=1:TBM(18,20)=2
47 TBM(19,1)=6:TBM(19,2)=5:TBM(19,3)=4:TBM(19,4)=3:TBM(19,5)=4:TBM(19,6)=5:TBM(19,7)=4:TBM(19,8)=3:TBM(19,9)=2:TBM(19,10)=3
48 TBM(19,11)=4:TBM(19,12)=3:TBM(19,13)=2:TBM(19,14)=1:TBM(19,15)=2:TBM(19,16)=3:TBM(19,17)=2:TBM(19,18)=1:TBM(19,19)=999:TBM(19,20)=1
49 TBM(20,1)=7:TBM(20,2)=6:TBM(20,3)=5:TBM(20,4)=4:TBM(20,5)=3:TBM(20,6)=6:TBM(20,7)=5:TBM(20,8)=4:TBM(20,9)=3:TBM(20,10)=2
50 TBM(20,11)=5:TBM(20,12)=4:TBM(20,13)=3:TBM(20,14)=2:TBM(20,15)=1:TBM(20,16)=4:TBM(20,17)=3:TBM(20,18)=2:TBM(20,19)=1:TBM(20,20)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
82 A(11)=11:A(12)=12:A(13)=13:A(14)=14:A(15)=15:A(16)=16:A(17)=17:A(18)=18:A(19)=19:A(20)=20
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 20
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*20)
331 IJN=1+FIX(RND*20)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=0*TBM(X(1),X(2))
402 T(2)=5*TBM(X(1),X(3))
403 T(3)=0*TBM(X(1),X(4))
404 T(4)=5*TBM(X(1),X(5))
405 T(5)=2*TBM(X(1),X(6))
406 T(6)=10*TBM(X(1),X(7))
407 T(7)=3*TBM(X(1),X(8))
408 T(8)=1*TBM(X(1),X(9))
409 T(9)=5*TBM(X(1),X(10))
410 T(10)=5*TBM(X(1),X(11))
411 T(11)=5*TBM(X(1),X(12))
412 T(12)=0*TBM(X(1),X(13))
413 T(13)=0*TBM(X(1),X(14))
414 T(14)=5*TBM(X(1),X(15))
415 T(15)=4*TBM(X(1),X(16))
416 T(16)=4*TBM(X(1),X(17))
417 T(17)=0*TBM(X(1),X(18))
418 T(18)=0*TBM(X(1),X(19))
419 T(19)=1*TBM(X(1),X(20))
615 T(20)=3*TBM(X(2),X(3))
616 T(21)=10*TBM(X(2),X(4))
617 T(22)=5*TBM(X(2),X(5))
618 T(23)=1*TBM(X(2),X(6))
619 T(24)=5*TBM(X(2),X(7))
620 T(25)=1*TBM(X(2),X(8))
621 T(26)=2*TBM(X(2),X(9))
622 T(27)=4*TBM(X(2),X(10))
623 T(28)=2*TBM(X(2),X(11))
624 T(29)=5*TBM(X(2),X(12))
625 T(30)=0*TBM(X(2),X(13))
626 T(31)=10*TBM(X(2),X(14))
627 T(32)=10*TBM(X(2),X(15))
628 T(33)=3*TBM(X(2),X(16))
629 T(34)=0*TBM(X(2),X(17))
630 T(35)=5*TBM(X(2),X(18))
631 T(36)=10*TBM(X(2),X(19))
632 T(37)=5*TBM(X(2),X(20))
648 T(38)=2*TBM(X(3),X(4))
649 T(39)=0*TBM(X(3),X(5))
650 T(40)=5*TBM(X(3),X(6))
651 T(41)=2*TBM(X(3),X(7))
652 T(42)=4*TBM(X(3),X(8))
653 T(43)=4*TBM(X(3),X(9))
654 T(44)=5*TBM(X(3),X(10))
655 T(45)=0*TBM(X(3),X(11))
656 T(46)=0*TBM(X(3),X(12))
657 T(47)=0*TBM(X(3),X(13))
658 T(48)=5*TBM(X(3),X(14))
659 T(49)=1*TBM(X(3),X(15))
660 T(50)=0*TBM(X(3),X(16))
661 T(51)=0*TBM(X(3),X(17))
662 T(52)=5*TBM(X(3),X(18))
663 T(53)=0*TBM(X(3),X(19))
664 T(54)=0*TBM(X(3),X(20))
740 T(55)=1*TBM(X(4),X(5))
741 T(56)=0*TBM(X(4),X(6))
742 T(57)=5*TBM(X(4),X(7))
743 T(58)=2*TBM(X(4),X(8))
744 T(59)=1*TBM(X(4),X(9))
745 T(60)=0*TBM(X(4),X(10))
746 T(61)=10*TBM(X(4),X(11))
747 T(62)=2*TBM(X(4),X(12))
748 T(63)=2*TBM(X(4),X(13))
749 T(64)=0*TBM(X(4),X(14))
750 T(65)=2*TBM(X(4),X(15))
751 T(66)=1*TBM(X(4),X(16))
752 T(67)=5*TBM(X(4),X(17))
753 T(68)=2*TBM(X(4),X(18))
754 T(69)=5*TBM(X(4),X(19))
755 T(70)=5*TBM(X(4),X(20))
851 T(71)=5*TBM(X(5),X(6))
852 T(72)=6*TBM(X(5),X(7))
853 T(73)=5*TBM(X(5),X(8))
854 T(74)=2*TBM(X(5),X(9))
855 T(75)=5*TBM(X(5),X(10))
856 T(76)=2*TBM(X(5),X(11))
857 T(77)=0*TBM(X(5),X(12))
858 T(78)=5*TBM(X(5),X(13))
859 T(79)=1*TBM(X(5),X(14))
860 T(80)=1*TBM(X(5),X(15))
861 T(81)=1*TBM(X(5),X(16))
862 T(82)=5*TBM(X(5),X(17))
863 T(83)=2*TBM(X(5),X(18))
864 T(84)=5*TBM(X(5),X(19))
865 T(85)=1*TBM(X(5),X(20))
961 T(86)=5*TBM(X(6),X(7))
962 T(87)=2*TBM(X(6),X(8))
963 T(88)=1*TBM(X(6),X(9))
964 T(89)=6*TBM(X(6),X(10))
965 T(90)=0*TBM(X(6),X(11))
966 T(91)=0*TBM(X(6),X(12))
967 T(92)=10*TBM(X(6),X(13))
968 T(93)=0*TBM(X(6),X(14))
969 T(94)=2*TBM(X(6),X(15))
970 T(95)=0*TBM(X(6),X(16))
971 T(96)=1*TBM(X(6),X(17))
972 T(97)=0*TBM(X(6),X(18))
973 T(98)=1*TBM(X(6),X(19))
974 T(99)=5*TBM(X(6),X(20))
1047 T(100)=0*TBM(X(7),X(8))
1048 T(101)=0*TBM(X(7),X(9))
1051 T(102)=0*TBM(X(7),X(10))
1052 T(103)=5*TBM(X(7),X(11))
1053 T(104)=10*TBM(X(7),X(12))
1054 T(105)=2*TBM(X(7),X(13))
1055 T(106)=2*TBM(X(7),X(14))
1056 T(107)=5*TBM(X(7),X(15))
1057 T(108)=1*TBM(X(7),X(16))
1058 T(109)=2*TBM(X(7),X(17))
1059 T(110)=1*TBM(X(7),X(18))
1060 T(111)=0*TBM(X(7),X(19))
1061 T(112)=10*TBM(X(7),X(20))
1077 T(113)=1*TBM(X(8),X(9))
1078 T(114)=1*TBM(X(8),X(10))
1079 T(115)=10*TBM(X(8),X(11))
1080 T(116)=10*TBM(X(8),X(12))
1081 T(117)=2*TBM(X(8),X(13))
1082 T(118)=0*TBM(X(8),X(14))
1083 T(119)=10*TBM(X(8),X(15))
1084 T(120)=2*TBM(X(8),X(16))
1085 T(121)=5*TBM(X(8),X(17))
1086 T(122)=2*TBM(X(8),X(18))
1087 T(123)=2*TBM(X(8),X(19))
1088 T(124)=10*TBM(X(8),X(20))
1114 T(125)=2*TBM(X(9),X(10))
1115 T(126)=0*TBM(X(9),X(11))
1116 T(127)=3*TBM(X(9),X(12))
1117 T(128)=5*TBM(X(9),X(13))
1118 T(129)=5*TBM(X(9),X(14))
1119 T(130)=0*TBM(X(9),X(15))
1120 T(131)=5*TBM(X(9),X(16))
1121 T(132)=0*TBM(X(9),X(17))
1122 T(133)=0*TBM(X(9),X(18))
1123 T(134)=0*TBM(X(9),X(19))
1124 T(135)=2*TBM(X(9),X(20))
1140 T(136)=5*TBM(X(10),X(11))
1141 T(137)=5*TBM(X(10),X(12))
1142 T(138)=0*TBM(X(10),X(13))
1143 T(139)=5*TBM(X(10),X(14))
1144 T(140)=1*TBM(X(10),X(15))
1145 T(141)=0*TBM(X(10),X(16))
1146 T(142)=0*TBM(X(10),X(17))
1147 T(143)=5*TBM(X(10),X(18))
1148 T(144)=5*TBM(X(10),X(19))
1149 T(145)=2*TBM(X(10),X(20))
1165 T(146)=5*TBM(X(11),X(12))
1166 T(147)=2*TBM(X(11),X(13))
1167 T(148)=5*TBM(X(11),X(14))
1168 T(149)=1*TBM(X(11),X(15))
1169 T(150)=10*TBM(X(11),X(16))
1170 T(151)=0*TBM(X(11),X(17))
1171 T(152)=2*TBM(X(11),X(18))
1172 T(153)=2*TBM(X(11),X(19))
1173 T(154)=5*TBM(X(11),X(20))
1189 T(155)=2*TBM(X(12),X(13))
1190 T(156)=10*TBM(X(12),X(14))
1191 T(157)=5*TBM(X(12),X(15))
1192 T(158)=0*TBM(X(12),X(16))
1193 T(159)=1*TBM(X(12),X(17))
1194 T(160)=1*TBM(X(12),X(18))
1195 T(161)=2*TBM(X(12),X(19))
1196 T(162)=5*TBM(X(12),X(20))
1282 T(163)=2*TBM(X(13),X(14))
1283 T(164)=2*TBM(X(13),X(15))
1284 T(165)=1*TBM(X(13),X(16))
1285 T(166)=0*TBM(X(13),X(17))
1286 T(167)=0*TBM(X(13),X(18))
1287 T(168)=0*TBM(X(13),X(19))
1288 T(169)=5*TBM(X(13),X(20))
1384 T(170)=5*TBM(X(14),X(15))
1385 T(171)=5*TBM(X(14),X(16))
1386 T(172)=1*TBM(X(14),X(17))
1387 T(173)=5*TBM(X(14),X(18))
1388 T(174)=5*TBM(X(14),X(19))
1389 T(175)=0*TBM(X(14),X(20))
1411 T(176)=3*TBM(X(15),X(16))
1412 T(177)=0*TBM(X(15),X(17))
1413 T(178)=5*TBM(X(15),X(18))
1414 T(179)=10*TBM(X(15),X(19))
1415 T(180)=10*TBM(X(15),X(20))
1435 T(181)=0*TBM(X(16),X(17))
1436 T(182)=0*TBM(X(16),X(18))
1437 T(183)=2*TBM(X(16),X(19))
1438 T(184)=0*TBM(X(16),X(20))
1458 T(185)=5*TBM(X(17),X(18))
1459 T(186)=2*TBM(X(17),X(19))
1460 T(187)=0*TBM(X(17),X(20))
1480 T(188)=1*TBM(X(18),X(19))
1481 T(189)=1*TBM(X(18),X(20))
1501 T(190)=6*TBM(X(19),X(20))
1651 P1NEW=0
1652 FOR KAU7=1 TO 190
1653 P1NEW=P1NEW+T(KAU7)
1654 NEXT KAU7
1655 P=-P1NEW
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 20
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-1286 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1927 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 10 minutes of running is presented below. What immediately follows is a manual copy from the computer screen.

2 14 17 15 4
1 3 7 16 18
12 13 6 19 9
11 5 20 10 8
-1285 -31898

2 14 17 15 4
1 3 7 16 18
12 13 6 19 9
11 5 20 10 8
-1285 -31810

17 9 2 10 19
16 18 12 1 3
7 8 11 4 14
6 20 5 15 13
-1285 -31506

1285 is optimal, Loiola et al. (2007, p. 668). Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31506 was produced during the first 10 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).

Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).

Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).

Loiola, E. M., N. M. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido, "A Survey for the Quadratic Assignment Problem," European Journal of Operational Research 176, 657-690 (2007).

Nugent, C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1966).

Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).

Tuesday, August 25, 2009

A Computer Program for Integer Programming

Jsun Yui Wong

The computer program listed below seeks to solve the 15-department problem in Nugent, Vollmann, and Ruml (1968).

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(111)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=4:TBM(1,6)=1:TBM(1,7)=2:TBM(1,8)=3:TBM(1,9)=4:TBM(1,10)=5
12 TBM(1,11)=2:TBM(1,12)=3:TBM(1,13)=4:TBM(1,14)=5:TBM(1,15)=6
13 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=3:TBM(2,6)=2:TBM(2,7)=1:TBM(2,8)=2:TBM(2,9)=3:TBM(2,10)=4
14 TBM(2,11)=3:TBM(2,12)=2:TBM(2,13)=3:TBM(2,14)=4:TBM(2,15)=5
15 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=3:TBM(3,7)=2:TBM(3,8)=1:TBM(3,9)=2:TBM(3,10)=3
16 TBM(3,11)=4:TBM(3,12)=3:TBM(3,13)=2:TBM(3,14)=3:TBM(3,15)=4
17 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=1:TBM(4,6)=4:TBM(4,7)=3:TBM(4,8)=2:TBM(4,9)=1:TBM(4,10)=2
18 TBM(4,11)=5:TBM(4,12)=4:TBM(4,13)=3:TBM(4,14)=2:TBM(4,15)=3
19 TBM(5,1)=4:TBM(5,2)=3:TBM(5,3)=2:TBM(5,4)=1:TBM(5,5)=999:TBM(5,6)=5:TBM(5,7)=4:TBM(5,8)=3:TBM(5,9)=2:TBM(5,10)=1
20 TBM(5,11)=6:TBM(5,12)=5:TBM(5,13)=4:TBM(5,14)=3:TBM(5,15)=2
21 TBM(6,1)=1:TBM(6,2)=2:TBM(6,3)=3:TBM(6,4)=4:TBM(6,5)=5:TBM(6,6)=999:TBM(6,7)=1:TBM(6,8)=2:TBM(6,9)=3:TBM(6,10)=4
22 TBM(6,11)=1:TBM(6,12)=2:TBM(6,13)=3:TBM(6,14)=4:TBM(6,15)=5
23 TBM(7,1)=2:TBM(7,2)=1:TBM(7,3)=2:TBM(7,4)=3:TBM(7,5)=4:TBM(7,6)=1:TBM(7,7)=999:TBM(7,8)=1:TBM(7,9)=2:TBM(7,10)=3
24 TBM(7,11)=2:TBM(7,12)=1:TBM(7,13)=2:TBM(7,14)=3:TBM(7,15)=4
25 TBM(8,1)=3:TBM(8,2)=2:TBM(8,3)=1:TBM(8,4)=2:TBM(8,5)=3:TBM(8,6)=2:TBM(8,7)=1:TBM(8,8)=999:TBM(8,9)=1:TBM(8,10)=2
26 TBM(8,11)=3:TBM(8,12)=2:TBM(8,13)=1:TBM(8,14)=2:TBM(8,15)=3
27 TBM(9,1)=4:TBM(9,2)=3:TBM(9,3)=2:TBM(9,4)=1:TBM(9,5)=2:TBM(9,6)=3:TBM(9,7)=2:TBM(9,8)=1:TBM(9,9)=999:TBM(9,10)=1
28 TBM(9,11)=4:TBM(9,12)=3:TBM(9,13)=2:TBM(9,14)=1:TBM(9,15)=2
29 TBM(10,1)=5:TBM(10,2)=4:TBM(10,3)=3:TBM(10,4)=2:TBM(10,5)=1:TBM(10,6)=4:TBM(10,7)=3:TBM(10,8)=2:TBM(10,9)=1:TBM(10,10)=999
30 TBM(10,11)=5:TBM(10,12)=4:TBM(10,13)=3:TBM(10,14)=2:TBM(10,15)=1
31 TBM(11,1)=2:TBM(11,2)=3:TBM(11,3)=4:TBM(11,4)=5:TBM(11,5)=6:TBM(11,6)=1:TBM(11,7)=2:TBM(11,8)=3:TBM(11,9)=4:TBM(11,10)=5
32 TBM(11,11)=999:TBM(11,12)=1:TBM(11,13)=2:TBM(11,14)=3:TBM(11,15)=4
33 TBM(12,1)=3:TBM(12,2)=2:TBM(12,3)=3:TBM(12,4)=4:TBM(12,5)=5:TBM(12,6)=2:TBM(12,7)=1:TBM(12,8)=2:TBM(12,9)=3:TBM(12,10)=4
34 TBM(12,11)=1:TBM(12,12)=999:TBM(12,13)=1:TBM(12,14)=2:TBM(12,15)=3
35 TBM(13,1)=4:TBM(13,2)=3:TBM(13,3)=2:TBM(13,4)=3:TBM(13,5)=4:TBM(13,6)=3:TBM(13,7)=2:TBM(13,8)=1:TBM(13,9)=2:TBM(13,10)=3
36 TBM(13,11)=2:TBM(13,12)=1:TBM(13,13)=999:TBM(13,14)=1:TBM(13,15)=2
37 TBM(14,1)=5:TBM(14,2)=4:TBM(14,3)=3:TBM(14,4)=2:TBM(14,5)=3:TBM(14,6)=4:TBM(14,7)=3:TBM(14,8)=2:TBM(14,9)=1:TBM(14,10)=2
38 TBM(14,11)=3:TBM(14,12)=2:TBM(14,13)=1:TBM(14,14)=999:TBM(14,15)=1
39 TBM(15,1)=6:TBM(15,2)=5:TBM(15,3)=4:TBM(15,4)=3:TBM(15,5)=2:TBM(15,6)=5:TBM(15,7)=4:TBM(15,8)=3:TBM(15,9)=2:TBM(15,10)=1
40 TBM(15,11)=4:TBM(15,12)=3:TBM(15,13)=2:TBM(15,14)=1:TBM(15,15)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
82 A(11)=11:A(12)=12:A(13)=13:A(14)=14:A(15)=15
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 15
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*15)
331 IJN=1+FIX(RND*15)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=10*TBM(X(1),X(2))
402 T(2)=0*TBM(X(1),X(3))
403 T(3)=5*TBM(X(1),X(4))
404 T(4)=1*TBM(X(1),X(5))
405 T(5)=0*TBM(X(1),X(6))
406 T(6)=1*TBM(X(1),X(7))
407 T(7)=2*TBM(X(1),X(8))
408 T(8)=2*TBM(X(1),X(9))
409 T(9)=2*TBM(X(1),X(10))
410 T(10)=2*TBM(X(1),X(11))
411 T(11)=0*TBM(X(1),X(12))
412 T(12)=4*TBM(X(1),X(13))
413 T(13)=0*TBM(X(1),X(14))
414 T(14)=0*TBM(X(1),X(15))
415 T(15)=1*TBM(X(2),X(3))
416 T(16)=3*TBM(X(2),X(4))
417 T(17)=2*TBM(X(2),X(5))
418 T(18)=2*TBM(X(2),X(6))
419 T(19)=2*TBM(X(2),X(7))
420 T(20)=3*TBM(X(2),X(8))
421 T(21)=2*TBM(X(2),X(9))
422 T(22)=0*TBM(X(2),X(10))
423 T(23)=2*TBM(X(2),X(11))
424 T(24)=0*TBM(X(2),X(12))
425 T(25)=10*TBM(X(2),X(13))
426 T(26)=5*TBM(X(2),X(14))
427 T(27)=0*TBM(X(2),X(15))
428 T(28)=10*TBM(X(3),X(4))
429 T(29)=2*TBM(X(3),X(5))
430 T(30)=0*TBM(X(3),X(6))
431 T(31)=2*TBM(X(3),X(7))
432 T(32)=5*TBM(X(3),X(8))
433 T(33)=4*TBM(X(3),X(9))
434 T(34)=5*TBM(X(3),X(10))
435 T(35)=2*TBM(X(3),X(11))
436 T(36)=2*TBM(X(3),X(12))
437 T(37)=5*TBM(X(3),X(13))
438 T(38)=5*TBM(X(3),X(14))
439 T(39)=5*TBM(X(3),X(15))
440 T(40)=1*TBM(X(4),X(5))
441 T(41)=1*TBM(X(4),X(6))
442 T(42)=5*TBM(X(4),X(7))
443 T(43)=0*TBM(X(4),X(8))
444 T(44)=0*TBM(X(4),X(9))
445 T(45)=2*TBM(X(4),X(10))
446 T(46)=1*TBM(X(4),X(11))
447 T(47)=0*TBM(X(4),X(12))
448 T(48)=2*TBM(X(4),X(13))
449 T(49)=5*TBM(X(4),X(14))
450 T(50)=0*TBM(X(4),X(15))
451 T(51)=3*TBM(X(5),X(6))
452 T(52)=5*TBM(X(5),X(7))
453 T(53)=5*TBM(X(5),X(8))
454 T(54)=5*TBM(X(5),X(9))
455 T(55)=1*TBM(X(5),X(10))
456 T(56)=0*TBM(X(5),X(11))
457 T(57)=3*TBM(X(5),X(12))
458 T(58)=0*TBM(X(5),X(13))
459 T(59)=5*TBM(X(5),X(14))
460 T(60)=5*TBM(X(5),X(15))
461 T(61)=2*TBM(X(6),X(7))
462 T(62)=2*TBM(X(6),X(8))
463 T(63)=1*TBM(X(6),X(9))
464 T(64)=5*TBM(X(6),X(10))
465 T(65)=0*TBM(X(6),X(11))
466 T(66)=0*TBM(X(6),X(12))
467 T(67)=2*TBM(X(6),X(13))
468 T(68)=5*TBM(X(6),X(14))
469 T(69)=10*TBM(X(6),X(15))
470 T(70)=6*TBM(X(7),X(8))
471 T(71)=0*TBM(X(7),X(9))
551 T(72)=1*TBM(X(7),X(10))
552 T(73)=5*TBM(X(7),X(11))
553 T(74)=5*TBM(X(7),X(12))
554 T(75)=5*TBM(X(7),X(13))
555 T(76)=1*TBM(X(7),X(14))
556 T(77)=0*TBM(X(7),X(15))
557 T(78)=5*TBM(X(8),X(9))
558 T(79)=2*TBM(X(8),X(10))
559 T(80)=10*TBM(X(8),X(11))
560 T(81)=0*TBM(X(8),X(12))
561 T(82)=5*TBM(X(8),X(13))
562 T(83)=0*TBM(X(8),X(14))
563 T(84)=0*TBM(X(8),X(15))
564 T(85)=0*TBM(X(9),X(10))
565 T(86)=10*TBM(X(9),X(11))
566 T(87)=5*TBM(X(9),X(12))
567 T(88)=10*TBM(X(9),X(13))
568 T(89)=0*TBM(X(9),X(14))
569 T(90)=2*TBM(X(9),X(15))
570 T(91)=0*TBM(X(10),X(11))
571 T(92)=4*TBM(X(10),X(12))
572 T(93)=0*TBM(X(10),X(13))
573 T(94)=0*TBM(X(10),X(14))
574 T(95)=5*TBM(X(10),X(15))
575 T(96)=5*TBM(X(11),X(12))
576 T(97)=0*TBM(X(11),X(13))
577 T(98)=5*TBM(X(11),X(14))
578 T(99)=0*TBM(X(11),X(15))
579 T(100)=3*TBM(X(12),X(13))
580 T(101)=3*TBM(X(12),X(14))
581 T(102)=0*TBM(X(12),X(15))
582 T(103)=10*TBM(X(13),X(14))
583 T(104)=2*TBM(X(13),X(15))
584 T(105)=4*TBM(X(14),X(15))
651 P1NEW=0
652 FOR KAU7=1 TO 105
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-576 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1927 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first minute of running is presented below. (What immediately follows is a manual copy from the computer screen.)

1 2 7 6 14
13 9 4 5 11
10 15 3 8 12
-575 -31879

1 2 7 6 14
13 9 4 5 11
10 15 3 8 12
-575 -31878

11 12 7 6 4
3 9 14 15 1
10 5 13 8 2
-575 -31859

Interpreted in accordance with line 1912 through line 1927, the output through
JJJJ=-31859 was produced during the first minute of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).

Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).

Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).

Nugent,C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1968).

Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly 18, 1-36 (1971).

Sunday, August 30, 2009

Saturday, August 29, 2009

Friday, August 28, 2009

Wednesday, August 26, 2009

Tuesday, August 25, 2009

Blog Archive