A Heuristic Nonlinear Integer Solver Applied to a Three-Dimensional Quadratic Assignment Problem of Size 8

Jsun Yui Wong

The computer program listed below tries to solve a problem that is a modification of the 8-department problem of Nugent, Vollmann, and Ruml (1968). With L01 standing for location 01, the plant shape is as follows:

L02
LO4 L05 L06 L07 L08
L03

And L01 is directly behind L04; the third dimension has L01 only.

The distance between L01 and L04 is one, the (rectangular) distance between L01 and L02 is two, the distance between L01 and L03 is two, the distance between L01 and L05 is two, the distance between L04 and L05 is one, the distance between L05 and L06 is one, the distance between between L06 and L07 is one, and the distance between L07 and L08 is one.

These rectangular distances are used in line 24 through line 31. The flows are shown in line 54 through line 60; these flows have been obtained from Nugent et al. (1968).

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 8
14 FOR JZ=1 TO 8
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
24 DATA 999,2,2,1,2,3,4,5
25 DATA 2,999,2,1,2,3,4,5
26 DATA 2,2,999,1,2,3,4,5
27 DATA 1,1,1,999,1,2,3,4
28 DATA 2,2,2,1,999,1,2,3
29 DATA 3,3,3,2,1,999,1,2
30 DATA 4,4,4,3,2,1,999,1
31 DATA 5,5,5,4,3,2,1,999
49 FOR IZ=1 TO 7
50 FOR JZ=IZ+1 TO 8
51 READ HS(IZ,JZ)
52 NEXT JZ
53 NEXT IZ
54 DATA 5,2,4,1,0,0,6
55 DATA 3,0,2,2,2,0
56 DATA 0,0,0,0,5
57 DATA 5,2,2,10
58 DATA 10,0,0
59 DATA 5,1
60 DATA 10
74 FOR JJJJ=-32000 TO 32000
75 RANDOMIZE JJJJ
76 M=-999999999999#
81 FOR ZI=1 TO 8
82 A(ZI)=ZI
83 NEXT ZI
126 IMAR=10+RND*1
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 8
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*8)
224 IJM=1+FIX(RND*8)
236 X(IJL)=A(IJM):X(IJM)=A(IJL)
1631 SUMUL=0
1632 FOR IS1=1 TO 7
1634 FOR IS2=IS1+1 TO 8
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 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-139 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1929 PRINT A(6),A(7),A(8),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=-31936 is presented below.

2 3 1 6 8
7 5 4 -137 -32000

1 2 3 5 8
7 6 4 -137 -31976

1 2 3 6 8
7 5 4 -137 -31960

1 2 3 5 8
7 6 4 -137 -31936

Interpreted in accordance with line 1912 through line 1929, the output above was obtained in about two seconds on a personal computer with speed of 2.66 GHz. and with the IBM basica/D interpreter.

References

Hillier, F. S., "Quantitative Tools for Plant Layout Analysis," Journal of Industrial Engineering, 14, 1 (1963), 33-40.

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., R. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research, 16 (1968), 150-173.

Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing, 2 (1990), 33-45.

A Heuristic Nonlinear Integer Programming Solver Applied to a Thirty-Facility/Department Quadratic Assignment Problem, Second Edition

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=-28046 is presented below; some candidate solutions are presented with their line 1912 through 1929 while the others are presented with their line 1929 only.

-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

-3088 -31452

-3091 -31433

-3085 -31213

-3085 -30681

-3088 -30534

-3092 -30347

-3073 -30244

-3081 -30065

-3076 -29935

17 2 27 26 6
4 15 16 9 10
22 5 3 25 30
21 18 29 14 19
1 23 24 11 13
12 28 7 8 20
-3065 -29472

-3089 -29423

17 26 3 7 30
28 15 16 21 22
10 29 27 2 6
9 18 5 14 1
25 11 12 23 13
24 4 19 20 8
-3062 -29328

-3091 -28884

-3072 -28767

-3090 -28733

-3088 -28630

-3087 -28591

-3092 -28518

-3088 -28509

-3083 -28396

-3092 -28379

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 -28146

-3078 -28071

-3092 -28046

3062 is optimal, Loiola et al. (2007). Interpreted in accordance with line 1912 through line 1929, the output through JJJJ=-28046 took fifteen 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. Boaventura-Netto, P. Hahn, and T. Querido
(2007), "A survey for the quadratic assignment problem," European Journal of Operational Research 176, 657-690.

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., T. E. Vollmann, and J. Ruml (1968), "An experimental comparisons of techniques for the assignment of facilities to locations," Operations Research 16, 150-173.

A Heuristic Nonlinear Integer Programming Solver Applied to a Thirty-Facility/Department Quadratic Assignment Problem

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).

A Heuristic Nonlinear Integer Programming Solver Illustrated

Jsun Yui Wong

