Jsun Yui Wong
The computer program listed below seeks to solve the example in Land (1963).
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)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
51 A(1)=0:A(6)=0
52 A(2)=12:A(7)=2
53 A(3)=10.01:A(8)=10
54 A(4)=25:A(9)=10
55 A(5)=0:A(10)=28
126 IMAR=10+FIX(RND*0)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*5)
331 IJN=1+FIX(RND*5)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
335 X(IJM+5)=A(IJN+5):X(IJN+5)=A(IJM+5)
501 B(1)=ABS(X(1)-X(2))+ABS(X(6)-X(7))
502 B(2)=ABS(X(1)-X(3))+ABS(X(6)-X(8))
503 B(3)=ABS(X(1)-X(4))+ABS(X(6)-X(9))
504 B(4)=ABS(X(1)-X(5))+ABS(X(6)-X(10))
505 B(5)=ABS(X(2)-X(3))+ABS(X(7)-X(8))
506 B(6)=ABS(X(2)-X(4))+ABS(X(7)-X(9))
507 B(7)=ABS(X(2)-X(5))+ABS(X(7)-X(10))
508 B(8)=ABS(X(3)-X(4))+ABS(X(8)-X(9))
509 B(9)=ABS(X(3)-X(5))+ABS(X(8)-X(10))
510 B(10)=ABS(X(4)-X(5))+ABS(X(9)-X(10))
1111 FOR IAA=1 TO 10
1112 IF B(IAA)=9.99 THEN B(IAA)=18
1113 NEXT IAA
1121 FOR IAA=1 TO 10
1122 IF B(IAA)=14 THEN B(IAA)=22
1123 NEXT IAA
1131 FOR IAA=1 TO 10
1132 IF B(IAA)=21 THEN B(IAA)=30
1133 NEXT IAA
1141 FOR IAA=1 TO 10
1142 IF B(IAA)=35 THEN B(IAA)=33
1143 NEXT IAA
1151 FOR IAA=1 TO 10
1152 IF B(IAA)=38 THEN B(IAA)=40
1153 NEXT IAA
1161 FOR IAA=1 TO 10
1162 IF B(IAA)=43 THEN B(IAA)=27
1163 NEXT IAA
1171 FOR IAA=1 TO 10
1172 IF B(IAA)=28.01 THEN B(IAA)=25
1173 NEXT IAA
1380 PH=-10*B(1)-3*B(2)-1*B(3)-15*B(4)-6*B(5)-8*B(6)
1381 PI=-4*B(7)-0*B(8)-10*B(9)-3*B(10)
1588 P=PH+PI
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-1350 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)
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.)
12 0 25 0 10.01
2 0 10 28 10
-1346.94 -31995
12 0 25 0 10.01
2 0 10 28 10
-1346.94 -31993
12 0 25 0 10.01
2 0 10 28 10
-1346.94 -31989
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31989 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.
References
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).
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
