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

A Computer Program for Scheduling 107 Activities among Eight Facilities

Jsun Yui Wong

The computer program listed below is concerned with the scheduling problem of Carlson and Nemhauser (1966). As shown in line 101 through line 263 for a case of scheduling 107 activities among eight facilities, the interaction cost between activity 1 and activity 2 (if scheduled on the same facility), the interaction cost between activity 1 and activity 3, the interaction cost between activity 1 and activity 4, ..., and the interaction cost between activity 106 and activity 107 are 1, 4, 1, ..., and 9, respectively. These data were not selected randomly or scientifically; most of the numbers in line 101 below were obtained from Simmons (1969).

0 DEFINT A-Z
4 DIM X(107),A(107)
7 DIM TM(107,107),HR(107,107)
21 FOR IW=1 TO 106
23 FOR JW=IW+1 TO 107
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
101 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,1
102 DATA 2,3,1,6,6,3,0,1,2,4,4,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,4,3,4
103 DATA 1,9,3,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,5,6,3,4,2,7,4,2,3,4,3,2
104 DATA 4,3,1,7,7,1,0,4,2,3,7,4,3,0,6,3,2,2,3,2,3,5,0,6,5,3,5,4,2,9,2,7,9,3,7
105 DATA 3,4,5,7,3,5,0,1,2,5,5,2,3,0,6,3,2,2,3,4,0,4,0,2,6,3,5,2,6,8,2,3,4,3,2
106 DATA 9,3,1,7,3,4,0,1,2,5,5,4,3,0,6,3,2,2,8,4,0,1,0,6,2,3,5,2,7,1,2,7,8,3,2
107 DATA 7,4,1,0,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,1,1,0,6,5,5,8,2,7,9,2,7,8,3,6
108 DATA 2,2,3,7,3,5,3,3,2,5,5,4,3,3,6,3,2,2,3,4,0,3,0,2,6,3,5,2,3,8,2,7,8,3,4
109 DATA 5,4,1,6,5,7,0,1,2,5,5,4,3,0,6,3,2,2,3,4,2,1,2,6,6,3,5,2,7,8,2,7,2,3,5
110 DATA 2,4,1,7,3,5,1,1,2,4,2,4,3,0,5,3,2,2,3,4,0,1,2,6,6,4,5,9,7,9,2,7,9,3,2
111 DATA 7,3,4,4,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,5,1,0,6,6,3,5,2,4,4,2,4,4,3,1
112 DATA 2,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
113 DATA 3,4,6,7,3,5,1,1,2,5,5,4,3,4,6,3,2,2,3,4,3,3,1,6,6,3,5,2,7,9,2,7,9,3,8
114 DATA 4,4,1,7,4,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,1,4,6,4,6,2,7,9,2,7,9,3,1
115 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
116 DATA 2,5,1,3,6,2,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,6,2,7,9,3,2
117 DATA 9,3,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,5,4,5,2,7,2,2,4,4,3,7
118 DATA 3,4,1,7,4,5,3,1,2,5,3,4,3,0,6,3,2,2,3,4,5,1,4,6,4,3,5,2,3,4,2,7,4,3,1
119 DATA 6,4,1,7,3,5,0,1,2,5,5,4,3,6,6,3,2,2,3,4,0,1,6,6,6,3,5,2,7,0,2,7,9,3,7
120 DATA 4,2,1,2,7,0,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,3,6,6,3,2,2,3,2,2,4,4,3
121 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
122 DATA 3,4,2,7,3,0,0,1,2,4,6,4,3,0,6,3,2,2,3,4,0,2,0,5,6,3,5,2,7,2,2,7,2,3,2
123 DATA 8,4,1,7,3,5,0,1,2,4,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,0,2,7,9,3,8
124 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,4,2,3,5,2,7,8,2,7,0,3,1
125 DATA 9,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,3,2,3,4,0,1,0,6,2,3,5,2,7,9,2,7,0,3,7
126 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,6,6,3,5,2,7,8,2,7,6,3,2
127 DATA 1,3,1,6,3,5,0,1,2,5,6,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
128 DATA 7,4,1,7,7,8,0,1,2,5,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,3,2,7,9,3,1
129 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,6,3,5,2,7,9,2,7,9,3,3
130 DATA 3,4,2,8,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,8,3,5,2,7,8,2,8,0,3,4
131 DATA 6,4,1,7,8,9,0,1,2,5,4,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,8,3,5
132 DATA 3,4,1,7,3,5,0,1,2,1,2,4,3,0,6,3,2,2,3,4,0,1,0,6,4,3,5,2,7,9,2,7,9,3,9
133 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,2,3,3
134 DATA 1,4,1,7,5,2,3,1,2,5,5,4,3,1,6,3,2,2,3,4,2,1,0,6,6,3,5,2,7,9,2,7,9,3,1
135 DATA 1,4,1,7,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,6,6,6,3,5,2,2,6,2,7,9,3,1
136 DATA 2,4,1,7,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,4,9,2,7,6,3,1
137 DATA 7,4,4,5,6,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,0,1,5,6,7,3,5,2,7,1,2,4,6,3,2
138 DATA 5,4,1,7,3,5,0,5,2,5,5,4,3,0,6,3,2,2,3,4,0,4,0,6,6,3,5,2,7,1,2,7,4,3,2
139 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,6,3,5,2,7,2,2,7,9,3,2
140 DATA 4,4,1,7,8,5,3,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,5,3,5,2,7,9,2,7,2,3,2
141 DATA 2,4,1,7,4,5,0,1,2,5,2,4,3,0,6,3,2,2,3,2,0,1,0,5,6,3,5,2,4,9,2,7,4,3,4
142 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,5,0,1,0,4,6,3,5,2,7,3,2,7,4,3,1
143 DATA 1,4,1,4,3,4,4,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
144 DATA 6,4,5,7,3,5,0,1,2,3,5,4,3,3,6,3,2,2,3,4,0,1,0,4,7,3,5,2,7,3,2,7,5,3,3
145 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,3,2,7,4,3,2
146 DATA 5,4,1,7,4,6,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,9,3,4
147 DATA 3,4,1,7,3,5,0,1,2,5,3,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,3,3,1
148 DATA 6,4,1,7,3,5,6,1,2,5,5,4,3,0,6,3,2,2,3,4,6,1,0,5,5,3,3,2,7,3,2,7,9,3,3
149 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,7,6,6,3,5,2,7,7,2,7,2,3,2
150 DATA 1,4,1,7,3,5,2,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,1,6,6,3,5,2,7,1,2,7,9,3,1
151 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,2,3,2
152 DATA 7,4,1,7,3,5,7,1,2,5,5,4,3,0,6,3,2,2,3,4,7,1,0,6,6,3,5,2,0,0,2,7,9,3,1
153 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,1
154 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,0
155 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,1
156 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
157 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,1,1,3,5,2,7,9,2,7,9,3,2
158 DATA 1,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,1,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
159 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,1,2,7,9,3,2
160 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,7
161 DATA 4,4,1,5,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,1,3,5
162 DATA 9,4,1,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,2,2,7,9,3,8
163 DATA 7,4,1,7,3,5,0,1,2,0,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
164 DATA 3,4,1,7,3,0,0,1,2,0,5,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,9,2,7,9,3,6
165 DATA 6,2,5,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,2,0,2,6,3,5,2,7,2,2,7,2,3,4
166 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,3,2,3,4,0,1,0,6,6,3,5,2,7,3,2,7,9,3,7
167 DATA 1,2,1,7,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,4,6,3,5,2,7,9,2,7,4,3,3
168 DATA 3,4,1,7,3,5,0,3,2,5,3,4,3,0,6,3,2,2,3,4,0,2,0,6,6,3,5,2,7,3,2,7,9,3,2
169 DATA 3,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
170 DATA 5,0,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
171 DATA 5,4,3,7,5,5,2,5,2,5,5,4,3,0,6,3,2,2,3,4,3,4,4,6,3,3,5,2,7,9,2,7,6,3,4
172 DATA 3,4,1,7,3,5,7,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,1,2,3,5,2,7,9,2,7,5,3,3
173 DATA 5,4,1,7,2,4,0,1,2,5,5,4,3,0,2,3,2,2,3,4,0,1,0,6,6,3,5,2,7,5,2,7,9,3,9
174 DATA 3,4,1,0,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,0,6,3,5,2,7,9,2,7,0,3,4
175 DATA 9,4,2,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,2,2,3,3,5,2,7,3,2,7,9,3,7
176 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,2,3,5,2,7,3,2,7,9,3,4
177 DATA 4,4,4,7,3,5,0,1,2,2,3,4,3,0,6,3,2,2,3,4,0,5,0,6,1,3,5,2,7,9,2,7,9,3,6
178 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,2
179 DATA 3,4,3,7,3,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,0,6,6,3,3,2,7,1,2,7,9,3,4
180 DATA 2,4,1,7,3,5,6,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,0,3,2
181 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,1,2,3,5,2,7,3,2,7,9,3,4
182 DATA 6,5,2,2,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,0,3,3,3,6,3,5,2,7,3,2,7,2,3,5
183 DATA 2,4,1,7,3,2,2,1,2,5,5,4,3,0,4,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,6,3,3
184 DATA 3,4,1,7,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,7,1,0,6,4,3,5,2,7,9,2,7,9,3,3
185 DATA 4,4,1,7,3,5,1,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,3,3,6
186 DATA 2,8,2,7,3,5,1,1,2,5,5,4,3,3,2,3,2,2,3,4,9,1,0,6,6,3,5,8,7,9,2,2,3,3,9
187 DATA 6,4,1,7,4,5,1,1,2,5,4,4,3,3,6,3,2,2,3,4,6,1,0,6,6,3,5,2,7,6,2,7,3,3,4
188 DATA 7,4,1,7,3,5,6,1,2,5,7,4,6,3,6,3,2,2,3,4,0,4,0,6,2,3,5,2,7,9,2,7,4,3,2
189 DATA 2,9,1,4,3,2,1,1,2,5,5,4,3,3,6,3,5,2,3,4,0,1,0,2,6,3,9,2,7,9,2,4,3,3,4
190 DATA 7,4,1,7,3,2,1,1,2,5,3,4,3,3,6,3,7,2,3,4,0,3,0,6,6,3,5,2,7,7,2,7,3,3,3
191 DATA 4,7,1,1,3,5,1,1,2,5,1,4,7,3,6,3,2,2,3,4,0,1,0,1,6,3,5,2,7,1,2,7,3,3,1
192 DATA 5,4,9,7,3,5,1,1,2,9,5,4,5,3,9,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,3,3,9
193 DATA 9,9,1,8,3,5,1,1,2,5,8,4,9,3,6,3,2,2,3,4,9,1,0,6,6,8,5,5,7,9,2,7,3,5,8
194 DATA 8,4,1,7,2,5,8,1,2,5,5,4,3,2,6,3,8,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,3,3,2
195 DATA 2,4,1,7,3,5,1,1,5,2,5,4,3,5,6,3,2,3,5,4,0,1,0,3,6,3,5,2,7,9,2,7,3,5,3
196 DATA 9,6,1,7,3,5,1,7,2,5,5,4,3,7,7,3,2,2,3,9,0,7,6,9,6,3,6,2,7,9,2,7,6,3,9
197 DATA 7,4,1,7,3,5,8,3,2,5,7,4,3,8,6,3,2,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,7,3,8
198 DATA 6,4,2,7,3,5,1,2,2,5,5,4,6,3,2,3,2,4,3,4,0,1,0,7,6,3,5,2,4,9,2,7,2,3,7
199 DATA 5,7,1,6,3,5,7,1,2,5,5,4,3,3,6,3,7,2,3,4,9,1,9,6,5,3,5,6,7,9,6,6,9,3,5
200 DATA 3,8,1,7,3,5,1,8,2,3,5,4,3,3,6,3,2,2,3,4,0,3,0,6,6,3,5,8,7,9,2,7,3,3,8
201 DATA 6,4,1,7,3,5,1,1,2,5,6,4,3,3,6,3,2,2,3,4,6,1,6,6,6,3,5,2,7,6,2,7,3,6,7
202 DATA 4,7,1,7,3,5,1,7,2,7,5,4,3,3,6,3,7,2,3,4,0,1,0,7,6,3,5,2,6,9,2,7,3,3,3
203 DATA 4,6,1,7,3,5,1,1,2,5,6,4,6,3,6,3,2,6,3,6,6,1,0,6,6,3,6,6,7,9,2,7,6,3,1
204 DATA 6,4,1,7,3,5,1,1,2,6,5,4,3,6,6,3,2,2,6,4,0,2,0,6,6,3,6,2,7,6,3,7,3,6,2
205 DATA 5,5,1,4,4,4,5,4,2,5,5,4,3,3,6,4,2,2,3,4,5,1,0,6,4,5,5,2,7,5,2,7,3,4,5
206 DATA 5,4,1,7,3,5,1,1,2,2,7,7,3,3,2,3,2,7,3,4,0,1,0,7,6,3,5,2,7,9,2,7,7,3,1
207 DATA 4,3,4,7,4,5,1,1,2,3,5,4,4,3,6,3,2,2,4,3,3,1,0,6,6,3,5,2,7,3,2,7,3,4,6
208 DATA 6,5,5,7,3,5,6,1,2,5,5,4,3,3,4,3,2,2,3,4,0,5,0,4,6,3,5,2,7,9,2,7,5,3,4
209 DATA 8,8,1,7,3,5,1,3,4,5,5,4,3,3,6,3,1,2,3,4,1,1,4,8,6,3,5,2,7,8,2,7,3,3,0
210 DATA 9,4,1,6,3,6,1,1,2,5,9,4,3,3,6,9,9,6,3,4,0,1,0,6,6,2,5,2,7,9,2,7,3,2,2
211 DATA 6,4,6,2,3,5,2,1,2,5,5,6,3,3,6,3,2,7,3,4,6,1,0,6,6,3,7,2,7,9,2,7,7,3,7
212 DATA 5,4,5,7,3,5,1,4,5,2,5,4,2,3,2,3,2,2,2,2,0,3,2,6,5,3,5,2,8,9,2,7,7,3,5
213 DATA 0,5,1,7,3,5,5,1,2,5,6,4,3,5,6,3,2,2,3,4,0,1,6,5,6,3,5,2,7,9,2,7,6,3,5
214 DATA 3,4,1,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,0,1,0,6,6,2,2,2,7,9,2,7,6,3,0
215 DATA 5,4,1,4,2,0,1,1,5,2,0,4,5,3,6,3,2,2,2,4,0,1,0,5,6,2,5,2,7,9,2,7,6,3,9
216 DATA 7,4,1,4,2,0,1,7,2,2,0,4,3,3,6,3,2,7,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,2
217 DATA 2,3,5,4,2,0,1,3,2,3,0,4,3,3,2,3,2,3,2,4,0,1,0,6,2,2,3,2,7,9,2,7,6,3,3
218 DATA 3,4,1,4,2,0,5,1,2,2,0,5,3,3,6,3,2,2,5,5,0,5,0,6,6,2,2,6,9,9,2,7,6,3,4
219 DATA 7,4,1,3,4,0,1,1,2,2,0,4,3,4,6,3,2,2,2,4,0,1,0,6,6,2,2,2,7,9,2,3,6,3,3
220 DATA 8,4,1,4,2,0,1,1,2,2,0,4,3,3,6,8,2,2,2,4,8,1,0,8,6,2,2,2,7,4,2,7,4,4,2
221 DATA 3,2,4,4,2,0,4,1,8,4,0,4,3,3,8,3,4,2,2,4,0,4,0,6,6,6,6,2,7,9,2,7,6,3,0
222 DATA 8,4,1,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,0,1,0,6,8,2,2,9,9,9,2,7,6,3,0
223 DATA 7,4,1,7,8,0,1,1,2,2,0,4,8,7,6,3,2,2,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,8
224 DATA 5,3,1,4,2,3,1,1,2,2,0,4,3,3,6,3,2,5,2,5,0,1,2,6,6,2,2,2,7,9,2,7,5,3,4
225 DATA 3,4,5,4,2,0,1,1,4,2,0,4,3,3,3,5,2,2,2,4,0,5,0,6,6,2,5,2,7,9,2,5,6,3,5
226 DATA 7,4,1,4,2,0,1,7,2,2,7,7,3,3,6,3,7,2,7,4,7,1,0,6,7,7,2,2,8,8,2,7,6,3,4
227 DATA 7,2,1,8,2,0,1,1,2,7,0,4,3,8,6,3,2,7,2,4,0,1,3,3,6,2,2,2,7,9,2,7,6,3,3
228 DATA 2,2,1,3,2,0,1,1,2,2,0,4,3,3,2,3,2,2,2,2,0,1,0,6,2,2,2,2,7,2,2,5,6,3,4
229 DATA 6,4,1,6,2,0,1,1,2,2,6,4,3,3,8,3,2,2,2,4,0,1,0,6,6,2,3,3,7,3,2,7,6,3,4
230 DATA 8,4,8,4,8,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,8,1,0,6,6,2,2,2,6,9,2,7,7,3,2
231 DATA 5,4,2,4,2,0,5,1,2,2,2,5,3,3,6,3,2,5,2,4,0,1,0,6,6,2,5,2,7,9,2,7,6,3,2
232 DATA 2,4,5,4,2,0,1,5,2,2,2,4,3,3,6,3,2,2,2,4,7,1,0,9,6,2,2,2,7,9,2,7,9,3,5
233 DATA 7,4,4,4,2,7,5,1,2,2,0,3,3,3,6,3,5,2,2,5,0,1,0,6,6,2,3,2,7,9,2,5,6,3,4
234 DATA 9,8,1,4,2,0,1,3,2,2,0,4,3,3,6,3,8,2,2,4,0,1,0,8,6,2,2,2,7,9,2,7,6,3,7
235 DATA 8,4,7,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,8,4,8,1,0,6,6,2,8,2,4,9,2,7,6,3,8
236 DATA 6,4,7,4,2,0,1,6,2,2,0,4,3,3,7,3,7,2,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,1
237 DATA 4,5,1,4,2,0,5,1,2,2,4,4,3,3,6,3,2,4,2,4,0,1,0,4,6,2,2,2,7,9,2,4,6,3,5
238 DATA 5,3,4,4,2,0,1,3,2,4,0,4,3,3,6,3,2,3,2,4,0,9,0,4,6,2,4,2,7,9,2,7,6,3,9
239 DATA 4,6,1,4,2,0,1,4,2,4,0,4,6,3,6,3,2,4,5,4,0,1,0,6,6,2,6,2,7,9,2,7,5,3,6
240 DATA 5,4,6,5,2,0,1,6,2,4,0,4,3,4,6,3,2,6,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,0
241 DATA 1,4,1,3,2,0,1,7,2,3,0,4,1,3,6,3,2,7,2,4,0,1,0,6,1,3,7,2,7,9,2,3,6,7,4
242 DATA 3,4,1,4,2,0,4,7,3,2,3,4,7,3,6,3,3,7,2,4,2,2,4,6,7,2,7,2,3,9,2,1,6,7,5
243 DATA 7,8,1,4,2,0,1,7,2,8,0,4,7,5,6,3,2,7,2,4,0,1,0,6,5,2,0,2,7,9,2,3,6,7,0
244 DATA 4,5,8,4,2,0,1,7,2,2,0,8,5,3,6,3,2,7,2,7,0,1,5,6,7,2,7,2,7,9,5,7,6,7,8
245 DATA 5,3,1,4,2,0,1,7,2,2,3,4,7,3,6,5,5,7,2,4,5,1,0,4,7,2,7,2,7,5,2,7,5,7,8
246 DATA 9,4,1,2,6,3,1,7,9,2,0,4,7,3,6,3,2,9,2,4,0,1,0,6,7,2,3,2,7,9,2,9,6,9,3
247 DATA 2,4,1,4,2,0,3,6,2,3,0,4,3,3,6,3,2,7,6,3,0,3,0,6,7,2,7,2,7,9,3,7,6,7,5
248 DATA 7,9,4,4,2,0,1,4,8,2,0,4,7,3,4,8,2,7,2,4,4,1,8,8,4,2,7,2,4,9,2,7,4,8,9
249 DATA 4,7,3,5,2,0,1,7,2,7,0,7,7,5,6,3,2,5,5,4,0,1,0,6,7,7,7,7,7,9,2,6,6,7,6
250 DATA 7,4,1,4,6,7,1,7,2,2,8,6,7,3,6,5,2,7,2,4,0,3,0,5,7,2,7,2,7,5,2,7,6,3,7
251 DATA 3,4,3,4,2,3,1,7,2,2,3,2,7,3,6,3,2,7,6,6,0,1,3,4,7,2,4,3,7,9,4,7,6,7,3
252 DATA 7,3,1,6,2,0,4,7,2,2,0,8,7,3,6,3,2,8,2,4,4,1,0,4,4,8,7,2,4,9,8,4,6,5,4
253 DATA 7,4,2,4,2,0,2,7,2,2,2,4,7,3,2,3,5,7,2,4,5,5,0,6,5,2,5,2,5,5,2,7,5,5,2
254 DATA 3,4,1,4,2,3,1,7,2,2,0,4,3,4,4,3,2,7,2,6,0,6,0,6,7,6,7,6,7,9,6,7,3,7,3
255 DATA 2,4,1,4,2,0,1,6,4,5,0,4,7,8,6,3,2,6,8,4,8,1,6,6,5,2,5,2,7,6,2,5,4,7,5
256 DATA 7,4,4,4,2,3,4,5,2,2,5,3,7,3,6,6,2,7,2,4,0,5,5,5,4,2,5,2,5,9,5,5,6,2,4
257 DATA 2,2,1,2,2,2,4,7,4,4,4,6,6,6,3,3,3,7,2,3,3,1,0,6,7,3,7,2,7,3,2,7,6,7,2
258 DATA 2,4,2,4,4,0,1,4,2,2,4,4,7,3,5,3,2,5,2,4,1,1,0,6,7,2,7,2,7,9,2,7,1,7,2
259 DATA 9,3,1,3,2,3,4,9,2,2,0,5,5,3,6,3,2,7,2,2,0,2,2,6,7,2,2,9,7,9,2,7,6,2,5
260 DATA 7,4,4,4,2,0,5,7,2,5,5,4,7,3,7,3,2,8,8,4,0,1,8,6,8,2,7,2,8,8,2,7,6,7,0
261 DATA 5,4,1,4,2,0,1,5,2,2,0,4,7,8,6,3,2,7,2,8,5,3,0,6,7,4,6,4,7,4,2,7,6,7,4
262 DATA 2,4,1,4,2,0,1,7,3,2,0,4,7,4,7,3,9,7,2,4,0,1,0,6,4,2,7,2,4,4,2,7,6,4,8
263 DATA 9
1065 FOR JJJJ=-32000 TO 32000
1074 RANDOMIZE JJJJ
1076 M=-32000
1085 FOR I=1 TO 107
1088 A(I)=FIX(RND*7)
1089 NEXT I
1126 IMAR=10+FIX(RND*2000)
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 107
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*107)
1234 X(IJL)=FIX(RND*8)
1533 FOR IX=1 TO 106
1534 FOR JX=IX+1 TO 107
1542 IF X(IX)=X(JX) THEN TM(IX,JX)=HR(IX,JX) ELSE TM(IX,JX)=0
1545 NEXT JX
1547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 106
1614 FOR IR2=IR1+1 TO 107
1616 SUMTL=SUMTL+TM(IR1,IR2)
1617 NEXT IR2
1619 NEXT IR1
1645 P=-SUMTL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 107
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 1128
1670 NEXT I
1890 IF M>-1330 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)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1928 PRINT A(81),A(82),A(83),A(84),A(85)
1929 PRINT A(86),A(87),A(88),A(89),A(90)
1930 PRINT A(91),A(92),A(93),A(94),A(95)
1931 PRINT A(96),A(97),A(98),A(99),A(100)
1932 PRINT A(101),A(102),A(103),A(104),A(105)
1937 PRINT A(106),A(107),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced during the first 20 hours of running are presented below. Only the candidate solution at JJJJ=-31926 is presented in full; each of the other candidate solutions below is briefly presented with its line
1937.