The computer program listed below seeks to solve the 12-department problem in Hillier (1963) and in 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(22,22)
11 FOR IZ=1 TO 12
14 FOR JZ=1 TO 12
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
24 DATA 999,1,2,3,1,2,3,4,2,3,4,5
25 DATA 1,999,1,2,2,1,2,3,3,2,3,4
26 DATA 2,1,999,1,3,2,1,2,4,3,2,3
27 DATA 3,2,1,999,4,3,2,1,5,4,3,2
28 DATA 1,2,3,4,999,1,2,3,1,2,3,4
29 DATA 2,1,2,3,1,999,1,2,2,1,2,3
30 DATA 3,2,1,2,2,1,999,1,3,2,1,2
31 DATA 4,3,2,1,3,2,1,999,4,3,2,1
32 DATA 2,3,4,5,1,2,3,4,999,1,2,3
33 DATA 3,2,3,4,2,1,2,3,1,999,1,2
34 DATA 4,3,2,3,3,2,1,2,2,1,999,1
35 DATA 5,4,3,2,4,3,2,1,3,2,1,999
49 FOR IZ=1 TO 11
50 FOR JZ=IZ+1 TO 12
51 READ HS(IZ,JZ)
52 NEXT JZ
53 NEXT IZ
54 DATA 5,2,4,1,0,0,6,2,1,1,1
55 DATA 3,0,2,2,2,0,4,5,0,0
56 DATA 0,0,0,0,5,5,2,2,2
57 DATA 5,2,2,10,0,0,5,5
58 DATA 10,0,0,0,5,1,1
59 DATA 5,1,1,5,4,0
60 DATA 10,5,2,3,3
61 DATA 0,0,5,0
62 DATA 0,10,10
63 DATA 5,0
64 DATA 2
74 FOR JJJJ=-32000 TO 32000
75 RANDOMIZE JJJJ
76 M=-999999999999#
81 FOR ZI=1 TO 12
82 A(ZI)=ZI
83 NEXT ZI
126 IMAR=10+RND*500
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 12
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*12)
224 IJM=1+FIX(RND*12)
236 X(IJL)=A(IJM):X(IJM)=A(IJL)
1631 SUMUL=0
1632 FOR IS1=1 TO 11
1634 FOR IS2=IS1+1 TO 12
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 12
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-290 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)
1929 PRINT M,JJJJ
1999 NEXT JJJJ

The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced during the first four minutes of running is presented below. What follows is a manual copy from the computer monitor.

5 1 9 8 4
3 11 7 10 2
6 12
-289 -31497

5 1 9 8 4
3 11 7 10 2
6 12
-289 -31472

5 1 9 8 4
3 11 7 10 2
6 12
-289 -31282

5 1 9 8 4
3 11 7 10 2
6 12
-289 -30926

5 9 1 8 12
11 3 7 2 10
6 4
-289 -30737

8 4 12 5 1
2 10 6 11 3
7 9
-289 -30390

289 is optimal. Interpreted in accordance with line 1912 through line 1929, the output above was produced during the first four minutes of running on a personal computer with speed of 2.66 GHz. and with the IBM basica/D interpreter, which is not a compiler.

References

Hillier, F. S. (1963), "Quantitative tools for plant layout analysis," J. Indust. Eng. 14, 33-40.

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).

A Heuristic Nonlinear Integer Programming Solver Applied to Hospital Layout

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.

A Heuristic Nonlinear Integer Programming Solver Applied to a Thirty-Department/Facility Quadratic Assignment Problem

Jsun Yui Wong

The computer program listed below tries to solve the thirty-department/facility problem of Nugent, Vollmann, and Ruml (1968).

0 DEFINT A-Z
5 DIM X(66),A(66)
8 DIM HS(33,33)
41 FOR IZ=1 TO 29
43 FOR JZ=IZ+1 TO 30
46 READ HS(IZ,JZ)
48 NEXT JZ
49 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=-32000
77 A(1)=0:A(31)=0
78 A(2)=1:A(32)=0
79 A(3)=2:A(33)=0
80 A(4)=3:A(34)=0
81 A(5)=4:A(35)=0
82 A(6)=5:A(36)=0
83 A(7)=0:A(37)=1
84 A(8)=1:A(38)=1
85 A(9)=2:A(39)=1
86 A(10)=3:A(40)=1
87 A(11)=4:A(41)=1
88 A(12)=5:A(42)=1
89 A(13)=0:A(43)=2
90 A(14)=1:A(44)=2
91 A(15)=2:A(45)=2
92 A(16)=3:A(46)=2
93 A(17)=4:A(47)=2
94 A(18)=5:A(48)=2
95 A(19)=0:A(49)=3
96 A(20)=1:A(50)=3
97 A(21)=2:A(51)=3
98 A(22)=3:A(52)=3
99 A(23)=4:A(53)=3
100 A(24)=5:A(54)=3
101 A(25)=0:A(55)=4
102 A(26)=1:A(56)=4
103 A(27)=2:A(57)=4
104 A(28)=3:A(58)=4
105 A(29)=4:A(59)=4
106 A(30)=5:A(60)=4
126 IMAR=10+RND*10000
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*30)
224 IJM=1+FIX(RND*30)
236 X(IJL)=A(IJM):X(IJM)=A(IJL):X(IJL+30)=A(IJM+30):X(IJM+30)=A(IJL+30)
1631 SUMUL=0
1632 FOR IS1=1 TO 29
1634 FOR IS2=IS1+1 TO 30
1636 SUMUL=SUMUL+HS(IS1,IS2)*(ABS(X(IS1)-X(IS2))+ABS(X(IS1+30)-X(IS2+30)))
1637 NEXT IS2
1639 NEXT IS1
1646 P=-SUMUL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 60
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-3070 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)
1920 PRINT A(41),A(42),A(43),A(44),A(45)
1921 PRINT A(46),A(47),A(48),A(49),A(50)
1922 PRINT A(51),A(52),A(53),A(54),A(55)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1929 PRINT M,JJJJ
1999 NEXT JJJJ

