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 with forty departments. Used in line 62 through line 72, 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, 9, 7, 3, 4, 6, 8, 9, 5, 7, 6, 8, 7, 5, 6, 8, 7, 6, 3, 9, 4, 2, 6. 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 49 below.
The computer program below is a heuristic procedure. To mitigate its 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. Among these three computer programs only line 126 varies. This multi-computer 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 39
23 FOR JW=IW+1 TO 40
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, 6,4,8
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, 7,5,9
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, 8,6,10
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, 9,7,11
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, 10,8,12
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, 7,5,9
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, 11,9,13
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, 8,6,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
40 DATA 9,7,11, 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, 10,8,12, 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,7,11, 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, 8,6,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
42 DATA 9,7,11, 10,9,6,12,13,11,7,8,10,12,13,9,11,10,12,11,9,10,12,11,10,7,13, 8,6,10, 11,8,14,15,13,9,10,12,14,15,11,13,12,14,13,11,12,14,13,12,9,15
43 DATA 10,8,12, 7,13,14,12,8,9,11,13,14,10,12,11,13,12,10,11,13,12,11,8,14, 9,7,11, 10,11,9,5,6,8,10,11,7,9,8,10,9,7,8,10,9,8,5,11
44 DATA 6,4,8, 17,15,11,12,14,16,17,13,15,14,16,15,13,14,16,15,14,11,17, 12,10,14, 16,12,13,15,17,18,14,16,15,17,16,14,15,17,16,15,12,18
45 DATA 13,11,15, 10,11,13,15,16,12,14,13,15,14,12,13,15,14,13,10,16, 11,9,13, 7,9,11,12,8,10,9,11,10,8,9,11,10,9,6,12
46 DATA 7,5,9, 10,12,13,9,11,10,12,11,9,10,12,11,10,9,13, 8,6,10, 14,15,11,13,12,14,13,11,12,14,13,12,9,15, 10,8,12, 17,13,15,14,16,15,13,14,16,15,14,11,17
47 DATA 12,10,14, 14,16,15,17,16,14,15,17,16,15,12,18, 13,11,15, 12,11,13,12,10,11,13,12,11,8,14, 9,7,11, 13,15,14,12,13,15,14,13,10,16, 11,9,13, 14,13,11,12,14,13,12,9,15
48 DATA 10,8,12, 15,13,14,16,15,14,11,17, 12,10,14, 12,13,15,14,13,10,16, 11,9,13, 11,13,12,11,8,14, 9,7,11, 14,13,12,9,15, 10,8,12, 15,14,11,17, 12,10,14, 13,10,16, 11,9,13, 9,15, 10,8,12, 12
49 DATA 7,5,9,13,11,15,6,10,8
50 FOR IZ=1 TO 39
51 FOR JZ=IZ+1 TO 40
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, 10,0,0, 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,10,0, 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, 10,5,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, 2,10,3, 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, 2,2,0, 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, 4,5,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,1, 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, 2,0,5, 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, 0,0,10, 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, 1,5,2, 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, 0,5,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, 5,5,1, 0,0,0,3,0,5,6,0,5,2,1,1,5,2,1,0,0,10,5,5,2,2,5,1, 1,0,1, 10,2,5,1,5,5,2,2,0,0,1,2,0,5,2,4,5,10,4,0,10,2,10, 1,2,5, 0,6,0,1,2,0,2
68 DATA 0,0,0,5,5,2,5,0,5,1,5,1,5,0,5, 5,2,10, 2,0,5,5,2,0,4,0,0,0,0,0,2,2,0,0,5,2,0,5,1, 0,5,0, 0,0,5,1,1,0,3,5,0,2,1,5,1,5,6,0,3,5,0,5, 0,0,5, 5,5,0,0,2,2,6,10,0,2,0,2,2,10
69 DATA 2,0,5,1,0, 6,3,4, 1,0,0,0,3,2,10,4,5,5,2,5,1,1,2,5,0,0, 10,3,2, 3,1,2,0,2,10,10,5,2,1,2,1,0,10,2,5,0, 5,0,4, 0,2,0,4,4,1,1,0,5,1,5,10,1,0,0,5, 10,10,4, 5,5,2,5,2,10,0,2,0,2,4,0,2,5
70 DATA 5, 2,2,2, 2,0,2,0,2,0,5,2,0,2,1,5,10,6, 1,5,2, 2,10,0,2,0,0,5,3,5,2,0,10,10, 3,0,2, 1,4,0,5,4,1,0,2,2,1,1,0, 4,0,3, 2,10,5,0,1,5,0,0,10,2,5, 0,0,0, 2,0,2,3,0,5,0,3,2,0, 2,10,0, 3,2,5,0,10,2,0,5,5
71 DATA 2,1,0, 0,0,0,3,6,5,0,5, 2,1,5, 1,0,5,4,10,5,1, 0,10,5, 2,0,5,2,0,2, 0,10,3, 2,4,1,2,0, 0,2,2, 2,5,0,0, 0,2,2, 2,1,0, 10,0,0, 5,2, 0,2,1, 0
72 DATA 2,5,0,10,10,5,2,10,1
81 FOR JJJJ=-32000 TO 32000
82 RANDOMIZE JJJJ
83 M=-9999999!
85 FOR II=1 TO 40
88 A(II)=RND*499
89 NEXT II
126 IMAR=10+RND*5000
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 40
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*40)
234 X(IJL)=RND*499
333 IF RND<.05 THEN X(IJL)=A(IJL)+1
533 FOR IX=1 TO 39
534 FOR JX=IX+1 TO 40
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 39
1614 FOR IR2=IR1+1 TO 40
1616 SUMTL=SUMTL+TM(IR1,IR2)
1617 NEXT IR2
1619 NEXT IR1
1631 SUMUL=0
1632 FOR IS1=1 TO 39
1634 FOR IS2=IS1+1 TO 40
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 40
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PZZZ
1666 GOTO 128
1670 NEXT I
1890 IF M>-270000! 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)
1919 PRINT A(36),A(37),A(38),A(39),A(40)
1924 PRINT MM,M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, and the top-two candidate solutions produced during the first 20 hours of running are presented immediately below. What follows is a manual copy from the computer monitor.
232 210 318 74 351
311 241 163 124 85
443 252 114 133 143
337 222 7 100 22
216 171 377 300 394
154 364 35 426 410
327 47 61 267 201
227 283 191 258 181
-262743 -262743 -31883
223 244 165 258 27
250 328 53 340 416
198 305 350 267 295
150 311 233 212 362
186 141 93 129 461
116 445 81 430 176
376 277 41 401 105
158 66 317 191 387
-264139 -264139 -31873
One can check the solution/result at JJJJ=-31883 to see whether there is a gap between any two adjacent facilities. If there is, then joining the two adjacent facilities together makes the actual cost for this order to be less than 262743.
The best candidate solution from the computer running with 126 IMAR=10+RND*6000 is as follows:
224 247 230 156 378
116 305 123 84 256
293 368 437 321 55
267 315 280 355 465
201 165 43 29 213
330 449 95 143 410
341 175 189 393 423
237 70 131 242 107
-268361 -268361 -31858
The best candidate solution from the computer running with 126 IMAR=10+RND*7000 is as follows:
179 334 118 326 157
139 23 224 247 396
291 98 352 341 108
301 183 428 366 443
205 272 70 56 39
147 313 381 8 235
281 258 412 129 214
166 85 173 266 196
-267367 -267367 -31851
Interpreted in accordance with line 1912 through line 1924, these four 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).