1 1 6 3 5
7 2 1 1 6
7 2 3 4 1
4 2 7 6 7
0 4 1 4 3
5 7 6 1 6
2 7 5 0 5
1 2 6 0 6
7 2 1 2 6
7 2 3 7 1
0 0 7 4 3
5 0 6 4 7
4 4 6 1 6
4 4 5 2 3
0 2 5 2 3
0 0 1 6 6
3 0 3 7 1
3 4 3 7 7
5 0 5 2 6
5 0 5 1 5
4 4 5 7 3
1 4 -1315 -31926

4 1 -1328 -31908

7 1 -1328 -31897

7 5 -1326 -31838

4 3 -1320 -31681

Interpreted in accordance with line 1912 through line 1937, these candidate solutions were produced during the first 20 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

Carlson, R. C., and G. L. Nemhauser, "Scheduling to Minimize Interaction Cost," Operations Research 14, 52-58 (1966).

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

A Computer Program for Scheduling 100 Activities among Seven Facilities

Jsun Yui Wong

The computer program listed below is concerned with the scheduling problem of Carlson and Nemhauser (1966). As shown in line 101 through line 242 for a case of scheduling 100 activities among seven facilities, the interaction cost between activity 1 and activity 2 (if scheduled on the same facility), the interaction cost between activity 1 and activity 3, the interaction cost between activity 1 and activity 4, ..., and the interaction cost between activity 99 and activity 100 are
1, 4, 1, ..., and 9, respectively. These data were not selected randomly or scientifically.

