Jsun Yui Wong
"These tests suggest that LB1 is adequate for problems with up to 35 departments. For larger problems, the linear programs become too large and too difficult to solve with the currently available LP solvers" (Amaral 2009). "Our computational results suggest that this approach can routinely obtain optimal layouts for SRFLPs with up to 25 facilities in a few hours, and in several dozen hours for SRFLPs with up to 30 facilities" (Anjos and Vannelli 2008).
The computer program listed below tries to solve a case for 37 departments. Used in line 62 through line 71, the flows are from Skorin-Kapov (1990, p. 40). The department lengths are almost all the lengths on page 824 of Simmons (1969)--2, 3, 4, 5, 6, 3, 7, 4, 5, 6, 5, 4, 5, 4, 6, 5, 2, 8, ,,,, 7, 6, 3, 9. In order to have integer locations, these Simmons' lengths were multiplied by two to give the minimum centroid-to-centroid distances of line 32 through line 48 below.
The computer program below is a heuristic procedure. To mitigate this shortcoming, one can use the multi-computer method that uses a number of personal computers running simultaneously and independently. To save human labor, each computer runs a very slightly different computer program. For example, if there are three computers, one computer can run with 126 IMAR=10+RND*5000, the second can run with 126 IMAR=10+RND*6000, and the third can run with 126 IMAR=10+RND*7000. This method is illustrated below.
0 DEFINT A-Z
2 DEFSNG S,P,M,T
5 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
7 DIM TM(44,44),HR(44,44),HS(44,44)
21 FOR IW=1 TO 36
23 FOR JW=IW+1 TO 37
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
32 DATA 5,6,7,8,5,9,6,7,8,7,6,7,6,8,7,4,10,11,9,5,6,8,10,11,7,9,8,10,9,7,8,10,9,8,5,11
33 DATA 7,8,9,6,10,7,8,9,8,7,8,7,9,8,5,11,12,10,6,7,9,11,12,8,10,9,11,10,8,9,11,10,9,6,12
34 DATA 9,10,7,11,8,9,10,9,8,9,8,10,9,6,12,13,11,7,8,10,12,13,9,11,10,12,11,9,10,12,11,10,7,13
35 DATA 11,8,12,9,10,11,10,9,10,9,11,10,7,13,14,12,8,9,11,13,14,10,12,11,13,12,10,11,13,12,11,8,14
36 DATA 9,13,10,11,12,11,10,11,10,12,11,8,14,15,13,9,10,12,14,15,10,13,12,14,13,11,12,14,13,12,9,15
37 DATA 10,7,8,9,8,7,8,7,9,8,5,11,12,10,6,7,9,11,12,8,10,9,11,10,8,9,11,10,9,6,12
38 DATA 11,12,13,12,11,12,11,13,12,9,15,16,14,10,11,13,15,16,12,14,13,15,14,12,13,15,14,13,10,16
39 DATA 9,10,9,8,9,8,10,9,6,12,13,11,7,8,10,12,13,9,11,10,12,11,9,10,12,11,10,9,13,11,10,9,10,9,11,10,7,13,14,12,8,9,11,13,14,10,12,11,13,12,10,11,13,12,11,8,14
40 DATA 11,10,11,10,12,11,8,14,15,13,9,10,12,14,15,10,13,12,14,13,11,12,14,13,12,9,15,9,10,9,11,10,7,13,14,12,8,9,11,13,14,10,12,11,13,12,10,11,13,12,11,8,14
41 DATA 9,8,10,9,6,12,13,11,7,8,10,12,13,9,11,10,12,11,9,10,12,11,10,7,13,9,11,10,7,13,14,12,8,9,11,13,14,10,12,11,13,12,10,11,13,12,11,8,14
42 DATA 10,9,6,12,13,11,7,8,10,12,13,9,11,10,12,11,9,10,12,11,10,7,13,11,8,14,15,13,9,10,12,14,15,11,13,12,14,13,11,12,14,13,12,9,15
43 DATA 7,13,14,12,8,9,11,13,14,10,12,11,13,12,10,11,13,12,11,8,14,10,11,9,5,6,8,10,11,7,9,8,10,9,7,8,10,9,8,5,11
44 DATA 17,15,11,12,14,16,17,13,15,14,16,15,13,14,16,15,14,11,17,16,12,13,15,17,18,14,16,15,17,16,14,15,17,16,15,12,18
45 DATA 10,11,13,15,16,12,14,13,15,14,12,13,15,14,13,10,16,7,9,11,12,8,10,9,11,10,8,9,11,10,9,6,12
46 DATA 10,12,13,9,11,10,12,11,9,10,12,11,10,9,13,14,15,11,13,12,14,13,11,12,14,13,12,9,15,17,13,15,14,16,15,13,14,16,15,14,11,17
47 DATA 14,16,15,17,16,14,15,17,16,15,12,18,12,11,13,12,10,11,13,12,11,8,14,13,15,14,12,13,15,14,13,10,16,14,13,11,12,14,13,12,9,15
48 DATA 15,13,14,16,15,14,11,17,12,13,15,14,13,10,16,11,13,12,11,8,14,14,13,12,9,15,15,14,11,17,13,10,16,9,15,12
50 FOR IZ=1 TO 36
51 FOR JZ=IZ+1 TO 37
52 READ HS(IZ,JZ)
53 NEXT JZ
54 NEXT IZ
62 DATA 2,10,5,4,1,5,6,5,0,2,0,0,1,2,5,0,5,0,2,5,5,0,10,0,1,4,2,0,0,0,2,0,5,5,0,10,1,0,5,1,0,0,0,2,1,0,5,10,0,1,0,10,10,0,2,1,1,0,0,3,5,10,0,5,0,2,1,1,3,10
63 DATA 5,0,1,5,10,0,0,1,0,5,0,3,2,5,1,5,0,1,1,1,5,1,2,2,0,1,1,5,2,6,1,1,0,10,5,0,1,0,0,10,2,1,2,5,5,5,5,0,2,2,6,5,5,0,5,2,1,0,0,1,2,3,2,10,5,4,0,0,1,6
64 DATA 1,1,0,0,6,0,0,2,2,2,3,5,0,2,2,2,0,5,5,5,0,1,5,0,4,2,2,1,5,6,0,5,1,5,1,0,0,0,1,0,0,0,1,0,0,1,2,5,5,1,2,1,10,0,0,0,2,5,0,10,5,0,5,4,10,10,2,0,2,5
65 DATA 10,0,4,5,6,4,0,2,1,2,1,2,2,0,2,3,2,5,0,0,0,0,1,5,2,0,0,2,2,0,2,0,0,4,0,0,2,5,3,2,2,5,2,2,2,5,0,2,5,2,5,0,5,4,2,10,5,0,2,2,1,2,0,0,6,1,5,0,0,0
66 DATA 0,5,10,10,3,5,1,2,1,2,5,3,2,5,5,5,10,0,0,1,2,4,0,0,5,0,3,2,5,0,0,1,5,2,0,5,2,5,0,2,1,2,0,2,0,5,2,5,1,4,0,1,10,3,5,5,0,5,2,0,0,1,0,0,0,10,2,4,5,0
67 DATA 0,0,0,1,10,5,1,1,5,5,2,1,5,10,5,3,0,0,0,3,0,5,6,0,5,2,1,1,5,2,1,0,0,10,5,5,2,2,5,1,10,2,5,1,5,5,2,2,0,0,1,2,0,5,2,4,5,10,4,0,10,2,10,0,6,0,1,2,0,2
68 DATA 0,0,0,5,5,2,5,0,5,1,5,1,5,0,5,2,0,5,5,2,0,4,0,0,0,0,0,2,2,0,0,5,2,0,5,1,0,0,5,1,1,0,3,5,0,2,1,5,1,5,6,0,3,5,0,5,5,5,0,0,2,2,6,10,0,2,0,2,2,10
69 DATA 2,0,5,1,0,1,0,0,0,3,2,10,4,5,5,2,5,1,1,2,5,0,0,3,1,2,0,2,10,10,5,2,1,2,1,0,10,2,5,0,0,2,0,4,4,1,1,0,5,1,5,10,1,0,0,5,5,5,2,5,2,10,0,2,0,2,4,0,2,5
70 DATA 5,2,0,2,0,2,0,5,2,0,2,1,5,10,6,2,10,0,2,0,0,5,3,5,2,0,10,10,1,4,0,5,4,1,0,2,2,1,1,0,2,10,5,0,1,5,0,0,10,2,5,2,0,2,3,0,5,0,3,2,0,3,2,5,0,10,2,0,5,5
71 DATA 0,0,0,3,6,5,0,5,1,0,5,4,10,5,1,2,0,5,2,0,2,2,4,1,2,0,2,5,0,0,2,1,0,5,2,0
81 FOR JJJJ=-32000 TO 32000
82 RANDOMIZE JJJJ
83 M=-9999999!
85 FOR II=1 TO 37
88 A(II)=RND*499
89 NEXT II
126 IMAR=10+RND*5000
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 37
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*37)
234 X(IJL)=RND*499
533 FOR IX=1 TO 36
534 FOR JX=IX+1 TO 37
543 IF ABS(X(IX)-X(JX))-HR(IX,JX)<-.0001 THEN TM(IX,JX)=99999! ELSE TM(IX,JX)=0
545 NEXT JX
547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 36
1614 FOR IR2=IR1+1 TO 37
1616 SUMTL=SUMTL+TM(IR1,IR2)
1617 NEXT IR2
1619 NEXT IR1
1631 SUMUL=0
1632 FOR IS1=1 TO 36
1634 FOR IS2=IS1+1 TO 37
1636 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1637 NEXT IS2
1639 NEXT IS1
1645 P=-SUMUL-SUMTL
1647 PZZZ=-SUMUL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 37
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PZZZ
1666 GOTO 128
1670 NEXT I
1890 IF M>-220000! 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)
1918 PRINT A(31),A(32),A(33),A(34),A(35)
1924 PRINT A(36),A(37),MM,M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solution produced during the first 20 hours of running is presented below.
192 329 153 122 367
257 93 228 60 163
70 216 185 250 17
175 222 340 397 239
146 322 266 45 287
313 415 302 135 380
80 29 109 4 354
275 203 -208555 -208555 -31937
The best candidate solution from the computer running with 126 IMAR=10+RND*6000 is as follows:
242 179 248 114 392
347 406 354 279 152
316 270 58 300 290
171 325 421 197 259
307 162 234 137 462
211 89 103 366 46
124 380 74 336 222
185 438 -210411 -210411 -31980
The best candidate solution from the computer running with 126 IMAR=10+RND*7000 is as follows:
275 219 234 294 244
334 97 341 326 159
210 262 148 254 137
70 167 354 56 39
270 226 380 413 430
174 82 199 123 186
110 368 313 25 283
302 395 -204529 -204529 -31902
Interpreted in accordance with line 1912 through line 1924, these three candidate solutions were produced during the first 20 hours of simultaneous running on three personal computers each with speed of about 2.66 GHz. and with the IBM basica/D interpreter, which is not a compiler.
References
Amaral, A. R. S., "A New Lower Bound for the Single Row Facility Layout Problem," Discrete Applied Mathematics 157, 183-190 (2009).
Anjos, M. F., and A. Vannelli, "Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes," INFORMS Journal on Computing 20, 611-617 (2008).
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.
Simmons, D. M., "One-Dimensional Space Allocation: an Ordering Algorithm," Operations Research 17, 812-826 (1969).
Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing 2, 33-45 (1990).
