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.
Sunday, December 27, 2009
Friday, December 18, 2009
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.
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.
Wednesday, December 16, 2009
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).
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).
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).
Sunday, December 13, 2009
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.
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).
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).
Saturday, December 12, 2009
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).
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).
Subscribe to:
Posts (Atom)