0 DEFINT A-Z
4 DIM X(100),A(100)
7 DIM TM(100,100),HR(100,100)
21 FOR IW=1 TO 99
23 FOR JW=IW+1 TO 100
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
101 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,1
102 DATA 2,3,1,6,6,3,0,1,2,4,4,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,4,3,4
103 DATA 1,9,3,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,5,6,3,4,2,7,4,2,3,4,3,2
104 DATA 4,3,1,7,7,1,0,4,2,3,7,4,3,0,6,3,2,2,3,2,3,5,0,6,5,3,5,4,2,9,2,7,9,3,7
105 DATA 3,4,5,7,3,5,0,1,2,5,5,2,3,0,6,3,2,2,3,4,0,4,0,2,6,3,5,2,6,8,2,3,4,3,2
106 DATA 9,3,1,7,3,4,0,1,2,5,5,4,3,0,6,3,2,2,8,4,0,1,0,6,2,3,5,2,7,1,2,7,8,3,2
107 DATA 7,4,1,0,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,1,1,0,6,5,5,8,2,7,9,2,7,8,3,6
108 DATA 2,2,3,7,3,5,3,3,2,5,5,4,3,3,6,3,2,2,3,4,0,3,0,2,6,3,5,2,3,8,2,7,8,3,4
109 DATA 5,4,1,6,5,7,0,1,2,5,5,4,3,0,6,3,2,2,3,4,2,1,2,6,6,3,5,2,7,8,2,7,2,3,5
110 DATA 2,4,1,7,3,5,1,1,2,4,2,4,3,0,5,3,2,2,3,4,0,1,2,6,6,4,5,9,7,9,2,7,9,3,2
111 DATA 7,3,4,4,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,5,1,0,6,6,3,5,2,4,4,2,4,4,3,1
112 DATA 2,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
113 DATA 3,4,6,7,3,5,1,1,2,5,5,4,3,4,6,3,2,2,3,4,3,3,1,6,6,3,5,2,7,9,2,7,9,3,8
114 DATA 4,4,1,7,4,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,1,4,6,4,6,2,7,9,2,7,9,3,1
115 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
116 DATA 2,5,1,3,6,2,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,6,2,7,9,3,2
117 DATA 9,3,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,5,4,5,2,7,2,2,4,4,3,7
118 DATA 3,4,1,7,4,5,3,1,2,5,3,4,3,0,6,3,2,2,3,4,5,1,4,6,4,3,5,2,3,4,2,7,4,3,1
119 DATA 6,4,1,7,3,5,0,1,2,5,5,4,3,6,6,3,2,2,3,4,0,1,6,6,6,3,5,2,7,0,2,7,9,3,7
120 DATA 4,2,1,2,7,0,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,3,6,6,3,2,2,3,2,2,4,4,3
121 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
122 DATA 3,4,2,7,3,0,0,1,2,4,6,4,3,0,6,3,2,2,3,4,0,2,0,5,6,3,5,2,7,2,2,7,2,3,2
123 DATA 8,4,1,7,3,5,0,1,2,4,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,0,2,7,9,3,8
124 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,4,2,3,5,2,7,8,2,7,0,3,1
125 DATA 9,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,3,2,3,4,0,1,0,6,2,3,5,2,7,9,2,7,0,3,7
126 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,6,6,3,5,2,7,8,2,7,6,3,2
127 DATA 1,3,1,6,3,5,0,1,2,5,6,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
128 DATA 7,4,1,7,7,8,0,1,2,5,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,3,2,7,9,3,1
129 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,6,3,5,2,7,9,2,7,9,3,3
130 DATA 3,4,2,8,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,8,3,5,2,7,8,2,8,0,3,4
131 DATA 6,4,1,7,8,9,0,1,2,5,4,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,8,3,5
132 DATA 3,4,1,7,3,5,0,1,2,1,2,4,3,0,6,3,2,2,3,4,0,1,0,6,4,3,5,2,7,9,2,7,9,3,9
133 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,2,3,3
134 DATA 1,4,1,7,5,2,3,1,2,5,5,4,3,1,6,3,2,2,3,4,2,1,0,6,6,3,5,2,7,9,2,7,9,3,1
135 DATA 1,4,1,7,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,6,6,6,3,5,2,2,6,2,7,9,3,1
136 DATA 2,4,1,7,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,4,9,2,7,6,3,1
137 DATA 7,4,4,5,6,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,0,1,5,6,7,3,5,2,7,1,2,4,6,3,2
138 DATA 5,4,1,7,3,5,0,5,2,5,5,4,3,0,6,3,2,2,3,4,0,4,0,6,6,3,5,2,7,1,2,7,4,3,2
139 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,6,3,5,2,7,2,2,7,9,3,2
140 DATA 4,4,1,7,8,5,3,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,5,3,5,2,7,9,2,7,2,3,2
141 DATA 2,4,1,7,4,5,0,1,2,5,2,4,3,0,6,3,2,2,3,2,0,1,0,5,6,3,5,2,4,9,2,7,4,3,4
142 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,5,0,1,0,4,6,3,5,2,7,3,2,7,4,3,1
143 DATA 1,4,1,4,3,4,4,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
144 DATA 6,4,5,7,3,5,0,1,2,3,5,4,3,3,6,3,2,2,3,4,0,1,0,4,7,3,5,2,7,3,2,7,5,3,3
145 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,3,2,7,4,3,2
146 DATA 5,4,1,7,4,6,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,9,3,4
147 DATA 3,4,1,7,3,5,0,1,2,5,3,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,3,3,1
148 DATA 6,4,1,7,3,5,6,1,2,5,5,4,3,0,6,3,2,2,3,4,6,1,0,5,5,3,3,2,7,3,2,7,9,3,3
149 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,7,6,6,3,5,2,7,7,2,7,2,3,2
150 DATA 1,4,1,7,3,5,2,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,1,6,6,3,5,2,7,1,2,7,9,3,1
151 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,2,3,2
152 DATA 7,4,1,7,3,5,7,1,2,5,5,4,3,0,6,3,2,2,3,4,7,1,0,6,6,3,5,2,0,0,2,7,9,3,1
153 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,1
154 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,0
155 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,1
156 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
157 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,1,1,3,5,2,7,9,2,7,9,3,2
158 DATA 1,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,1,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
159 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,1,2,7,9,3,2
160 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,7
161 DATA 4,4,1,5,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,1,3,5
162 DATA 9,4,1,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,2,2,7,9,3,8
163 DATA 7,4,1,7,3,5,0,1,2,0,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
164 DATA 3,4,1,7,3,0,0,1,2,0,5,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,9,2,7,9,3,6
165 DATA 6,2,5,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,2,0,2,6,3,5,2,7,2,2,7,2,3,4
166 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,3,2,3,4,0,1,0,6,6,3,5,2,7,3,2,7,9,3,7
167 DATA 1,2,1,7,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,4,6,3,5,2,7,9,2,7,4,3,3
168 DATA 3,4,1,7,3,5,0,3,2,5,3,4,3,0,6,3,2,2,3,4,0,2,0,6,6,3,5,2,7,3,2,7,9,3,2
169 DATA 3,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
170 DATA 5,0,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
171 DATA 5,4,3,7,5,5,2,5,2,5,5,4,3,0,6,3,2,2,3,4,3,4,4,6,3,3,5,2,7,9,2,7,6,3,4
172 DATA 3,4,1,7,3,5,7,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,1,2,3,5,2,7,9,2,7,5,3,3
173 DATA 5,4,1,7,2,4,0,1,2,5,5,4,3,0,2,3,2,2,3,4,0,1,0,6,6,3,5,2,7,5,2,7,9,3,9
174 DATA 3,4,1,0,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,0,6,3,5,2,7,9,2,7,0,3,4
175 DATA 9,4,2,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,2,2,3,3,5,2,7,3,2,7,9,3,7
176 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,2,3,5,2,7,3,2,7,9,3,4
177 DATA 4,4,4,7,3,5,0,1,2,2,3,4,3,0,6,3,2,2,3,4,0,5,0,6,1,3,5,2,7,9,2,7,9,3,6
178 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,2
179 DATA 3,4,3,7,3,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,0,6,6,3,3,2,7,1,2,7,9,3,4
180 DATA 2,4,1,7,3,5,6,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,0,3,2
181 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,1,2,3,5,2,7,3,2,7,9,3,4
182 DATA 6,5,2,2,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,0,3,3,3,6,3,5,2,7,3,2,7,2,3,5
183 DATA 2,4,1,7,3,2,2,1,2,5,5,4,3,0,4,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,6,3,3
184 DATA 3,4,1,7,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,7,1,0,6,4,3,5,2,7,9,2,7,9,3,3
185 DATA 4,4,1,7,3,5,1,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,3,3,6
186 DATA 2,8,2,7,3,5,1,1,2,5,5,4,3,3,2,3,2,2,3,4,9,1,0,6,6,3,5,8,7,9,2,2,3,3,9
187 DATA 6,4,1,7,4,5,1,1,2,5,4,4,3,3,6,3,2,2,3,4,6,1,0,6,6,3,5,2,7,6,2,7,3,3,4
188 DATA 7,4,1,7,3,5,6,1,2,5,7,4,6,3,6,3,2,2,3,4,0,4,0,6,2,3,5,2,7,9,2,7,4,3,2
189 DATA 2,9,1,4,3,2,1,1,2,5,5,4,3,3,6,3,5,2,3,4,0,1,0,2,6,3,9,2,7,9,2,4,3,3,4
190 DATA 7,4,1,7,3,2,1,1,2,5,3,4,3,3,6,3,7,2,3,4,0,3,0,6,6,3,5,2,7,7,2,7,3,3,3
191 DATA 4,7,1,1,3,5,1,1,2,5,1,4,7,3,6,3,2,2,3,4,0,1,0,1,6,3,5,2,7,1,2,7,3,3,1
192 DATA 5,4,9,7,3,5,1,1,2,9,5,4,5,3,9,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,3,3,9
193 DATA 9,9,1,8,3,5,1,1,2,5,8,4,9,3,6,3,2,2,3,4,9,1,0,6,6,8,5,5,7,9,2,7,3,5,8
194 DATA 8,4,1,7,2,5,8,1,2,5,5,4,3,2,6,3,8,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,3,3,2
195 DATA 2,4,1,7,3,5,1,1,5,2,5,4,3,5,6,3,2,3,5,4,0,1,0,3,6,3,5,2,7,9,2,7,3,5,3
196 DATA 9,6,1,7,3,5,1,7,2,5,5,4,3,7,7,3,2,2,3,9,0,7,6,9,6,3,6,2,7,9,2,7,6,3,9
197 DATA 7,4,1,7,3,5,8,3,2,5,7,4,3,8,6,3,2,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,7,3,8
198 DATA 6,4,2,7,3,5,1,2,2,5,5,4,6,3,2,3,2,4,3,4,0,1,0,7,6,3,5,2,4,9,2,7,2,3,7
199 DATA 5,7,1,6,3,5,7,1,2,5,5,4,3,3,6,3,7,2,3,4,9,1,9,6,5,3,5,6,7,9,6,6,9,3,5
200 DATA 3,8,1,7,3,5,1,8,2,3,5,4,3,3,6,3,2,2,3,4,0,3,0,6,6,3,5,8,7,9,2,7,3,3,8
201 DATA 6,4,1,7,3,5,1,1,2,5,6,4,3,3,6,3,2,2,3,4,6,1,6,6,6,3,5,2,7,6,2,7,3,6,7
202 DATA 4,7,1,7,3,5,1,7,2,7,5,4,3,3,6,3,7,2,3,4,0,1,0,7,6,3,5,2,6,9,2,7,3,3,3
203 DATA 4,6,1,7,3,5,1,1,2,5,6,4,6,3,6,3,2,6,3,6,6,1,0,6,6,3,6,6,7,9,2,7,6,3,1
204 DATA 6,4,1,7,3,5,1,1,2,6,5,4,3,6,6,3,2,2,6,4,0,2,0,6,6,3,6,2,7,6,3,7,3,6,2
205 DATA 5,5,1,4,4,4,5,4,2,5,5,4,3,3,6,4,2,2,3,4,5,1,0,6,4,5,5,2,7,5,2,7,3,4,5
206 DATA 5,4,1,7,3,5,1,1,2,2,7,7,3,3,2,3,2,7,3,4,0,1,0,7,6,3,5,2,7,9,2,7,7,3,1
207 DATA 4,3,4,7,4,5,1,1,2,3,5,4,4,3,6,3,2,2,4,3,3,1,0,6,6,3,5,2,7,3,2,7,3,4,6
208 DATA 6,5,5,7,3,5,6,1,2,5,5,4,3,3,4,3,2,2,3,4,0,5,0,4,6,3,5,2,7,9,2,7,5,3,4
209 DATA 8,8,1,7,3,5,1,3,4,5,5,4,3,3,6,3,1,2,3,4,1,1,4,8,6,3,5,2,7,8,2,7,3,3,0
210 DATA 9,4,1,6,3,6,1,1,2,5,9,4,3,3,6,9,9,6,3,4,0,1,0,6,6,2,5,2,7,9,2,7,3,2,2
211 DATA 6,4,6,2,3,5,2,1,2,5,5,6,3,3,6,3,2,7,3,4,6,1,0,6,6,3,7,2,7,9,2,7,7,3,7
212 DATA 5,4,5,7,3,5,1,4,5,2,5,4,2,3,2,3,2,2,2,2,0,3,2,6,5,3,5,2,8,9,2,7,7,3,5
213 DATA 0,5,1,7,3,5,5,1,2,5,6,4,3,5,6,3,2,2,3,4,0,1,6,5,6,3,5,2,7,9,2,7,6,3,5
214 DATA 3,4,1,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,0,1,0,6,6,2,2,2,7,9,2,7,6,3,0
215 DATA 5,4,1,4,2,0,1,1,5,2,0,4,5,3,6,3,2,2,2,4,0,1,0,5,6,2,5,2,7,9,2,7,6,3,9
216 DATA 7,4,1,4,2,0,1,7,2,2,0,4,3,3,6,3,2,7,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,2
217 DATA 2,3,5,4,2,0,1,3,2,3,0,4,3,3,2,3,2,3,2,4,0,1,0,6,2,2,3,2,7,9,2,7,6,3,3
218 DATA 3,4,1,4,2,0,5,1,2,2,0,5,3,3,6,3,2,2,5,5,0,5,0,6,6,2,2,6,9,9,2,7,6,3,4
219 DATA 7,4,1,3,4,0,1,1,2,2,0,4,3,4,6,3,2,2,2,4,0,1,0,6,6,2,2,2,7,9,2,3,6,3,3
220 DATA 8,4,1,4,2,0,1,1,2,2,0,4,3,3,6,8,2,2,2,4,8,1,0,8,6,2,2,2,7,4,2,7,4,4,2
221 DATA 3,2,4,4,2,0,4,1,8,4,0,4,3,3,8,3,4,2,2,4,0,4,0,6,6,6,6,2,7,9,2,7,6,3,0
222 DATA 8,4,1,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,0,1,0,6,8,2,2,9,9,9,2,7,6,3,0
223 DATA 7,4,1,7,8,0,1,1,2,2,0,4,8,7,6,3,2,2,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,8
224 DATA 5,3,1,4,2,3,1,1,2,2,0,4,3,3,6,3,2,5,2,5,0,1,2,6,6,2,2,2,7,9,2,7,5,3,4
225 DATA 3,4,5,4,2,0,1,1,4,2,0,4,3,3,3,5,2,2,2,4,0,5,0,6,6,2,5,2,7,9,2,5,6,3,5
226 DATA 7,4,1,4,2,0,1,7,2,2,7,7,3,3,6,3,7,2,7,4,7,1,0,6,7,7,2,2,8,8,2,7,6,3,4
227 DATA 7,2,1,8,2,0,1,1,2,7,0,4,3,8,6,3,2,7,2,4,0,1,3,3,6,2,2,2,7,9,2,7,6,3,3
228 DATA 2,2,1,3,2,0,1,1,2,2,0,4,3,3,2,3,2,2,2,2,0,1,0,6,2,2,2,2,7,2,2,5,6,3,4
229 DATA 6,4,1,6,2,0,1,1,2,2,6,4,3,3,8,3,2,2,2,4,0,1,0,6,6,2,3,3,7,3,2,7,6,3,4
230 DATA 8,4,8,4,8,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,8,1,0,6,6,2,2,2,6,9,2,7,7,3,2
231 DATA 5,4,2,4,2,0,5,1,2,2,2,5,3,3,6,3,2,5,2,4,0,1,0,6,6,2,5,2,7,9,2,7,6,3,2
232 DATA 2,4,5,4,2,0,1,5,2,2,2,4,3,3,6,3,2,2,2,4,7,1,0,9,6,2,2,2,7,9,2,7,9,3,5
233 DATA 7,4,4,4,2,7,5,1,2,2,0,3,3,3,6,3,5,2,2,5,0,1,0,6,6,2,3,2,7,9,2,5,6,3,4
234 DATA 9,8,1,4,2,0,1,3,2,2,0,4,3,3,6,3,8,2,2,4,0,1,0,8,6,2,2,2,7,9,2,7,6,3,7
235 DATA 8,4,7,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,8,4,8,1,0,6,6,2,8,2,4,9,2,7,6,3,8
236 DATA 6,4,7,4,2,0,1,6,2,2,0,4,3,3,7,3,7,2,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,1
237 DATA 4,5,1,4,2,0,5,1,2,2,4,4,3,3,6,3,2,4,2,4,0,1,0,4,6,2,2,2,7,9,2,4,6,3,5
238 DATA 5,3,4,4,2,0,1,3,2,4,0,4,3,3,6,3,2,3,2,4,0,9,0,4,6,2,4,2,7,9,2,7,6,3,9
239 DATA 4,6,1,4,2,0,1,4,2,4,0,4,6,3,6,3,2,4,5,4,0,1,0,6,6,2,6,2,7,9,2,7,5,3,6
240 DATA 5,4,6,5,2,0,1,6,2,4,0,4,3,4,6,3,2,6,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,0
241 DATA 7,4,1,4,2,0,1,7,2,2,0,4,7,3,6,3,2,7,2,4,0,1,0,6,7,2,7,2,7,9,2,7,6,7,5
242 DATA 9,7,1,4,5,0,1,1,7,2,0,4,3,3,9
1065 FOR JJJJ=-32000 TO 32000
1074 RANDOMIZE JJJJ
1076 M=-32000
1085 FOR I=1 TO 100
1088 A(I)=FIX(RND*7)
1089 NEXT I
1126 IMAR=10+FIX(RND*2000)
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 100
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*100)
1234 X(IJL)=FIX(RND*7)
1533 FOR IX=1 TO 99
1534 FOR JX=IX+1 TO 100
1542 IF X(IX)=X(JX) THEN TM(IX,JX)=HR(IX,JX) ELSE TM(IX,JX)=0
1545 NEXT JX
1547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 99
1614 FOR IR2=IR1+1 TO 100
1616 SUMTL=SUMTL+TM(IR1,IR2)
1617 NEXT IR2
1619 NEXT IR1
1645 P=-SUMTL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 100
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 1128
1670 NEXT I
1890 IF M>-1300 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)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1928 PRINT A(81),A(82),A(83),A(84),A(85)
1929 PRINT A(86),A(87),A(88),A(89),A(90)
1930 PRINT A(91),A(92),A(93),A(94),A(95)
1931 PRINT A(96),A(97),A(98),A(99),A(100)
1937 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced in 20 hours of running are presented below. Only the candidate solution at JJJJ=-31786 is presented in full; each of the other candidate solutions below is briefly presented with its line
1937.

