Jsun Yui Wong
The computer program listed below seeks to solve the 7-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(111)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=2:TBM(1,6)=3:TBM(1,7)=4
13 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=1:TBM(2,6)=2:TBM(2,7)=3
15 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=1:TBM(3,7)=2
17 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=3:TBM(4,6)=2:TBM(4,7)=1
19 TBM(5,1)=2:TBM(5,2)=1:TBM(5,3)=2:TBM(5,4)=3:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=2
21 TBM(6,1)=3:TBM(6,2)=2:TBM(6,3)=1:TBM(6,4)=2:TBM(6,5)=1:TBM(6,6)=999:TBM(6,7)=1
23 TBM(7,1)=4:TBM(7,2)=3:TBM(7,3)=2:TBM(7,4)=1:TBM(7,5)=2:TBM(7,6)=1:TBM(7,7)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7
126 IMAR=10+FIX(RND*100)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 7
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*7)
331 IJN=1+FIX(RND*7)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=5*TBM(X(1),X(2))
402 T(2)=2*TBM(X(1),X(3))
403 T(3)=4*TBM(X(1),X(4))
404 T(4)=1*TBM(X(1),X(5))
405 T(5)=0*TBM(X(1),X(6))
406 T(6)=0*TBM(X(1),X(7))
415 T(12)=3*TBM(X(2),X(3))
416 T(13)=0*TBM(X(2),X(4))
417 T(14)=2*TBM(X(2),X(5))
418 T(15)=2*TBM(X(2),X(6))
419 T(16)=2*TBM(X(2),X(7))
426 T(22)=1*TBM(X(3),X(4))
427 T(23)=0*TBM(X(3),X(5))
428 T(24)=2*TBM(X(3),X(6))
429 T(25)=5*TBM(X(3),X(7))
437 T(31)=5*TBM(X(4),X(5))
438 T(32)=2*TBM(X(4),X(6))
439 T(33)=2*TBM(X(4),X(7))
445 T(39)=10*TBM(X(5),X(6))
446 T(40)=0*TBM(X(5),X(7))
452 T(46)=5*TBM(X(6),X(7))
651 P1NEW=0
652 FOR KAU7=1 TO 46
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 7
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-76 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 3 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 2 5 3 4
7 6
-74 -31977
4 3 1 7 6
5 2
-74 -31970
4 3 1 7 6
5 2
-74 -31946
4 3 1 7 6
5 2
-74 -31944
7 6 5 4 3
2 1
-75 -31931
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31931 was produced during the first 3 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Nugent,C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1968).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly 18, 1-36 (1971).
Tuesday, August 25, 2009
A Computer Program for Solving Integer Programs
Jsun Yui Wong
The computer program listed below seeks to solve the 7-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(111)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=2:TBM(1,6)=3:TBM(1,7)=4
13 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=1:TBM(2,6)=2:TBM(2,7)=3
15 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=1:TBM(3,7)=2
17 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=3:TBM(4,6)=2:TBM(4,7)=1
19 TBM(5,1)=2:TBM(5,2)=1:TBM(5,3)=2:TBM(5,4)=3:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=2
21 TBM(6,1)=3:TBM(6,2)=2:TBM(6,3)=1:TBM(6,4)=2:TBM(6,5)=1:TBM(6,6)=999:TBM(6,7)=1
23 TBM(7,1)=4:TBM(7,2)=3:TBM(7,3)=2:TBM(7,4)=1:TBM(7,5)=2:TBM(7,6)=1:TBM(7,7)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7
126 IMAR=10+FIX(RND*100)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 7
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*7)
331 IJN=1+FIX(RND*7)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=5*TBM(X(1),X(2))
402 T(2)=2*TBM(X(1),X(3))
403 T(3)=4*TBM(X(1),X(4))
404 T(4)=1*TBM(X(1),X(5))
405 T(5)=0*TBM(X(1),X(6))
406 T(6)=0*TBM(X(1),X(7))
415 T(12)=3*TBM(X(2),X(3))
416 T(13)=0*TBM(X(2),X(4))
417 T(14)=2*TBM(X(2),X(5))
418 T(15)=2*TBM(X(2),X(6))
419 T(16)=2*TBM(X(2),X(7))
426 T(22)=1*TBM(X(3),X(4))
427 T(23)=0*TBM(X(3),X(5))
428 T(24)=2*TBM(X(3),X(6))
429 T(25)=5*TBM(X(3),X(7))
437 T(31)=5*TBM(X(4),X(5))
438 T(32)=2*TBM(X(4),X(6))
439 T(33)=2*TBM(X(4),X(7))
445 T(39)=10*TBM(X(5),X(6))
446 T(40)=0*TBM(X(5),X(7))
452 T(46)=5*TBM(X(6),X(7))
651 P1NEW=0
652 FOR KAU7=1 TO 46
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 7
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-76 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 3 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 2 5 3 4
7 6
-74 -31977
4 3 1 7 6
5 2
-74 -31970
4 3 1 7 6
5 2
-74 -31946
4 3 1 7 6
5 2
-74 -31944
7 6 5 4 3
2 1
-75 -31931
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31559 was produced during the first 3 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Nugent,C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1968).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
The computer program listed below seeks to solve the 7-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(111)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=2:TBM(1,6)=3:TBM(1,7)=4
13 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=1:TBM(2,6)=2:TBM(2,7)=3
15 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=1:TBM(3,7)=2
17 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=3:TBM(4,6)=2:TBM(4,7)=1
19 TBM(5,1)=2:TBM(5,2)=1:TBM(5,3)=2:TBM(5,4)=3:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=2
21 TBM(6,1)=3:TBM(6,2)=2:TBM(6,3)=1:TBM(6,4)=2:TBM(6,5)=1:TBM(6,6)=999:TBM(6,7)=1
23 TBM(7,1)=4:TBM(7,2)=3:TBM(7,3)=2:TBM(7,4)=1:TBM(7,5)=2:TBM(7,6)=1:TBM(7,7)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7
126 IMAR=10+FIX(RND*100)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 7
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*7)
331 IJN=1+FIX(RND*7)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=5*TBM(X(1),X(2))
402 T(2)=2*TBM(X(1),X(3))
403 T(3)=4*TBM(X(1),X(4))
404 T(4)=1*TBM(X(1),X(5))
405 T(5)=0*TBM(X(1),X(6))
406 T(6)=0*TBM(X(1),X(7))
415 T(12)=3*TBM(X(2),X(3))
416 T(13)=0*TBM(X(2),X(4))
417 T(14)=2*TBM(X(2),X(5))
418 T(15)=2*TBM(X(2),X(6))
419 T(16)=2*TBM(X(2),X(7))
426 T(22)=1*TBM(X(3),X(4))
427 T(23)=0*TBM(X(3),X(5))
428 T(24)=2*TBM(X(3),X(6))
429 T(25)=5*TBM(X(3),X(7))
437 T(31)=5*TBM(X(4),X(5))
438 T(32)=2*TBM(X(4),X(6))
439 T(33)=2*TBM(X(4),X(7))
445 T(39)=10*TBM(X(5),X(6))
446 T(40)=0*TBM(X(5),X(7))
452 T(46)=5*TBM(X(6),X(7))
651 P1NEW=0
652 FOR KAU7=1 TO 46
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 7
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-76 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 3 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 2 5 3 4
7 6
-74 -31977
4 3 1 7 6
5 2
-74 -31970
4 3 1 7 6
5 2
-74 -31946
4 3 1 7 6
5 2
-74 -31944
7 6 5 4 3
2 1
-75 -31931
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31559 was produced during the first 3 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Nugent,C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1968).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
A Computer Program for Solving Integer Programs
Jsun Yui Wong
The computer program listed below seeks to solve the 12-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(111)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=1:TBM(1,6)=2:TBM(1,7)=3:TBM(1,8)=4:TBM(1,9)=2:TBM(1,10)=3
12 TBM(1,11)=4:TBM(1,12)=5
13 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=2:TBM(2,6)=1:TBM(2,7)=2:TBM(2,8)=3:TBM(2,9)=3:TBM(2,10)=2
14 TBM(2,11)=3:TBM(2,12)=4
15 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=3:TBM(3,6)=2:TBM(3,7)=1:TBM(3,8)=2:TBM(3,9)=4:TBM(3,10)=3
16 TBM(3,11)=2:TBM(3,12)=3
17 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=4:TBM(4,6)=3:TBM(4,7)=2:TBM(4,8)=1:TBM(4,9)=5:TBM(4,10)=4
18 TBM(4,11)=3:TBM(4,12)=2
19 TBM(5,1)=1:TBM(5,2)=2:TBM(5,3)=3:TBM(5,4)=4:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=2:TBM(5,8)=3:TBM(5,9)=1:TBM(5,10)=2
20 TBM(5,11)=3:TBM(5,12)=4
21 TBM(6,1)=2:TBM(6,2)=1:TBM(6,3)=2:TBM(6,4)=3:TBM(6,5)=1:TBM(6,6)=999:TBM(6,7)=1:TBM(6,8)=2:TBM(6,9)=2:TBM(6,10)=1
22 TBM(6,11)=2:TBM(6,12)=3
23 TBM(7,1)=3:TBM(7,2)=2:TBM(7,3)=1:TBM(7,4)=2:TBM(7,5)=2:TBM(7,6)=1:TBM(7,7)=999:TBM(7,8)=1:TBM(7,9)=3:TBM(7,10)=2
24 TBM(7,11)=1:TBM(7,12)=2
25 TBM(8,1)=4:TBM(8,2)=3:TBM(8,3)=2:TBM(8,4)=1:TBM(8,5)=3:TBM(8,6)=2:TBM(8,7)=1:TBM(8,8)=999:TBM(8,9)=4:TBM(8,10)=3
26 TBM(8,11)=2:TBM(8,12)=1
27 TBM(9,1)=2:TBM(9,2)=3:TBM(9,3)=4:TBM(9,4)=5:TBM(9,5)=1:TBM(9,6)=2:TBM(9,7)=3:TBM(9,8)=4:TBM(9,9)=999:TBM(9,10)=1
28 TBM(9,11)=2:TBM(9,12)=3
29 TBM(10,1)=3:TBM(10,2)=2:TBM(10,3)=3:TBM(10,4)=4:TBM(10,5)=2:TBM(10,6)=1:TBM(10,7)=2:TBM(10,8)=3:TBM(10,9)=1:TBM(10,10)=999
30 TBM(10,11)=1:TBM(10,12)=2
31 TBM(11,1)=4:TBM(11,2)=3:TBM(11,3)=2:TBM(11,4)=3:TBM(11,5)=3:TBM(11,6)=2:TBM(11,7)=1:TBM(11,8)=2:TBM(11,9)=2:TBM(11,10)=1
32 TBM(11,11)=999:TBM(11,12)=1
33 TBM(12,1)=5:TBM(12,2)=4:TBM(12,3)=3:TBM(12,4)=2:TBM(12,5)=4:TBM(12,6)=3:TBM(12,7)=2:TBM(12,8)=1:TBM(12,9)=3:TBM(12,10)=2
34 TBM(12,11)=1:TBM(12,12)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
82 A(11)=11:A(12)=12
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 12
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*12)
331 IJN=1+FIX(RND*12)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=5*TBM(X(1),X(2))
402 T(2)=2*TBM(X(1),X(3))
403 T(3)=4*TBM(X(1),X(4))
404 T(4)=1*TBM(X(1),X(5))
405 T(5)=0*TBM(X(1),X(6))
406 T(6)=0*TBM(X(1),X(7))
407 T(7)=6*TBM(X(1),X(8))
408 T(8)=2*TBM(X(1),X(9))
409 T(9)=1*TBM(X(1),X(10))
410 T(10)=1*TBM(X(1),X(11))
411 T(11)=1*TBM(X(1),X(12))
415 T(12)=3*TBM(X(2),X(3))
416 T(13)=0*TBM(X(2),X(4))
417 T(14)=2*TBM(X(2),X(5))
418 T(15)=2*TBM(X(2),X(6))
419 T(16)=2*TBM(X(2),X(7))
420 T(17)=0*TBM(X(2),X(8))
421 T(18)=4*TBM(X(2),X(9))
422 T(19)=5*TBM(X(2),X(10))
423 T(20)=0*TBM(X(2),X(11))
424 T(21)=0*TBM(X(2),X(12))
426 T(22)=0*TBM(X(3),X(4))
427 T(23)=0*TBM(X(3),X(5))
428 T(24)=0*TBM(X(3),X(6))
429 T(25)=0*TBM(X(3),X(7))
430 T(26)=5*TBM(X(3),X(8))
431 T(27)=5*TBM(X(3),X(9))
432 T(28)=2*TBM(X(3),X(10))
433 T(29)=2*TBM(X(3),X(11))
434 T(30)=2*TBM(X(3),X(12))
437 T(31)=5*TBM(X(4),X(5))
438 T(32)=2*TBM(X(4),X(6))
439 T(33)=2*TBM(X(4),X(7))
440 T(34)=10*TBM(X(4),X(8))
441 T(35)=0*TBM(X(4),X(9))
442 T(36)=0*TBM(X(4),X(10))
443 T(37)=5*TBM(X(4),X(11))
444 T(38)=5*TBM(X(4),X(12))
445 T(39)=10*TBM(X(5),X(6))
446 T(40)=0*TBM(X(5),X(7))
447 T(41)=0*TBM(X(5),X(8))
448 T(42)=0*TBM(X(5),X(9))
449 T(43)=5*TBM(X(5),X(10))
450 T(44)=1*TBM(X(5),X(11))
451 T(45)=1*TBM(X(5),X(12))
452 T(46)=5*TBM(X(6),X(7))
453 T(47)=1*TBM(X(6),X(8))
454 T(48)=1*TBM(X(6),X(9))
455 T(49)=5*TBM(X(6),X(10))
456 T(50)=4*TBM(X(6),X(11))
457 T(51)=0*TBM(X(6),X(12))
458 T(52)=10*TBM(X(7),X(8))
459 T(53)=5*TBM(X(7),X(9))
460 T(54)=2*TBM(X(7),X(10))
461 T(55)=3*TBM(X(7),X(11))
462 T(56)=3*TBM(X(7),X(12))
463 T(57)=0*TBM(X(8),X(9))
464 T(58)=0*TBM(X(8),X(10))
465 T(59)=5*TBM(X(8),X(11))
466 T(60)=0*TBM(X(8),X(12))
467 T(61)=0*TBM(X(9),X(10))
468 T(62)=10*TBM(X(9),X(11))
469 T(63)=10*TBM(X(9),X(12))
470 T(64)=5*TBM(X(10),X(11))
471 T(65)=0*TBM(X(10),X(12))
472 T(66)=2*TBM(X(11),X(12))
651 P1NEW=0
652 FOR KAU7=1 TO 66
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 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)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 7 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
5 1 9 8 4
3 11 7 10 2
6 12
-289 -31975
5 1 9 8 4
3 11 7 10 2
6 12
-289 -31631
5 1 9 8 4
3 11 7 10 2
6 12
-289 -30853
5 1 9 8 4
3 11 7 10 2
6 12
-289 -30792
5 9 1 8 12
11 3 7 2 10
6 4
-289 -30035
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-30035 was produced during the first 7 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Nugent, C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1968).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
The computer program listed below seeks to solve the 12-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(111)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=1:TBM(1,6)=2:TBM(1,7)=3:TBM(1,8)=4:TBM(1,9)=2:TBM(1,10)=3
12 TBM(1,11)=4:TBM(1,12)=5
13 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=2:TBM(2,6)=1:TBM(2,7)=2:TBM(2,8)=3:TBM(2,9)=3:TBM(2,10)=2
14 TBM(2,11)=3:TBM(2,12)=4
15 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=3:TBM(3,6)=2:TBM(3,7)=1:TBM(3,8)=2:TBM(3,9)=4:TBM(3,10)=3
16 TBM(3,11)=2:TBM(3,12)=3
17 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=4:TBM(4,6)=3:TBM(4,7)=2:TBM(4,8)=1:TBM(4,9)=5:TBM(4,10)=4
18 TBM(4,11)=3:TBM(4,12)=2
19 TBM(5,1)=1:TBM(5,2)=2:TBM(5,3)=3:TBM(5,4)=4:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=2:TBM(5,8)=3:TBM(5,9)=1:TBM(5,10)=2
20 TBM(5,11)=3:TBM(5,12)=4
21 TBM(6,1)=2:TBM(6,2)=1:TBM(6,3)=2:TBM(6,4)=3:TBM(6,5)=1:TBM(6,6)=999:TBM(6,7)=1:TBM(6,8)=2:TBM(6,9)=2:TBM(6,10)=1
22 TBM(6,11)=2:TBM(6,12)=3
23 TBM(7,1)=3:TBM(7,2)=2:TBM(7,3)=1:TBM(7,4)=2:TBM(7,5)=2:TBM(7,6)=1:TBM(7,7)=999:TBM(7,8)=1:TBM(7,9)=3:TBM(7,10)=2
24 TBM(7,11)=1:TBM(7,12)=2
25 TBM(8,1)=4:TBM(8,2)=3:TBM(8,3)=2:TBM(8,4)=1:TBM(8,5)=3:TBM(8,6)=2:TBM(8,7)=1:TBM(8,8)=999:TBM(8,9)=4:TBM(8,10)=3
26 TBM(8,11)=2:TBM(8,12)=1
27 TBM(9,1)=2:TBM(9,2)=3:TBM(9,3)=4:TBM(9,4)=5:TBM(9,5)=1:TBM(9,6)=2:TBM(9,7)=3:TBM(9,8)=4:TBM(9,9)=999:TBM(9,10)=1
28 TBM(9,11)=2:TBM(9,12)=3
29 TBM(10,1)=3:TBM(10,2)=2:TBM(10,3)=3:TBM(10,4)=4:TBM(10,5)=2:TBM(10,6)=1:TBM(10,7)=2:TBM(10,8)=3:TBM(10,9)=1:TBM(10,10)=999
30 TBM(10,11)=1:TBM(10,12)=2
31 TBM(11,1)=4:TBM(11,2)=3:TBM(11,3)=2:TBM(11,4)=3:TBM(11,5)=3:TBM(11,6)=2:TBM(11,7)=1:TBM(11,8)=2:TBM(11,9)=2:TBM(11,10)=1
32 TBM(11,11)=999:TBM(11,12)=1
33 TBM(12,1)=5:TBM(12,2)=4:TBM(12,3)=3:TBM(12,4)=2:TBM(12,5)=4:TBM(12,6)=3:TBM(12,7)=2:TBM(12,8)=1:TBM(12,9)=3:TBM(12,10)=2
34 TBM(12,11)=1:TBM(12,12)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
82 A(11)=11:A(12)=12
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 12
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*12)
331 IJN=1+FIX(RND*12)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=5*TBM(X(1),X(2))
402 T(2)=2*TBM(X(1),X(3))
403 T(3)=4*TBM(X(1),X(4))
404 T(4)=1*TBM(X(1),X(5))
405 T(5)=0*TBM(X(1),X(6))
406 T(6)=0*TBM(X(1),X(7))
407 T(7)=6*TBM(X(1),X(8))
408 T(8)=2*TBM(X(1),X(9))
409 T(9)=1*TBM(X(1),X(10))
410 T(10)=1*TBM(X(1),X(11))
411 T(11)=1*TBM(X(1),X(12))
415 T(12)=3*TBM(X(2),X(3))
416 T(13)=0*TBM(X(2),X(4))
417 T(14)=2*TBM(X(2),X(5))
418 T(15)=2*TBM(X(2),X(6))
419 T(16)=2*TBM(X(2),X(7))
420 T(17)=0*TBM(X(2),X(8))
421 T(18)=4*TBM(X(2),X(9))
422 T(19)=5*TBM(X(2),X(10))
423 T(20)=0*TBM(X(2),X(11))
424 T(21)=0*TBM(X(2),X(12))
426 T(22)=0*TBM(X(3),X(4))
427 T(23)=0*TBM(X(3),X(5))
428 T(24)=0*TBM(X(3),X(6))
429 T(25)=0*TBM(X(3),X(7))
430 T(26)=5*TBM(X(3),X(8))
431 T(27)=5*TBM(X(3),X(9))
432 T(28)=2*TBM(X(3),X(10))
433 T(29)=2*TBM(X(3),X(11))
434 T(30)=2*TBM(X(3),X(12))
437 T(31)=5*TBM(X(4),X(5))
438 T(32)=2*TBM(X(4),X(6))
439 T(33)=2*TBM(X(4),X(7))
440 T(34)=10*TBM(X(4),X(8))
441 T(35)=0*TBM(X(4),X(9))
442 T(36)=0*TBM(X(4),X(10))
443 T(37)=5*TBM(X(4),X(11))
444 T(38)=5*TBM(X(4),X(12))
445 T(39)=10*TBM(X(5),X(6))
446 T(40)=0*TBM(X(5),X(7))
447 T(41)=0*TBM(X(5),X(8))
448 T(42)=0*TBM(X(5),X(9))
449 T(43)=5*TBM(X(5),X(10))
450 T(44)=1*TBM(X(5),X(11))
451 T(45)=1*TBM(X(5),X(12))
452 T(46)=5*TBM(X(6),X(7))
453 T(47)=1*TBM(X(6),X(8))
454 T(48)=1*TBM(X(6),X(9))
455 T(49)=5*TBM(X(6),X(10))
456 T(50)=4*TBM(X(6),X(11))
457 T(51)=0*TBM(X(6),X(12))
458 T(52)=10*TBM(X(7),X(8))
459 T(53)=5*TBM(X(7),X(9))
460 T(54)=2*TBM(X(7),X(10))
461 T(55)=3*TBM(X(7),X(11))
462 T(56)=3*TBM(X(7),X(12))
463 T(57)=0*TBM(X(8),X(9))
464 T(58)=0*TBM(X(8),X(10))
465 T(59)=5*TBM(X(8),X(11))
466 T(60)=0*TBM(X(8),X(12))
467 T(61)=0*TBM(X(9),X(10))
468 T(62)=10*TBM(X(9),X(11))
469 T(63)=10*TBM(X(9),X(12))
470 T(64)=5*TBM(X(10),X(11))
471 T(65)=0*TBM(X(10),X(12))
472 T(66)=2*TBM(X(11),X(12))
651 P1NEW=0
652 FOR KAU7=1 TO 66
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 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)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 7 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
5 1 9 8 4
3 11 7 10 2
6 12
-289 -31975
5 1 9 8 4
3 11 7 10 2
6 12
-289 -31631
5 1 9 8 4
3 11 7 10 2
6 12
-289 -30853
5 1 9 8 4
3 11 7 10 2
6 12
-289 -30792
5 9 1 8 12
11 3 7 2 10
6 4
-289 -30035
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-30035 was produced during the first 7 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Nugent, C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1968).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
An Integer Programming Computer Program Applied to a Quadratic Assignment Problem, Second Edition
Jsun Yui Wong
The computer program listed below seeks to solve the example in Land (1963).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466)
6 DIM TBM(11,11)
11 TBM(1,1)=999:TBM(1,2)=28:TBM(1,3)=33:TBM(1,4)=22:TBM(1,5)=20
12 TBM(2,1)=28:TBM(2,2)=999:TBM(2,3)=27:TBM(2,4)=40:TBM(2,5)=25
13 TBM(3,1)=33:TBM(3,2)=27:TBM(3,3)=999:TBM(3,4)=30:TBM(3,5)=15
14 TBM(4,1)=22:TBM(4,2)=40:TBM(4,3)=30:TBM(4,4)=999:TBM(4,5)=18
15 TBM(5,1)=20:TBM(5,2)=25:TBM(5,3)=15:TBM(5,4)=18:TBM(5,5)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5
126 IMAR=10+FIX(RND*0)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*5)
331 IJN=1+FIX(RND*5)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=10*TBM(X(1),X(2))
402 T(2)=3*TBM(X(1),X(3))
403 T(3)=1*TBM(X(1),X(4))
404 T(4)=15*TBM(X(1),X(5))
405 T(5)=6*TBM(X(2),X(3))
406 T(6)=8*TBM(X(2),X(4))
407 T(7)=4*TBM(X(2),X(5))
408 T(8)=0*TBM(X(3),X(4))
409 T(9)=10*TBM(X(3),X(5))
410 T(10)=3*TBM(X(4),X(5))
1589 P=-T(1)-T(2)-T(3)-T(4)-T(5)-T(6)-T(7)-T(8)-T(9)-T(10)
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-1348 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first second of running is presented below. (What immediately follows is a manual copy from the computer screen.)
4 1 3 2 5
-1347 -32000
4 1 3 2 5
-1347 -31998
4 1 3 2 5
-1347 -31993
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31993 was produced during the first second of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," OperationalResearch Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr. 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
The computer program listed below seeks to solve the example in Land (1963).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466)
6 DIM TBM(11,11)
11 TBM(1,1)=999:TBM(1,2)=28:TBM(1,3)=33:TBM(1,4)=22:TBM(1,5)=20
12 TBM(2,1)=28:TBM(2,2)=999:TBM(2,3)=27:TBM(2,4)=40:TBM(2,5)=25
13 TBM(3,1)=33:TBM(3,2)=27:TBM(3,3)=999:TBM(3,4)=30:TBM(3,5)=15
14 TBM(4,1)=22:TBM(4,2)=40:TBM(4,3)=30:TBM(4,4)=999:TBM(4,5)=18
15 TBM(5,1)=20:TBM(5,2)=25:TBM(5,3)=15:TBM(5,4)=18:TBM(5,5)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5
126 IMAR=10+FIX(RND*0)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*5)
331 IJN=1+FIX(RND*5)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=10*TBM(X(1),X(2))
402 T(2)=3*TBM(X(1),X(3))
403 T(3)=1*TBM(X(1),X(4))
404 T(4)=15*TBM(X(1),X(5))
405 T(5)=6*TBM(X(2),X(3))
406 T(6)=8*TBM(X(2),X(4))
407 T(7)=4*TBM(X(2),X(5))
408 T(8)=0*TBM(X(3),X(4))
409 T(9)=10*TBM(X(3),X(5))
410 T(10)=3*TBM(X(4),X(5))
1589 P=-T(1)-T(2)-T(3)-T(4)-T(5)-T(6)-T(7)-T(8)-T(9)-T(10)
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-1348 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first second of running is presented below. (What immediately follows is a manual copy from the computer screen.)
4 1 3 2 5
-1347 -32000
4 1 3 2 5
-1347 -31998
4 1 3 2 5
-1347 -31993
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31993 was produced during the first second of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," OperationalResearch Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr. 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
An Integer Programming Computer Program Applied to a Hospital Layout Problem
Jsun Yui Wong
The computer program listed below seeks to solve the hospital layout problem in Elshafei (1977).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(111)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=12:TBM(1,3)=36:TBM(1,4)=28:TBM(1,5)=52:TBM(1,6)=44:TBM(1,7)=110:TBM(1,8)=126:TBM(1,9)=94:TBM(1,10)=63
12 TBM(1,11)=130:TBM(1,12)=102:TBM(1,13)=65:TBM(1,14)=98:TBM(1,15)=132:TBM(1,16)=132:TBM(1,17)=126:TBM(1,18)=120:TBM(1,19)=126
13 TBM(2,1)=12:TBM(2,2)=999:TBM(2,3)=24:TBM(2,4)=75:TBM(2,5)=82:TBM(2,6)=75:TBM(2,7)=108:TBM(2,8)=70:TBM(2,9)=124:TBM(2,10)=86
14 TBM(2,11)=93:TBM(2,12)=106:TBM(2,13)=58:TBM(2,14)=124:TBM(2,15)=161:TBM(2,16)=161:TBM(2,17)=70:TBM(2,18)=64:TBM(2,19)=70
15 TBM(3,1)=36:TBM(3,2)=24:TBM(3,3)=999:TBM(3,4)=47:TBM(3,5)=71:TBM(3,6)=47:TBM(3,7)=110:TBM(3,8)=73:TBM(3,9)=126:TBM(3,10)=71
16 TBM(3,11)=95:TBM(3,12)=110:TBM(3,13)=46:TBM(3,14)=127:TBM(3,15)=163:TBM(3,16)=163:TBM(3,17)=73:TBM(3,18)=67:TBM(3,19)=73
17 TBM(4,1)=28:TBM(4,2)=75:TBM(4,3)=47:TBM(4,4)=999:TBM(4,5)=42:TBM(4,6)=34:TBM(4,7)=148:TBM(4,8)=111:TBM(4,9)=160:TBM(4,10)=52
18 TBM(4,11)=94:TBM(4,12)=148:TBM(4,13)=49:TBM(4,14)=117:TBM(4,15)=104:TBM(4,16)=109:TBM(4,17)=111:TBM(4,18)=105:TBM(4,19)=111
19 TBM(5,1)=52:TBM(5,2)=82:TBM(5,3)=71:TBM(5,4)=42:TBM(5,5)=999:TBM(5,6)=42:TBM(5,7)=125:TBM(5,8)=136:TBM(5,9)=102:TBM(5,10)=22
20 TBM(5,11)=73:TBM(5,12)=125:TBM(5,13)=32:TBM(5,14)=94:TBM(5,15)=130:TBM(5,16)=130:TBM(5,17)=136:TBM(5,18)=130:TBM(5,19)=136
21 TBM(6,1)=44:TBM(6,2)=75:TBM(6,3)=47:TBM(6,4)=34:TBM(6,5)=42:TBM(6,6)=999:TBM(6,7)=148:TBM(6,8)=111:TBM(6,9)=162:TBM(6,10)=52
22 TBM(6,11)=96:TBM(6,12)=148:TBM(6,13)=49:TBM(6,14)=117:TBM(6,15)=152:TBM(6,16)=152:TBM(6,17)=111:TBM(6,18)=105:TBM(6,19)=111
23 TBM(7,1)=110:TBM(7,2)=108:TBM(7,3)=110:TBM(7,4)=148:TBM(7,5)=125:TBM(7,6)=148:TBM(7,7)=999:TBM(7,8)=46:TBM(7,9)=46:TBM(7,10)=136
24 TBM(7,11)=47:TBM(7,12)=30:TBM(7,13)=108:TBM(7,14)=51:TBM(7,15)=79:TBM(7,16)=79:TBM(7,17)=46:TBM(7,18)=47:TBM(7,19)=41
25 TBM(8,1)=126:TBM(8,2)=70:TBM(8,3)=73:TBM(8,4)=111:TBM(8,5)=136:TBM(8,6)=111:TBM(8,7)=46:TBM(8,8)=999:TBM(8,9)=69:TBM(8,10)=141
26 TBM(8,11)=63:TBM(8,12)=46:TBM(8,13)=119:TBM(8,14)=68:TBM(8,15)=121:TBM(8,16)=121:TBM(8,17)=27:TBM(8,18)=24:TBM(8,19)=36
27 TBM(9,1)=94:TBM(9,2)=124:TBM(9,3)=126:TBM(9,4)=160:TBM(9,5)=102:TBM(9,6)=162:TBM(9,7)=46:TBM(9,8)=69:TBM(9,9)=999:TBM(9,10)=102
28 TBM(9,11)=34:TBM(9,12)=45:TBM(9,13)=84:TBM(9,14)=23:TBM(9,15)=80:TBM(9,16)=80:TBM(9,17)=69:TBM(9,18)=64:TBM(9,19)=51
29 TBM(10,1)=63:TBM(10,2)=86:TBM(10,3)=71:TBM(10,4)=52:TBM(10,5)=22:TBM(10,6)=52:TBM(10,7)=136:TBM(10,8)=141:TBM(10,9)=102:TBM(10,10)=999
30 TBM(10,11)=64:TBM(10,12)=118:TBM(10,13)=29:TBM(10,14)=95:TBM(10,15)=131:TBM(10,16)=131:TBM(10,17)=141:TBM(10,18)=135:TBM(10,19)=141
31 TBM(11,1)=130:TBM(11,2)=93:TBM(11,3)=95:TBM(11,4)=94:TBM(11,5)=73:TBM(11,6)=96:TBM(11,7)=47:TBM(11,8)=63:TBM(11,9)=34:TBM(11,10)=64
32 TBM(11,11)=999:TBM(11,12)=47:TBM(11,13)=56:TBM(11,14)=54:TBM(11,15)=94:TBM(11,16)=94:TBM(11,17)=63:TBM(11,18)=46:TBM(11,19)=24
33 TBM(12,1)=102:TBM(12,2)=106:TBM(12,3)=110:TBM(12,4)=148:TBM(12,5)=125:TBM(12,6)=148:TBM(12,7)=30:TBM(12,8)=46:TBM(12,9)=45:TBM(12,10)=118
34 TBM(12,11)=47:TBM(12,12)=999:TBM(12,13)=100:TBM(12,14)=51:TBM(12,15)=89:TBM(12,16)=89:TBM(12,17)=46:TBM(12,18)=40:TBM(12,19)=36
35 TBM(13,1)=659:TBM(13,2)=58:TBM(13,3)=46:TBM(13,4)=49:TBM(13,5)=32:TBM(13,6)=49:TBM(13,7)=108:TBM(13,8)=119:TBM(13,9)=84:TBM(13,10)=29
36 TBM(13,11)=56:TBM(13,12)=100:TBM(13,13)=999:TBM(13,14)=77:TBM(13,15)=113:TBM(13,16)=113:TBM(13,17)=119:TBM(13,18)=113:TBM(13,19)=119
37 TBM(14,1)=98:TBM(14,2)=124:TBM(14,3)=127:TBM(14,4)=117:TBM(14,5)=94:TBM(14,6)=117:TBM(14,7)=51:TBM(14,8)=68:TBM(14,9)=23:TBM(14,10)=95
38 TBM(14,11)=54:TBM(14,12)=51:TBM(14,13)=77:TBM(14,14)=999:TBM(14,15)=79:TBM(14,16)=79:TBM(14,17)=68:TBM(14,18)=62:TBM(14,19)=51
39 TBM(15,1)=132:TBM(15,2)=161:TBM(15,3)=163:TBM(15,4)=104:TBM(15,5)=130:TBM(15,6)=152:TBM(15,7)=79:TBM(15,8)=121:TBM(15,9)=80:TBM(15,10)=131
40 TBM(15,11)=94:TBM(15,12)=89:TBM(15,13)=113:TBM(15,14)=79:TBM(15,15)=999:TBM(15,16)=10:TBM(15,17)=113:TBM(15,18)=107:TBM(15,19)=119
41 TBM(16,1)=132:TBM(16,2)=161:TBM(16,3)=163:TBM(16,4)=109:TBM(16,5)=130:TBM(16,6)=152:TBM(16,7)=79:TBM(16,8)=121:TBM(16,9)=80:TBM(16,10)=131
42 TBM(16,11)=94:TBM(16,12)=89:TBM(16,13)=113:TBM(16,14)=79:TBM(16,15)=10:TBM(16,16)=999:TBM(16,17)=113:TBM(16,18)=107:TBM(16,19)=119
43 TBM(17,1)=126:TBM(17,2)=70:TBM(17,3)=73:TBM(17,4)=111:TBM(17,5)=136:TBM(17,6)=111:TBM(17,7)=46:TBM(17,8)=27:TBM(17,9)=69:TBM(17,10)=141
44 TBM(17,11)=63:TBM(17,12)=46:TBM(17,13)=119:TBM(17,14)=68:TBM(17,15)=113:TBM(17,16)=113:TBM(17,17)=999:TBM(17,18)=6:TBM(17,19)=24
45 TBM(18,1)=120:TBM(18,2)=64:TBM(18,3)=67:TBM(18,4)=105:TBM(18,5)=130:TBM(18,6)=105:TBM(18,7)=47:TBM(18,8)=24:TBM(18,9)=64:TBM(18,10)=135
46 TBM(18,11)=46:TBM(18,12)=40:TBM(18,13)=113:TBM(18,14)=62:TBM(18,15)=107:TBM(18,16)=107:TBM(18,17)=6:TBM(18,18)=999:TBM(18,19)=12
47 TBM(19,1)=126:TBM(19,2)=70:TBM(19,3)=73:TBM(19,4)=111:TBM(19,5)=136:TBM(19,6)=111:TBM(19,7)=41:TBM(19,8)=36:TBM(19,9)=51:TBM(19,10)=141
48 TBM(19,11)=24:TBM(19,12)=36:TBM(19,13)=119:TBM(19,14)=51:TBM(19,15)=119:TBM(19,16)=119:TBM(19,17)=24:TBM(19,18)=12:TBM(19,19)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
82 A(11)=11:A(12)=12:A(13)=13:A(14)=14:A(15)=15:A(16)=16:A(17)=17:A(18)=18:A(19)=19
126 IMAR=10+FIX(RND*3000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 19
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*19)
331 IJN=1+FIX(RND*19)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=76687!*TBM(X(1),X(2))
402 T(2)=415*TBM(X(1),X(4))
403 T(3)=545*TBM(X(1),X(5))
404 T(4)=819*TBM(X(1),X(6))
405 T(5)=135*TBM(X(1),X(7))
406 T(6)=1368*TBM(X(1),X(8))
407 T(7)=819*TBM(X(1),X(9))
408 T(8)=5630*TBM(X(1),X(10))
409 T(9)=3432*TBM(X(1),X(12))
410 T(10)=9082*TBM(X(1),X(13))
411 T(11)=1503*TBM(X(1),X(14))
412 T(12)=13732*TBM(X(1),X(17))
413 T(13)=1368*TBM(X(1),X(18))
414 T(14)=1783*TBM(X(1),X(19))
415 T(15)=40951!*TBM(X(2),X(3))
416 T(16)=4118*TBM(X(2),X(4))
417 T(17)=5767*TBM(X(2),X(5))
418 T(18)=2055*TBM(X(2),X(6))
419 T(19)=1917*TBM(X(2),X(7))
420 T(20)=2746*TBM(X(2),X(8))
421 T(21)=1097*TBM(X(2),X(9))
422 T(22)=5712*TBM(X(2),X(10))
423 T(23)=268*TBM(X(2),X(14))
424 T(24)=1373*TBM(X(2),X(16))
425 T(25)=268*TBM(X(2),X(17))
426 T(26)=3848*TBM(X(3),X(4))
427 T(27)=2524*TBM(X(3),X(5))
428 T(28)=3213*TBM(X(3),X(6))
429 T(29)=2072*TBM(X(3),X(7))
430 T(30)=4225*TBM(X(3),X(8))
431 T(31)=566*TBM(X(3),X(9))
432 T(32)=404*TBM(X(3),X(12))
433 T(33)=9372*TBM(X(3),X(13))
434 T(34)=972*TBM(X(3),X(15))
435 T(35)=13538*TBM(X(3),X(17))
436 T(36)=1368*TBM(X(3),X(18))
437 T(37)=256*TBM(X(4),X(5))
438 T(38)=829*TBM(X(4),X(10))
439 T(39)=128*TBM(X(4),X(11))
440 T(40)=47*TBM(X(5),X(9))
441 T(41)=1655*TBM(X(5),X(10))
442 T(42)=287*TBM(X(5),X(11))
443 T(43)=42*TBM(X(5),X(13))
444 T(44)=226*TBM(X(5),X(17))
445 T(45)=926*TBM(X(6),X(10))
446 T(46)=161*TBM(X(6),X(11))
447 T(47)=196*TBM(X(7),X(9))
448 T(48)=1538*TBM(X(7),X(10))
449 T(49)=196*TBM(X(7),X(11))
450 T(50)=301*TBM(X(8),X(11))
451 T(51)=1954*TBM(X(9),X(10))
452 T(52)=418*TBM(X(9),X(11))
453 T(53)=282*TBM(X(10),X(12))
454 T(54)=1686*TBM(X(11),X(12))
455 T(55)=226*TBM(X(11),X(17))
456 T(56)=99999!*TBM(X(15),X(16))
651 P1NEW=0
652 FOR KAU7=1 TO 56
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 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>-8700000! 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)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 5 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
17 18 19 11 12
9 3 14 1 2
10 13 7 5 15
16 8 6 4
-8606274 -31653
17 18 19 11 12
3 4 14 1 2
10 13 7 5 15
16 8 9 6
-8679132 -31568
17 18 19 11 3
14 4 7 1 2
10 13 12 5 15
16 8 9 6
-8679132 -31563
17 18 19 11 12
9 3 14 1 2
10 13 7 5 15
16 8 4 6
-8606274 -31559
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31559 was produced during the first 5 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr. 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
The computer program listed below seeks to solve the hospital layout problem in Elshafei (1977).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(111)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=12:TBM(1,3)=36:TBM(1,4)=28:TBM(1,5)=52:TBM(1,6)=44:TBM(1,7)=110:TBM(1,8)=126:TBM(1,9)=94:TBM(1,10)=63
12 TBM(1,11)=130:TBM(1,12)=102:TBM(1,13)=65:TBM(1,14)=98:TBM(1,15)=132:TBM(1,16)=132:TBM(1,17)=126:TBM(1,18)=120:TBM(1,19)=126
13 TBM(2,1)=12:TBM(2,2)=999:TBM(2,3)=24:TBM(2,4)=75:TBM(2,5)=82:TBM(2,6)=75:TBM(2,7)=108:TBM(2,8)=70:TBM(2,9)=124:TBM(2,10)=86
14 TBM(2,11)=93:TBM(2,12)=106:TBM(2,13)=58:TBM(2,14)=124:TBM(2,15)=161:TBM(2,16)=161:TBM(2,17)=70:TBM(2,18)=64:TBM(2,19)=70
15 TBM(3,1)=36:TBM(3,2)=24:TBM(3,3)=999:TBM(3,4)=47:TBM(3,5)=71:TBM(3,6)=47:TBM(3,7)=110:TBM(3,8)=73:TBM(3,9)=126:TBM(3,10)=71
16 TBM(3,11)=95:TBM(3,12)=110:TBM(3,13)=46:TBM(3,14)=127:TBM(3,15)=163:TBM(3,16)=163:TBM(3,17)=73:TBM(3,18)=67:TBM(3,19)=73
17 TBM(4,1)=28:TBM(4,2)=75:TBM(4,3)=47:TBM(4,4)=999:TBM(4,5)=42:TBM(4,6)=34:TBM(4,7)=148:TBM(4,8)=111:TBM(4,9)=160:TBM(4,10)=52
18 TBM(4,11)=94:TBM(4,12)=148:TBM(4,13)=49:TBM(4,14)=117:TBM(4,15)=104:TBM(4,16)=109:TBM(4,17)=111:TBM(4,18)=105:TBM(4,19)=111
19 TBM(5,1)=52:TBM(5,2)=82:TBM(5,3)=71:TBM(5,4)=42:TBM(5,5)=999:TBM(5,6)=42:TBM(5,7)=125:TBM(5,8)=136:TBM(5,9)=102:TBM(5,10)=22
20 TBM(5,11)=73:TBM(5,12)=125:TBM(5,13)=32:TBM(5,14)=94:TBM(5,15)=130:TBM(5,16)=130:TBM(5,17)=136:TBM(5,18)=130:TBM(5,19)=136
21 TBM(6,1)=44:TBM(6,2)=75:TBM(6,3)=47:TBM(6,4)=34:TBM(6,5)=42:TBM(6,6)=999:TBM(6,7)=148:TBM(6,8)=111:TBM(6,9)=162:TBM(6,10)=52
22 TBM(6,11)=96:TBM(6,12)=148:TBM(6,13)=49:TBM(6,14)=117:TBM(6,15)=152:TBM(6,16)=152:TBM(6,17)=111:TBM(6,18)=105:TBM(6,19)=111
23 TBM(7,1)=110:TBM(7,2)=108:TBM(7,3)=110:TBM(7,4)=148:TBM(7,5)=125:TBM(7,6)=148:TBM(7,7)=999:TBM(7,8)=46:TBM(7,9)=46:TBM(7,10)=136
24 TBM(7,11)=47:TBM(7,12)=30:TBM(7,13)=108:TBM(7,14)=51:TBM(7,15)=79:TBM(7,16)=79:TBM(7,17)=46:TBM(7,18)=47:TBM(7,19)=41
25 TBM(8,1)=126:TBM(8,2)=70:TBM(8,3)=73:TBM(8,4)=111:TBM(8,5)=136:TBM(8,6)=111:TBM(8,7)=46:TBM(8,8)=999:TBM(8,9)=69:TBM(8,10)=141
26 TBM(8,11)=63:TBM(8,12)=46:TBM(8,13)=119:TBM(8,14)=68:TBM(8,15)=121:TBM(8,16)=121:TBM(8,17)=27:TBM(8,18)=24:TBM(8,19)=36
27 TBM(9,1)=94:TBM(9,2)=124:TBM(9,3)=126:TBM(9,4)=160:TBM(9,5)=102:TBM(9,6)=162:TBM(9,7)=46:TBM(9,8)=69:TBM(9,9)=999:TBM(9,10)=102
28 TBM(9,11)=34:TBM(9,12)=45:TBM(9,13)=84:TBM(9,14)=23:TBM(9,15)=80:TBM(9,16)=80:TBM(9,17)=69:TBM(9,18)=64:TBM(9,19)=51
29 TBM(10,1)=63:TBM(10,2)=86:TBM(10,3)=71:TBM(10,4)=52:TBM(10,5)=22:TBM(10,6)=52:TBM(10,7)=136:TBM(10,8)=141:TBM(10,9)=102:TBM(10,10)=999
30 TBM(10,11)=64:TBM(10,12)=118:TBM(10,13)=29:TBM(10,14)=95:TBM(10,15)=131:TBM(10,16)=131:TBM(10,17)=141:TBM(10,18)=135:TBM(10,19)=141
31 TBM(11,1)=130:TBM(11,2)=93:TBM(11,3)=95:TBM(11,4)=94:TBM(11,5)=73:TBM(11,6)=96:TBM(11,7)=47:TBM(11,8)=63:TBM(11,9)=34:TBM(11,10)=64
32 TBM(11,11)=999:TBM(11,12)=47:TBM(11,13)=56:TBM(11,14)=54:TBM(11,15)=94:TBM(11,16)=94:TBM(11,17)=63:TBM(11,18)=46:TBM(11,19)=24
33 TBM(12,1)=102:TBM(12,2)=106:TBM(12,3)=110:TBM(12,4)=148:TBM(12,5)=125:TBM(12,6)=148:TBM(12,7)=30:TBM(12,8)=46:TBM(12,9)=45:TBM(12,10)=118
34 TBM(12,11)=47:TBM(12,12)=999:TBM(12,13)=100:TBM(12,14)=51:TBM(12,15)=89:TBM(12,16)=89:TBM(12,17)=46:TBM(12,18)=40:TBM(12,19)=36
35 TBM(13,1)=659:TBM(13,2)=58:TBM(13,3)=46:TBM(13,4)=49:TBM(13,5)=32:TBM(13,6)=49:TBM(13,7)=108:TBM(13,8)=119:TBM(13,9)=84:TBM(13,10)=29
36 TBM(13,11)=56:TBM(13,12)=100:TBM(13,13)=999:TBM(13,14)=77:TBM(13,15)=113:TBM(13,16)=113:TBM(13,17)=119:TBM(13,18)=113:TBM(13,19)=119
37 TBM(14,1)=98:TBM(14,2)=124:TBM(14,3)=127:TBM(14,4)=117:TBM(14,5)=94:TBM(14,6)=117:TBM(14,7)=51:TBM(14,8)=68:TBM(14,9)=23:TBM(14,10)=95
38 TBM(14,11)=54:TBM(14,12)=51:TBM(14,13)=77:TBM(14,14)=999:TBM(14,15)=79:TBM(14,16)=79:TBM(14,17)=68:TBM(14,18)=62:TBM(14,19)=51
39 TBM(15,1)=132:TBM(15,2)=161:TBM(15,3)=163:TBM(15,4)=104:TBM(15,5)=130:TBM(15,6)=152:TBM(15,7)=79:TBM(15,8)=121:TBM(15,9)=80:TBM(15,10)=131
40 TBM(15,11)=94:TBM(15,12)=89:TBM(15,13)=113:TBM(15,14)=79:TBM(15,15)=999:TBM(15,16)=10:TBM(15,17)=113:TBM(15,18)=107:TBM(15,19)=119
41 TBM(16,1)=132:TBM(16,2)=161:TBM(16,3)=163:TBM(16,4)=109:TBM(16,5)=130:TBM(16,6)=152:TBM(16,7)=79:TBM(16,8)=121:TBM(16,9)=80:TBM(16,10)=131
42 TBM(16,11)=94:TBM(16,12)=89:TBM(16,13)=113:TBM(16,14)=79:TBM(16,15)=10:TBM(16,16)=999:TBM(16,17)=113:TBM(16,18)=107:TBM(16,19)=119
43 TBM(17,1)=126:TBM(17,2)=70:TBM(17,3)=73:TBM(17,4)=111:TBM(17,5)=136:TBM(17,6)=111:TBM(17,7)=46:TBM(17,8)=27:TBM(17,9)=69:TBM(17,10)=141
44 TBM(17,11)=63:TBM(17,12)=46:TBM(17,13)=119:TBM(17,14)=68:TBM(17,15)=113:TBM(17,16)=113:TBM(17,17)=999:TBM(17,18)=6:TBM(17,19)=24
45 TBM(18,1)=120:TBM(18,2)=64:TBM(18,3)=67:TBM(18,4)=105:TBM(18,5)=130:TBM(18,6)=105:TBM(18,7)=47:TBM(18,8)=24:TBM(18,9)=64:TBM(18,10)=135
46 TBM(18,11)=46:TBM(18,12)=40:TBM(18,13)=113:TBM(18,14)=62:TBM(18,15)=107:TBM(18,16)=107:TBM(18,17)=6:TBM(18,18)=999:TBM(18,19)=12
47 TBM(19,1)=126:TBM(19,2)=70:TBM(19,3)=73:TBM(19,4)=111:TBM(19,5)=136:TBM(19,6)=111:TBM(19,7)=41:TBM(19,8)=36:TBM(19,9)=51:TBM(19,10)=141
48 TBM(19,11)=24:TBM(19,12)=36:TBM(19,13)=119:TBM(19,14)=51:TBM(19,15)=119:TBM(19,16)=119:TBM(19,17)=24:TBM(19,18)=12:TBM(19,19)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
82 A(11)=11:A(12)=12:A(13)=13:A(14)=14:A(15)=15:A(16)=16:A(17)=17:A(18)=18:A(19)=19
126 IMAR=10+FIX(RND*3000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 19
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*19)
331 IJN=1+FIX(RND*19)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=76687!*TBM(X(1),X(2))
402 T(2)=415*TBM(X(1),X(4))
403 T(3)=545*TBM(X(1),X(5))
404 T(4)=819*TBM(X(1),X(6))
405 T(5)=135*TBM(X(1),X(7))
406 T(6)=1368*TBM(X(1),X(8))
407 T(7)=819*TBM(X(1),X(9))
408 T(8)=5630*TBM(X(1),X(10))
409 T(9)=3432*TBM(X(1),X(12))
410 T(10)=9082*TBM(X(1),X(13))
411 T(11)=1503*TBM(X(1),X(14))
412 T(12)=13732*TBM(X(1),X(17))
413 T(13)=1368*TBM(X(1),X(18))
414 T(14)=1783*TBM(X(1),X(19))
415 T(15)=40951!*TBM(X(2),X(3))
416 T(16)=4118*TBM(X(2),X(4))
417 T(17)=5767*TBM(X(2),X(5))
418 T(18)=2055*TBM(X(2),X(6))
419 T(19)=1917*TBM(X(2),X(7))
420 T(20)=2746*TBM(X(2),X(8))
421 T(21)=1097*TBM(X(2),X(9))
422 T(22)=5712*TBM(X(2),X(10))
423 T(23)=268*TBM(X(2),X(14))
424 T(24)=1373*TBM(X(2),X(16))
425 T(25)=268*TBM(X(2),X(17))
426 T(26)=3848*TBM(X(3),X(4))
427 T(27)=2524*TBM(X(3),X(5))
428 T(28)=3213*TBM(X(3),X(6))
429 T(29)=2072*TBM(X(3),X(7))
430 T(30)=4225*TBM(X(3),X(8))
431 T(31)=566*TBM(X(3),X(9))
432 T(32)=404*TBM(X(3),X(12))
433 T(33)=9372*TBM(X(3),X(13))
434 T(34)=972*TBM(X(3),X(15))
435 T(35)=13538*TBM(X(3),X(17))
436 T(36)=1368*TBM(X(3),X(18))
437 T(37)=256*TBM(X(4),X(5))
438 T(38)=829*TBM(X(4),X(10))
439 T(39)=128*TBM(X(4),X(11))
440 T(40)=47*TBM(X(5),X(9))
441 T(41)=1655*TBM(X(5),X(10))
442 T(42)=287*TBM(X(5),X(11))
443 T(43)=42*TBM(X(5),X(13))
444 T(44)=226*TBM(X(5),X(17))
445 T(45)=926*TBM(X(6),X(10))
446 T(46)=161*TBM(X(6),X(11))
447 T(47)=196*TBM(X(7),X(9))
448 T(48)=1538*TBM(X(7),X(10))
449 T(49)=196*TBM(X(7),X(11))
450 T(50)=301*TBM(X(8),X(11))
451 T(51)=1954*TBM(X(9),X(10))
452 T(52)=418*TBM(X(9),X(11))
453 T(53)=282*TBM(X(10),X(12))
454 T(54)=1686*TBM(X(11),X(12))
455 T(55)=226*TBM(X(11),X(17))
456 T(56)=99999!*TBM(X(15),X(16))
651 P1NEW=0
652 FOR KAU7=1 TO 56
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 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>-8700000! 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)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 5 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
17 18 19 11 12
9 3 14 1 2
10 13 7 5 15
16 8 6 4
-8606274 -31653
17 18 19 11 12
3 4 14 1 2
10 13 7 5 15
16 8 9 6
-8679132 -31568
17 18 19 11 3
14 4 7 1 2
10 13 12 5 15
16 8 9 6
-8679132 -31563
17 18 19 11 12
9 3 14 1 2
10 13 7 5 15
16 8 4 6
-8606274 -31559
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31559 was produced during the first 5 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr. 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
Monday, August 24, 2009
An Integer Programming Computer Program Applied to a Quadratic Assignment Problem
Jsun Yui Wong
The computer program listed below seeks to solve the example in Land (1963).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466)
6 DIM TBM(11,11)
11 TBM(1,1)=999:TBM(1,2)=28:TBM(1,3)=33:TBM(1,4)=22:TBM(1,5)=20
12 TBM(2,1)=28:TBM(2,2)=999:TBM(2,3)=27:TBM(2,4)=40:TBM(2,5)=25
13 TBM(3,1)=33:TBM(3,2)=27:TBM(3,3)=999:TBM(3,4)=30:TBM(3,5)=15
14 TBM(4,1)=22:TBM(4,2)=40:TBM(4,3)=30:TBM(4,4)=999:TBM(4,5)=18
15 TBM(5,1)=20:TBM(5,2)=25:TBM(5,3)=15:TBM(5,4)=18:TBM(5,5)=999
51 A(1)=1
52 A(2)=2
53 A(3)=3
54 A(4)=4
55 A(5)=5
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
126 IMAR=10+FIX(RND*0)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*5)
331 IJN=1+FIX(RND*5)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=10*TBM(X(1),X(2))
402 T(2)=3*TBM(X(1),X(3))
403 T(3)=1*TBM(X(1),X(4))
404 T(4)=15*TBM(X(1),X(5))
405 T(5)=6*TBM(X(2),X(3))
406 T(6)=8*TBM(X(2),X(4))
407 T(7)=4*TBM(X(2),X(5))
408 T(8)=0*TBM(X(3),X(4))
409 T(9)=10*TBM(X(3),X(5))
410 T(10)=3*TBM(X(4),X(5))
1589 P=-T(1)-T(2)-T(3)-T(4)-T(5)-T(6)-T(7)-T(8)-T(9)-T(10)
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-1350 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first second of running is presented below. (What immediately follows is a manual copy from the computer screen.)
4 1 3 2 5
-1347 -32000
4 1 3 2 5
-1347 -31993
4 1 3 2 5
-1347 -31981
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31981 was produced during the first second of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr. 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
The computer program listed below seeks to solve the example in Land (1963).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466)
6 DIM TBM(11,11)
11 TBM(1,1)=999:TBM(1,2)=28:TBM(1,3)=33:TBM(1,4)=22:TBM(1,5)=20
12 TBM(2,1)=28:TBM(2,2)=999:TBM(2,3)=27:TBM(2,4)=40:TBM(2,5)=25
13 TBM(3,1)=33:TBM(3,2)=27:TBM(3,3)=999:TBM(3,4)=30:TBM(3,5)=15
14 TBM(4,1)=22:TBM(4,2)=40:TBM(4,3)=30:TBM(4,4)=999:TBM(4,5)=18
15 TBM(5,1)=20:TBM(5,2)=25:TBM(5,3)=15:TBM(5,4)=18:TBM(5,5)=999
51 A(1)=1
52 A(2)=2
53 A(3)=3
54 A(4)=4
55 A(5)=5
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
126 IMAR=10+FIX(RND*0)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*5)
331 IJN=1+FIX(RND*5)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=10*TBM(X(1),X(2))
402 T(2)=3*TBM(X(1),X(3))
403 T(3)=1*TBM(X(1),X(4))
404 T(4)=15*TBM(X(1),X(5))
405 T(5)=6*TBM(X(2),X(3))
406 T(6)=8*TBM(X(2),X(4))
407 T(7)=4*TBM(X(2),X(5))
408 T(8)=0*TBM(X(3),X(4))
409 T(9)=10*TBM(X(3),X(5))
410 T(10)=3*TBM(X(4),X(5))
1589 P=-T(1)-T(2)-T(3)-T(4)-T(5)-T(6)-T(7)-T(8)-T(9)-T(10)
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-1350 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first second of running is presented below. (What immediately follows is a manual copy from the computer screen.)
4 1 3 2 5
-1347 -32000
4 1 3 2 5
-1347 -31993
4 1 3 2 5
-1347 -31981
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31981 was produced during the first second of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr. 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
An Integer Programming Computer Program Applied to a Quadratic Assignment Problem
Jsun Yui Wong
The computer program listed below seeks to solve the example in Gavett and Plyter (1966) and in Pierce and Crowston (1971).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466)
6 DIM TBM(11,11)
11 TBM(1,1)=999:TBM(1,2)=6:TBM(1,3)=7:TBM(1,4)=2
12 TBM(2,1)=6:TBM(2,2)=999:TBM(2,3)=5:TBM(2,4)=6
13 TBM(3,1)=7:TBM(3,2)=5:TBM(3,3)=999:TBM(3,4)=1
14 TBM(4,1)=2:TBM(4,2)=6:TBM(4,3)=1:TBM(4,4)=999
51 A(1)=1
52 A(2)=2
53 A(3)=3
54 A(4)=4
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
126 IMAR=10+FIX(RND*0)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 4
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*4)
331 IJN=1+FIX(RND*4)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=28*TBM(X(1),X(2))
402 T(2)=25*TBM(X(1),X(3))
403 T(3)=13*TBM(X(1),X(4))
404 T(4)=15*TBM(X(2),X(3))
405 T(5)=4*TBM(X(2),X(4))
406 T(6)=23*TBM(X(3),X(4))
1589 P=-T(1)-T(2)-T(3)-T(4)-T(5)-T(6)
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-417 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first second of running is presented below. (What immediately follows is a manual copy from the computer screen.)
3 2 4 1
-416 -31998
4 1 3 2
-403 -31996
4 1 3 2
-403 -31995
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31995 was produced during the first second of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr. 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
The computer program listed below seeks to solve the example in Gavett and Plyter (1966) and in Pierce and Crowston (1971).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466)
6 DIM TBM(11,11)
11 TBM(1,1)=999:TBM(1,2)=6:TBM(1,3)=7:TBM(1,4)=2
12 TBM(2,1)=6:TBM(2,2)=999:TBM(2,3)=5:TBM(2,4)=6
13 TBM(3,1)=7:TBM(3,2)=5:TBM(3,3)=999:TBM(3,4)=1
14 TBM(4,1)=2:TBM(4,2)=6:TBM(4,3)=1:TBM(4,4)=999
51 A(1)=1
52 A(2)=2
53 A(3)=3
54 A(4)=4
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
126 IMAR=10+FIX(RND*0)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 4
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*4)
331 IJN=1+FIX(RND*4)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=28*TBM(X(1),X(2))
402 T(2)=25*TBM(X(1),X(3))
403 T(3)=13*TBM(X(1),X(4))
404 T(4)=15*TBM(X(2),X(3))
405 T(5)=4*TBM(X(2),X(4))
406 T(6)=23*TBM(X(3),X(4))
1589 P=-T(1)-T(2)-T(3)-T(4)-T(5)-T(6)
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-417 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first second of running is presented below. (What immediately follows is a manual copy from the computer screen.)
3 2 4 1
-416 -31998
4 1 3 2
-403 -31996
4 1 3 2
-403 -31995
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31995 was produced during the first second of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr. 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly, 18, 1-36 (1971).
Subscribe to:
Posts (Atom)