The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced during the first five hours of running is presented below. What follows is a manual copy from the computer monitor.

4 1 2 0 5
3 2 3 2 3
3 4 2 1 5
2 5 4 1 0
0 4 5 4 0
5 3 0 1 1
2 0 4 3 0
0 2 2 1 1
3 0 0 4 4
3 2 4 2 4
0 3 3 1 2
1 4 1 1 3
-3062 -31599

3062 is optimal. Interpreted in accordance with line 1912 through line 1929, the output above was produced during the first five hours of running on a personal computer with speed of 2.66 GHz. and with the IBM basica/D interpreter, which is not a compiler.

References

Hillier, F. S. (1963), "Quantitative tools for plant layout analysis," J. Indust. Eng. 14, 33-40.

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).

A Heuristic Nonlinear Integer Programming Solver Applied to a Quadratic Assignment Problem

Jsun Yui Wong

The computer program listed below tries to solve the 12-department problem in Hillier (1963) and in Nugent, Vollmann, and Ruml (1968).

0 DEFINT A-Z
3 DEFSNG M,P,S,T
5 DIM X(66),A(66)
6 DIM TM(24,24),HR(24,24),HS(24,24)
41 FOR IZ=1 TO 11
43 FOR JZ=IZ+1 TO 12
46 READ HS(IZ,JZ)
48 NEXT JZ
49 NEXT IZ
53 DATA 5,2,4,1,0,0,6,2,1,1,1,3,0,2,2,2,0,4,5,0,0,0,0,0,0,5,5,2,2,2,5,2,2,10,0,0,5,5,10,0,0,0,5,1,1,5,1,1,5,4,0,10,5,2,3,3,0,0,5,0,0,10,10,5,0,2
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-999999!
77 A(1)=0:A(13)=0
78 A(2)=1:A(14)=0
79 A(3)=2:A(15)=0
80 A(4)=3:A(16)=0
81 A(5)=0:A(17)=1
82 A(6)=1:A(18)=1
83 A(7)=2:A(19)=1
84 A(8)=3:A(20)=1
85 A(9)=0:A(21)=2
86 A(10)=1:A(22)=2
87 A(11)=2:A(23)=2
88 A(12)=3:A(24)=2
126 IMAR=10+RND*100
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 24
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*12)
224 IJM=1+FIX(RND*12)
236 X(IJL)=A(IJM):X(IJM)=A(IJL):X(IJL+12)=A(IJM+12):X(IJM+12)=A(IJL+12)
1631 SUMUL=0
1632 FOR IS1=1 TO 11
1634 FOR IS2=IS1+1 TO 12
1636 SUMUL=SUMUL+HS(IS1,IS2)*(ABS(X(IS1)-X(IS2))+ABS(X(IS1+12)-X(IS2+12)))
1637 NEXT IS2
1639 NEXT IS1
1646 P=-SUMUL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 24
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-292 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)
1916 PRINT A(16),A(17),A(18),A(19),A(20)
1917 PRINT A(21),A(22),A(23),A(24)
1919 PRINT M,JJJJ
1999 NEXT JJJJ

The BASIC computer program above 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.

0 0 0 3 3
2 2 2 1 1
1 3 1 0 2
1 0 0 2 1
2 0 1 2
-289 -31453

3 3 3 0 0
1 2 2 1 2
1 0 1 0 2
1 0 0 2 1
2 0 1 2
-291 -30883

0 0 0 3 3
2 2 2 1 1
1 3 1 0 2
1 0 0 2 1
2 0 1 2
-289 -29610

0 0 0 3 3
2 2 2 1 1
1 3 1 0 2
1 0 0 2 1
2 0 1 2
-289 -29081

3 3 3 0 0
1 1 1 2 2
2 0 1 2 0
1 2 2 0 1
0 2 1 0
-289 -28266

289 is optimal. Interpreted in accordance with line 1912 through line 1919, the output above was produced during the first five minutes of running on a personal computer with speed of 2.66 GHz. and with the IBM basica/D interpreter, which is not a compiler.

References

Hillier, F. S. (1963), "Quantitative tools for plant layout analysis," J. Indust.Eng. 14, 33-40.

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).

A Heuristic Nonlinear Integer Programming Solver Applied to a Forty-Department/Facility Ordering Problem

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).

An Application of a Multi-Computer Method for Heuristically Solving an Ordering Problem with Forty Departments/Facilities

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).

An Application of a Multi-Computer Method for Heuristically Solving Integer-Programming Problems

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).