4 4 5 5 6
0 2 4 4 3
0 3 0 3 4
6 2 0 6 0
5 4 6 3 5
3 1 5 4 5
3 1 5 0 3
4 2 5 5 2
2 2 6 3 2
2 3 0 6 4
2 3 0 6 0
1 4 6 5 0
1 1 2 4 1
2 1 0 0 3
4 3 5 5 1
1 0 4 2 6
0 5 6 3 4
3 6 6 2 1
1 6 1 4 0
1 1 0 4 5
-1261 -31786

-1292 -31592

-1299 -31580

-1292 -31485

-1276 -31469

Interpreted in accordance with line 1912 through line 1937, these candidate solutions were produced in 20 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

Reference

Carlson, R. C., and G. L. Nemhauser, "Scheduling to Minimize Interaction Cost," Operations Research 14, 52-58 (1966).

An IP Computer Program Applied to a One-Dimensional Space Allocation Problem, Second Edition

An Integer-Programming Computer Program Applied to a One-Dimensional Space
Allocation Problem, Second Edition

Jsun Yui Wong

The computer program listed below seeks to solve Problem S8 of Amaral (2006),
which is a problem from Simmons (1969). In order to have integer locations, the
department lengths used in the computer program below have been made twice as
long as the given department lengths.

0 DEFINT A-Z
15 DIM X(11),A(11)
16 DIM TM(24,24),HR(24,24),HS(24,24)
21 FOR IW=1 TO 7
23 FOR JW=IW+1 TO 8
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
32 DATA 5,6,7,8,5,9,6,7,8,9,6,10,7,9,10,7,11,8,11,8,12,9,9,13,10,10,7,11
41 FOR IZ=1 TO 7
43 FOR JZ=IZ+1 TO 8
46 READ HS(IZ,JZ)
48 NEXT JZ
49 NEXT IZ
52 DATA 6,4,1,7,3,5,0,1,2,5,2,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-32000
85 FOR II=1 TO 8
88 A(II)=RND*99
89 NEXT II
126 IMAR=10+FIX(RND*2000)
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)
234 X(IJL)=RND*99
533 FOR IX=1 TO 7
534 FOR JX=IX+1 TO 8
543 IF ABS(X(IX)-X(JX))-HR(IX,JX)<-.0001 THEN TM(IX,JX)=1000 ELSE TM(IX,JX)=0
545 NEXT JX
547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 7
1614 FOR IR2=IR1+1 TO 8
1616 SUMTL=SUMTL+TM(IR1,IR2)
1617 NEXT IR2
1619 NEXT IR1
1631 SUMUL=0
1632 FOR IS1=1 TO 7
1634 FOR IS2=IS1+1 TO 8
1636 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1637 NEXT IS2
1639 NEXT IS1
1645 P=-SUMUL-SUMTL
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>-1605 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 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, and the best candidate solutions through JJJJ=-21042 are presented below. What immediately follows is a manual copy from the computer screen.

67 72 49 26 59
34 82 41 -1602 -31520

38 33 56 79 46
71 23 64 -1602 -25855

60 65 42 19 52
27 75 34 -1602 -25642

19 14 37 60 27
52 4 45 -1602 -22630

54 59 36 13 46
21 69 28 -1602 -22263

62 67 44 21 54
29 77 36 -1602 -22006

75 80 57 34 67
42 90 49 -1602 -21959

70 75 52 29 62
37 85 44 -1602 -21042

1602 is optimal. Interpreted in accordance with line 1912 and line 1914, the output through JJJJ=-21042 was produced in three hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, A. R. S., "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518 (2006).

Simmons, D. M., "One-dimensional space allocation: an ordering algorithm," Operations Research 17, 812-826 (1969).