Jsun Yui Wong
The computer program listed below tries to solve the nineteen-facility problem of Elshafei [1].
0 DEFINT A-Z
3 DEFSNG H,S,P,M
5 DIM X(66),A(66)
8 DIM HS(33,33),HR(22,22)
11 FOR IZ=1 TO 19
14 FOR JZ=1 TO 19
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
24 DATA 999,12,36,28,52,44,110,126,94,63,130,102,65,98,132,132,126,120,126
25 DATA 12,999,24,75,82,75,108,70,124,86,93,106,58,124,161,161,70,64,70
26 DATA 36,24,999,47,71,47,110,73,126,71,95,110,46,127,163,163,73,67,73
27 DATA 28,75,47,999,42,34,148,111,160,52,94,148,49,117,104,109,111,105,111
28 DATA 52,82,71,42,999,42,125,136,102,22,73,125,32,94,130,130,136,130,136
29 DATA 44,75,47,34,42,999,148,111,162,52,96,148,49,117,152,152,111,105,111
30 DATA 110,108,110,148,125,148,999,46,46,136,47,30,108,51,79,79,46,47,41
31 DATA 126,70,73,111,136,111,46,999,69,141,63,46,119,68,121,121,27,24,36
32 DATA 94,124,126,160,102,162,46,69,999,102,34,45,84,23,80,80,69,64,51
33 DATA 63,86,71,52,22,52,136,141,102,999,64,118,29,95,131,131,141,135,141
34 DATA 130,93,95,94,73,96,47,63,34,64,999,47,56,54,94,94,63,46,24
35 DATA 102,106,110,148,125,148,30,46,45,118,47,999,100,51,89,89,46,40,36
36 DATA 65,58,46,49,32,49,108,119,84,29,56,100,999,77,113,113,119,113,119
37 DATA 98,124,127,117,94,117,51,68,23,95,54,51,77,999,79,79,68,62,51
38 DATA 132,161,163,104,130,152,79,121,80,131,94,89,113,79,999,10,113,107,119
39 DATA 132,161,163,109,130,152,79,121,80,131,94,89,113,79,10,999,113,107,119
40 DATA 126,70,73,111,136,111,46,27,69,141,63,46,119,68,113,113,999,6,24
41 DATA 120,64,67,105,130,105,47,24,64,135,46,40,113,62,107,107,6,999,12
42 DATA 126,70,73,111,136,111,41,36,51,141,24,36,119,51,119,119,24,12,999
49 FOR IZ=1 TO 18
50 FOR JZ=IZ+1 TO 19
51 READ HS(IZ,JZ)
52 NEXT JZ
53 NEXT IZ
54 DATA 76687,0,415,545,819,135,1368,819,5630,0,3432,9082,1503,0,0,13732,1368,1783
55 DATA 40951,4118,5767,2055,1917,2746,1097,5712,0,0,0,268,0,1373,268,0,0
56 DATA 3848,2524,3213,2072,4225,566,0,0,404,9372,0,972,0,13538,1368,0
57 DATA 256,0,0,0,0,829,128,0,0,0,0,0,0,0,0
58 DATA 0,0,0,47,1655,287,0,42,0,0,0,226,0,0
59 DATA 0,0,0,926,161,0,0,0,0,0,0,0,0
60 DATA 0,196,1538,196,0,0,0,0,0,0,0,0
61 DATA 0,0,301,0,0,0,0,0,0,0,0
62 DATA 1954,418,0,0,0,0,0,0,0,0
63 DATA 0,282,0,0,0,0,0,0,0
64 DATA 1686,0,0,0,0,226,0,0
65 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
66 DATA 99999,0,0,0,0,0,0,0,0,0
74 FOR JJJJ=-32000 TO 32000
75 RANDOMIZE JJJJ
76 M=-999999999#
81 FOR ZI=1 TO 19
82 A(ZI)=ZI
83 NEXT ZI
126 IMAR=10+RND*1000
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 60
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*19)
224 IJM=1+FIX(RND*19)
236 X(IJL)=A(IJM):X(IJM)=A(IJL)
1631 SUMUL=0
1632 FOR IS1=1 TO 18
1634 FOR IS2=IS1+1 TO 19
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 19
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-8611111! 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)
1929 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced during the first five minutes of running is presented below. What follows is a manual copy from the computer monitor.
17 18 19 11 12
9 3 14 1 2
10 13 7 5 15
16 8 6 4
-8606274 -31881
17 18 19 11 12
9 3 14 1 2
10 13 7 5 15
16 8 6 4
-8606274 -31855
17 18 19 11 12
9 3 14 1 2
10 13 7 5 15
16 8 6 4
-8606274 -31826
17 18 19 11 12
9 3 14 1 2
10 13 7 5 15
16 8 6 4
-8606274 -31762
One notes that this 8606274 corresponds to the objective function value of 17212548 of Mautor and Roucairol [2, p. 291]. Interpreted in accordance with line 1912 through line 1929, the output above was produced during the first five minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
[1] A. Elshafei, "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28 (1977) 167-179.
[2] T. Mautor and C. Roucairol, "A New Exact Algorithm for the Solution of Quadratic Assignment Problems," Discrete Applied Mathematics 55 (1994) 281-293.
[3] 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.
