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