Jsun Yui Wong
The computer program listed below tries to solve the 30-department problem of Nugent, Vollmann, and Ruml (1968).
0 DEFINT A-Z
3 DEFSNG H,S,P,M
5 DIM X(66),A(66)
8 DIM HS(33,33),HR(33,33)
9 FOR IZ=1 TO 30
10 FOR JZ=1 TO 30
11 READ HR(IZ,JZ)
12 NEXT JZ
13 NEXT IZ
14 DATA 999,1,2,3,4,5,1,2,3,4,5,6,2,3,4,5,6,7,3,4,5,6,7,8,4,5,6,7,8,9
15 DATA 1,999,1,2,3,4,2,1,2,3,4,5,3,2,3,4,5,6,4,3,4,5,6,7,5,4,5,6,7,8
16 DATA 2,1,999,1,2,3,3,2,1,2,3,4,4,3,2,3,4,5,5,4,3,4,5,6,6,5,4,5,6,7
17 DATA 3,2,1,999,1,2,4,3,2,1,2,3,5,4,3,2,3,4,6,5,4,3,4,5,7,6,5,4,5,6
18 DATA 4,3,2,1,999,1,5,4,3,2,1,2,6,5,4,3,2,3,7,6,5,4,3,4,8,7,6,5,4,5
19 DATA 5,4,3,2,1,999,6,5,4,3,2,1,7,6,5,4,3,2,8,7,6,5,4,3,9,8,7,6,5,4
20 DATA 1,2,3,4,5,6,999,1,2,3,4,5,1,2,3,4,5,6,2,3,4,5,6,7,3,4,5,6,7,8
21 DATA 2,1,2,3,4,5,1,999,1,2,3,4,2,1,2,3,4,5,3,2,3,4,5,6,4,3,4,5,6,7
22 DATA 3,2,1,2,3,4,2,1,999,1,2,3,3,2,1,2,3,4,4,3,2,3,4,5,5,4,3,4,5,6
23 DATA 4,3,2,1,2,3,3,2,1,999,1,2,4,3,2,1,2,3,5,4,3,2,3,4,6,5,4,3,4,5
24 DATA 5,4,3,2,1,2,4,3,2,1,999,1,5,4,3,2,1,2,6,5,4,3,2,3,7,6,5,4,3,4
25 DATA 6,5,4,3,2,1,5,4,3,2,1,999,6,5,4,3,2,1,7,6,5,4,3,2,8,7,6,5,4,3
26 DATA 2,3,4,5,6,7,1,2,3,4,5,6,999,1,2,3,4,5,1,2,3,4,5,6,2,3,4,5,6,7
27 DATA 3,2,3,4,5,6,2,1,2,3,4,5,1,999,1,2,3,4,2,1,2,3,4,5,3,2,3,4,5,6
28 DATA 4,3,2,3,4,5,3,2,1,2,3,4,2,1,999,1,2,3,3,2,1,2,3,4,4,3,2,3,4,5
29 DATA 5,4,3,2,3,4,4,3,2,1,2,3,3,2,1,999,1,2,4,3,2,1,2,3,5,4,3,2,3,4
30 DATA 6,5,4,3,2,3,5,4,3,2,1,2,4,3,2,1,999,1,5,4,3,2,1,2,6,5,4,3,2,3
31 DATA 7,6,5,4,3,2,6,5,4,3,2,1,5,4,3,2,1,999,6,5,4,3,2,1,7,6,5,4,3,2
32 DATA 3,4,5,6,7,8,2,3,4,5,6,7,1,2,3,4,5,6,999,1,2,3,4,5,1,2,3,4,5,6
33 DATA 4,3,4,5,6,7,3,2,3,4,5,6,2,1,2,3,4,5,1,999,1,2,3,4,2,1,2,3,4,5
34 DATA 5,4,3,4,5,6,4,3,2,3,4,5,3,2,1,2,3,4,2,1,999,1,2,3,3,2,1,2,3,4
35 DATA 6,5,4,3,4,5,5,4,3,2,3,4,4,3,2,1,2,3,3,2,1,999,1,2,4,3,2,1,2,3
36 DATA 7,6,5,4,3,4,6,5,4,3,2,3,5,4,3,2,1,2,4,3,2,1,999,1,5,4,3,2,1,2
37 DATA 8,7,6,5,4,3,7,6,5,4,3,2,6,5,4,3,2,1,5,4,3,2,1,999,6,5,4,3,2,1
38 DATA 4,5,6,7,8,9,3,4,5,6,7,8,2,3,4,5,6,7,1,2,3,4,5,6,999,1,2,3,4,5
39 DATA 5,4,5,6,7,8,4,3,4,5,6,7,3,2,3,4,5,6,2,1,2,3,4,5,1,999,1,2,3,4
40 DATA 6,5,4,5,6,7,5,4,3,4,5,6,4,3,2,3,4,5,3,2,1,2,3,4,2,1,999,1,2,3
41 DATA 7,6,5,4,5,6,6,5,4,3,4,5,5,4,3,2,3,4,4,3,2,1,2,3,3,2,1,999,1,2
42 DATA 8,7,6,5,4,5,7,6,5,4,3,4,6,5,4,3,2,3,5,4,3,2,1,2,4,3,2,1,999,1
43 DATA 9,8,7,6,5,4,8,7,6,5,4,3,7,6,5,4,3,2,6,5,4,3,2,1,5,4,3,2,1,999
49 FOR IZ=1 TO 29
50 FOR JZ=IZ+1 TO 30
51 READ HS(IZ,JZ)
52 NEXT JZ
53 NEXT IZ
54 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
55 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
56 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
57 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
58 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
59 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
60 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
61 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
62 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
63 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
64 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
65 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
66 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
67 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5,4,5,1,0,1,0,5,0,2,0,0,5,1,1,0,0,3,0,2,2,0,2,0,5,0,5,2,5,10,2,2,0,0,0,6,5,3,5,0,0,5,1
68 DATA 5,1,2,10,10,4,0,0,5,0,0,0,0,5,5,1,0,5,2,1,2,10,10
69 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2
74 FOR JJJJ=-32000 TO 32000
75 RANDOMIZE JJJJ
76 M=-999999999999#
81 FOR ZI=1 TO 30
82 A(ZI)=ZI
83 NEXT ZI
126 IMAR=10+RND*10000
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 30
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*30)
224 IJM=1+FIX(RND*30)
236 X(IJL)=A(IJM):X(IJM)=A(IJL)
1631 SUMUL=0
1632 FOR IS1=1 TO 29
1634 FOR IS2=IS1+1 TO 30
1637 SUMUL=SUMUL+HS(IS1,IS2)*HR(X(IS1),X(IS2))
1638 NEXT IS2
1639 NEXT IS1
1646 P=-SUMUL
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 128
1670 NEXT I
1890 IF M>-3093 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)
1929 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its output through JJJJ=-31599 is presented below. What follows is a manual copy from the computer monitor.
18 13 19 25 1
11 10 22 8 9
28 5 3 26 30
15 24 23 16 20
7 17 29 6 4
12 27 2 14 21
-3090 -31843
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 -31599
3062 is optimal, Loiola et al. (2007). Interpreted in accordance with line 1912 through line 1929, the output above was produced in 1.5 hours of running on a personal computer with an Intel 2.66 GHz. chip and with the IBM basica/D interpreter.
References
Hillier, F. S. (1963), "Quantitative tools for plant layout analysis," J. Indust. Eng. 14, 33-40.
Loiola, E. M., N. M. M. de Abreu, P. O. Boaventur-Netto, P. Hahn, and T. Querido, " A survey for the quadratic assignment problem," European Journal of Operational Research 176, 657-690 (2007).
Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Nugent, C. E., Vollmann, T. E., and Ruml, J. (1968), "An experimental comparisons of techniques for the assignment of facilities to locations," Operations Research 16, 150-173.(1969).
