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 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 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*7000
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
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 best candidate solution produced during the first 20 hours of running is presented immediately below.
221 366 309 180 415
206 332 271 214 229
170 301 440 263 59
198 277 454 471 100
290 283 356 249 43
405 428 319 85 143
345 394 128 158 113
238 378 189 295 71
-264696 -264696 -31976
The best candidate solution from the computer running with 126 IMAR=10+RND*6000 is as follows:
189 256 415 138 241
250 404 423 19 93
348 339 128 83 175
358 307 161 326 434
184 46 117 32 388
230 298 105 371 284
148 56 70 449 271
262 212 313 223 197
-268168 -268168 -31982
The computer running with 126 IMAR=10+RND*5000 produced no output during the first twenty hours.
Interpreted in accordance with line 1912 through line 1924, these two 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).
