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)
6 DIM TBM(11,11)
11 TBM(1,1)=999:TBM(1,2)=28:TBM(1,3)=33:TBM(1,4)=22:TBM(1,5)=20
12 TBM(2,1)=28:TBM(2,2)=999:TBM(2,3)=27:TBM(2,4)=40:TBM(2,5)=25
13 TBM(3,1)=33:TBM(3,2)=27:TBM(3,3)=999:TBM(3,4)=30:TBM(3,5)=15
14 TBM(4,1)=22:TBM(4,2)=40:TBM(4,3)=30:TBM(4,4)=999:TBM(4,5)=18
15 TBM(5,1)=20:TBM(5,2)=25:TBM(5,3)=15:TBM(5,4)=18:TBM(5,5)=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
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
330 IJM=1+FIX(RND*5)
331 IJN=1+FIX(RND*5)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=10*TBM(X(1),X(2))
402 T(2)=3*TBM(X(1),X(3))
403 T(3)=1*TBM(X(1),X(4))
404 T(4)=15*TBM(X(1),X(5))
405 T(5)=6*TBM(X(2),X(3))
406 T(6)=8*TBM(X(2),X(4))
407 T(7)=4*TBM(X(2),X(5))
408 T(8)=0*TBM(X(3),X(4))
409 T(9)=10*TBM(X(3),X(5))
410 T(10)=3*TBM(X(4),X(5))
1589 P=-T(1)-T(2)-T(3)-T(4)-T(5)-T(6)-T(7)-T(8)-T(9)-T(10)
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>-1348 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.)
4 1 3 2 5
-1347 -32000
4 1 3 2 5
-1347 -31998
4 1 3 2 5
-1347 -31993
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31993 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
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," OperationalResearch 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).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
