Jsun Yui Wong
The computer program listed below seeks to solve the 15-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)=4:TBM(1,6)=1:TBM(1,7)=2:TBM(1,8)=3:TBM(1,9)=4:TBM(1,10)=5
12 TBM(1,11)=2:TBM(1,12)=3:TBM(1,13)=4:TBM(1,14)=5:TBM(1,15)=6
13 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=3:TBM(2,6)=2:TBM(2,7)=1:TBM(2,8)=2:TBM(2,9)=3:TBM(2,10)=4
14 TBM(2,11)=3:TBM(2,12)=2:TBM(2,13)=3:TBM(2,14)=4:TBM(2,15)=5
15 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=3:TBM(3,7)=2:TBM(3,8)=1:TBM(3,9)=2:TBM(3,10)=3
16 TBM(3,11)=4:TBM(3,12)=3:TBM(3,13)=2:TBM(3,14)=3:TBM(3,15)=4
17 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=1:TBM(4,6)=4:TBM(4,7)=3:TBM(4,8)=2:TBM(4,9)=1:TBM(4,10)=2
18 TBM(4,11)=5:TBM(4,12)=4:TBM(4,13)=3:TBM(4,14)=2:TBM(4,15)=3
19 TBM(5,1)=4:TBM(5,2)=3:TBM(5,3)=2:TBM(5,4)=1:TBM(5,5)=999:TBM(5,6)=5:TBM(5,7)=4:TBM(5,8)=3:TBM(5,9)=2:TBM(5,10)=1
20 TBM(5,11)=6:TBM(5,12)=5:TBM(5,13)=4:TBM(5,14)=3:TBM(5,15)=2
21 TBM(6,1)=1:TBM(6,2)=2:TBM(6,3)=3:TBM(6,4)=4:TBM(6,5)=5:TBM(6,6)=999:TBM(6,7)=1:TBM(6,8)=2:TBM(6,9)=3:TBM(6,10)=4
22 TBM(6,11)=1:TBM(6,12)=2:TBM(6,13)=3:TBM(6,14)=4:TBM(6,15)=5
23 TBM(7,1)=2:TBM(7,2)=1:TBM(7,3)=2:TBM(7,4)=3:TBM(7,5)=4:TBM(7,6)=1:TBM(7,7)=999:TBM(7,8)=1:TBM(7,9)=2:TBM(7,10)=3
24 TBM(7,11)=2:TBM(7,12)=1:TBM(7,13)=2:TBM(7,14)=3:TBM(7,15)=4
25 TBM(8,1)=3:TBM(8,2)=2:TBM(8,3)=1:TBM(8,4)=2:TBM(8,5)=3:TBM(8,6)=2:TBM(8,7)=1:TBM(8,8)=999:TBM(8,9)=1:TBM(8,10)=2
26 TBM(8,11)=3:TBM(8,12)=2:TBM(8,13)=1:TBM(8,14)=2:TBM(8,15)=3
27 TBM(9,1)=4:TBM(9,2)=3:TBM(9,3)=2:TBM(9,4)=1:TBM(9,5)=2:TBM(9,6)=3:TBM(9,7)=2:TBM(9,8)=1:TBM(9,9)=999:TBM(9,10)=1
28 TBM(9,11)=4:TBM(9,12)=3:TBM(9,13)=2:TBM(9,14)=1:TBM(9,15)=2
29 TBM(10,1)=5:TBM(10,2)=4:TBM(10,3)=3:TBM(10,4)=2:TBM(10,5)=1:TBM(10,6)=4:TBM(10,7)=3:TBM(10,8)=2:TBM(10,9)=1:TBM(10,10)=999
30 TBM(10,11)=5:TBM(10,12)=4:TBM(10,13)=3:TBM(10,14)=2:TBM(10,15)=1
31 TBM(11,1)=2:TBM(11,2)=3:TBM(11,3)=4:TBM(11,4)=5:TBM(11,5)=6:TBM(11,6)=1:TBM(11,7)=2:TBM(11,8)=3:TBM(11,9)=4:TBM(11,10)=5
32 TBM(11,11)=999:TBM(11,12)=1:TBM(11,13)=2:TBM(11,14)=3:TBM(11,15)=4
33 TBM(12,1)=3:TBM(12,2)=2:TBM(12,3)=3:TBM(12,4)=4:TBM(12,5)=5:TBM(12,6)=2:TBM(12,7)=1:TBM(12,8)=2:TBM(12,9)=3:TBM(12,10)=4
34 TBM(12,11)=1:TBM(12,12)=999:TBM(12,13)=1:TBM(12,14)=2:TBM(12,15)=3
35 TBM(13,1)=4:TBM(13,2)=3:TBM(13,3)=2:TBM(13,4)=3:TBM(13,5)=4:TBM(13,6)=3:TBM(13,7)=2:TBM(13,8)=1:TBM(13,9)=2:TBM(13,10)=3
36 TBM(13,11)=2:TBM(13,12)=1:TBM(13,13)=999:TBM(13,14)=1:TBM(13,15)=2
37 TBM(14,1)=5:TBM(14,2)=4:TBM(14,3)=3:TBM(14,4)=2:TBM(14,5)=3:TBM(14,6)=4:TBM(14,7)=3:TBM(14,8)=2:TBM(14,9)=1:TBM(14,10)=2
38 TBM(14,11)=3:TBM(14,12)=2:TBM(14,13)=1:TBM(14,14)=999:TBM(14,15)=1
39 TBM(15,1)=6:TBM(15,2)=5:TBM(15,3)=4:TBM(15,4)=3:TBM(15,5)=2:TBM(15,6)=5:TBM(15,7)=4:TBM(15,8)=3:TBM(15,9)=2:TBM(15,10)=1
40 TBM(15,11)=4:TBM(15,12)=3:TBM(15,13)=2:TBM(15,14)=1:TBM(15,15)=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
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 15
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*15)
331 IJN=1+FIX(RND*15)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=10*TBM(X(1),X(2))
402 T(2)=0*TBM(X(1),X(3))
403 T(3)=5*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)=1*TBM(X(1),X(7))
407 T(7)=2*TBM(X(1),X(8))
408 T(8)=2*TBM(X(1),X(9))
409 T(9)=2*TBM(X(1),X(10))
410 T(10)=2*TBM(X(1),X(11))
411 T(11)=0*TBM(X(1),X(12))
412 T(12)=4*TBM(X(1),X(13))
413 T(13)=0*TBM(X(1),X(14))
414 T(14)=0*TBM(X(1),X(15))
415 T(15)=1*TBM(X(2),X(3))
416 T(16)=3*TBM(X(2),X(4))
417 T(17)=2*TBM(X(2),X(5))
418 T(18)=2*TBM(X(2),X(6))
419 T(19)=2*TBM(X(2),X(7))
420 T(20)=3*TBM(X(2),X(8))
421 T(21)=2*TBM(X(2),X(9))
422 T(22)=0*TBM(X(2),X(10))
423 T(23)=2*TBM(X(2),X(11))
424 T(24)=0*TBM(X(2),X(12))
425 T(25)=10*TBM(X(2),X(13))
426 T(26)=5*TBM(X(2),X(14))
427 T(27)=0*TBM(X(2),X(15))
428 T(28)=10*TBM(X(3),X(4))
429 T(29)=2*TBM(X(3),X(5))
430 T(30)=0*TBM(X(3),X(6))
431 T(31)=2*TBM(X(3),X(7))
432 T(32)=5*TBM(X(3),X(8))
433 T(33)=4*TBM(X(3),X(9))
434 T(34)=5*TBM(X(3),X(10))
435 T(35)=2*TBM(X(3),X(11))
436 T(36)=2*TBM(X(3),X(12))
437 T(37)=5*TBM(X(3),X(13))
438 T(38)=5*TBM(X(3),X(14))
439 T(39)=5*TBM(X(3),X(15))
440 T(40)=1*TBM(X(4),X(5))
441 T(41)=1*TBM(X(4),X(6))
442 T(42)=5*TBM(X(4),X(7))
443 T(43)=0*TBM(X(4),X(8))
444 T(44)=0*TBM(X(4),X(9))
445 T(45)=2*TBM(X(4),X(10))
446 T(46)=1*TBM(X(4),X(11))
447 T(47)=0*TBM(X(4),X(12))
448 T(48)=2*TBM(X(4),X(13))
449 T(49)=5*TBM(X(4),X(14))
450 T(50)=0*TBM(X(4),X(15))
451 T(51)=3*TBM(X(5),X(6))
452 T(52)=5*TBM(X(5),X(7))
453 T(53)=5*TBM(X(5),X(8))
454 T(54)=5*TBM(X(5),X(9))
455 T(55)=1*TBM(X(5),X(10))
456 T(56)=0*TBM(X(5),X(11))
457 T(57)=3*TBM(X(5),X(12))
458 T(58)=0*TBM(X(5),X(13))
459 T(59)=5*TBM(X(5),X(14))
460 T(60)=5*TBM(X(5),X(15))
461 T(61)=2*TBM(X(6),X(7))
462 T(62)=2*TBM(X(6),X(8))
463 T(63)=1*TBM(X(6),X(9))
464 T(64)=5*TBM(X(6),X(10))
465 T(65)=0*TBM(X(6),X(11))
466 T(66)=0*TBM(X(6),X(12))
467 T(67)=2*TBM(X(6),X(13))
468 T(68)=5*TBM(X(6),X(14))
469 T(69)=10*TBM(X(6),X(15))
470 T(70)=6*TBM(X(7),X(8))
471 T(71)=0*TBM(X(7),X(9))
551 T(72)=1*TBM(X(7),X(10))
552 T(73)=5*TBM(X(7),X(11))
553 T(74)=5*TBM(X(7),X(12))
554 T(75)=5*TBM(X(7),X(13))
555 T(76)=1*TBM(X(7),X(14))
556 T(77)=0*TBM(X(7),X(15))
557 T(78)=5*TBM(X(8),X(9))
558 T(79)=2*TBM(X(8),X(10))
559 T(80)=10*TBM(X(8),X(11))
560 T(81)=0*TBM(X(8),X(12))
561 T(82)=5*TBM(X(8),X(13))
562 T(83)=0*TBM(X(8),X(14))
563 T(84)=0*TBM(X(8),X(15))
564 T(85)=0*TBM(X(9),X(10))
565 T(86)=10*TBM(X(9),X(11))
566 T(87)=5*TBM(X(9),X(12))
567 T(88)=10*TBM(X(9),X(13))
568 T(89)=0*TBM(X(9),X(14))
569 T(90)=2*TBM(X(9),X(15))
570 T(91)=0*TBM(X(10),X(11))
571 T(92)=4*TBM(X(10),X(12))
572 T(93)=0*TBM(X(10),X(13))
573 T(94)=0*TBM(X(10),X(14))
574 T(95)=5*TBM(X(10),X(15))
575 T(96)=5*TBM(X(11),X(12))
576 T(97)=0*TBM(X(11),X(13))
577 T(98)=5*TBM(X(11),X(14))
578 T(99)=0*TBM(X(11),X(15))
579 T(100)=3*TBM(X(12),X(13))
580 T(101)=3*TBM(X(12),X(14))
581 T(102)=0*TBM(X(12),X(15))
582 T(103)=10*TBM(X(13),X(14))
583 T(104)=2*TBM(X(13),X(15))
584 T(105)=4*TBM(X(14),X(15))
651 P1NEW=0
652 FOR KAU7=1 TO 105
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-576 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)
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 minute of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 2 7 6 14
13 9 4 5 11
10 15 3 8 12
-575 -31879
1 2 7 6 14
13 9 4 5 11
10 15 3 8 12
-575 -31878
11 12 7 6 4
3 9 14 15 1
10 5 13 8 2
-575 -31859
Interpreted in accordance with line 1912 through line 1927, the output through
JJJJ=-31859 was produced during the first minute 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).
