A General Integer Programming Computer Program Applied to a 20-Facility Space Allocation Problem

Jsun Yui Wong
The problem considered is problem 7 of Heragu and Kusiak [3, p. 9]. The computer program listed below follows the mathematical formulation appearing on their page 4 [3] and on page 139 of Heragu [4]. The lengths of the twenty facilities are from their page 9 [3] and are used in line 561 through line 750 of the computer program below; the inter-facility flows are from Nugent et al. [5, p. 169] and are used in line 1238 through line 1317 of the computer program below.
The following computer program benefits from the computer programs of the present blog and the computer program of Conley [2, pp. 229-232].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
25 B(1)=0:B(2)=0:B(3)=0:B(4)=0:B(5)=0:B(6)=0
26 B(7)=0:B(8)=0:B(9)=0:B(10)=0:B(11)=0
27 B(12)=0:B(13)=0:B(14)=0:B(15)=0
31 B(16)=0:B(17)=0:B(18)=0:B(19)=0:B(20)=0
37 N(1)=99200!:N(2)=99200!:N(3)=99200!:N(4)=99200!:N(5)=99200!:N(6)=99200!
38 N(7)=99200!:N(8)=99200!:N(9)=99200!:N(10)=99200!:N(11)=92900!
39 N(12)=99200!:N(13)=99200!:N(14)=99200!:N(15)=99200!
41 N(16)=99200!:N(17)=99200!:N(18)=99200!:N(19)=99200!:N(20)=92900!
43 GOTO 61
51 FOR IOCTT=1 TO 20
53 N(IOCTT)=999999!
57 NEXT IOCTT
61 FOR KLQ=1 TO 20
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 20
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 13
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 20
111 REM
128 FOR I=1 TO 2
129 FOR KKQQ=1 TO 20
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 20
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
305 REM
306 KLPS=FIX(1+RND*60)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+20*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 461
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 461
355 X(JJ)=N(JJ)
461 IF RND>.1 GOTO 561
471 IOCT1=1+FIX(RND*20)
474 IOCT2=1+FIX(RND*20)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P(11)=ABS(X(1)-X(2))-11.5
562 P(12)=ABS(X(1)-X(3))-14.5
563 P(13)=ABS(X(1)-X(4))-11.5
564 P(14)=ABS(X(1)-X(5))-13.5
565 P(15)=ABS(X(1)-X(6))-11.5
566 P(16)=ABS(X(1)-X(7))-13.5
567 P(17)=ABS(X(1)-X(8))-12.5
568 P(18)=ABS(X(1)-X(9))-14.5
569 P(19)=ABS(X(1)-X(10))-13
570 P(20)=ABS(X(1)-X(11))-12.5
571 P(21)=ABS(X(1)-X(12))-11.5
572 P(22)=ABS(X(1)-X(13))-14.5
573 P(23)=ABS(X(1)-X(14))-11.5
574 P(24)=ABS(X(1)-X(15))-13.5
575 P(25)=ABS(X(1)-X(16))-11.5
576 P(26)=ABS(X(1)-X(17))-13.5
577 P(27)=ABS(X(1)-X(18))-12.5
578 P(28)=ABS(X(1)-X(19))-14.5
579 P(29)=ABS(X(1)-X(20))-13
580 P(30)=ABS(X(2)-X(3))-6
581 P(31)=ABS(X(2)-X(4))-3
582 P(32)=ABS(X(2)-X(5))-5
583 P(33)=ABS(X(2)-X(6))-3
584 P(34)=ABS(X(2)-X(7))-5
585 P(35)=ABS(X(2)-X(8))-4
586 P(36)=ABS(X(2)-X(9))-6
587 P(37)=ABS(X(2)-X(10))-4.5
588 P(38)=ABS(X(2)-X(11))-4
589 P(39)=ABS(X(2)-X(12))-3
590 P(40)=ABS(X(2)-X(13))-6
591 P(41)=ABS(X(2)-X(14))-3
592 P(42)=ABS(X(2)-X(15))-5
593 P(43)=ABS(X(2)-X(16))-3
594 P(44)=ABS(X(2)-X(17))-5
595 P(45)=ABS(X(2)-X(18))-4
596 P(46)=ABS(X(2)-X(19))-6
597 P(47)=ABS(X(2)-X(20))-4.5
598 P(48)=ABS(X(3)-X(4))-6
599 P(49)=ABS(X(3)-X(5))-8
600 P(50)=ABS(X(3)-X(6))-6
601 P(51)=ABS(X(3)-X(7))-8
602 P(52)=ABS(X(3)-X(8))-7
603 P(53)=ABS(X(3)-X(9))-9
604 P(54)=ABS(X(3)-X(10))-7.5
605 P(55)=ABS(X(3)-X(11))-7
606 P(56)=ABS(X(3)-X(12))-6
607 P(57)=ABS(X(3)-X(13))-9
608 P(58)=ABS(X(3)-X(14))-6
609 P(59)=ABS(X(3)-X(15))-8
610 P(60)=ABS(X(3)-X(16))-6
611 P(61)=ABS(X(3)-X(17))-8
612 P(62)=ABS(X(3)-X(18))-7
613 P(63)=ABS(X(3)-X(19))-9
614 P(64)=ABS(X(3)-X(20))-7.5
615 P(65)=ABS(X(4)-X(5))-5
616 P(66)=ABS(X(4)-X(6))-3
617 P(67)=ABS(X(4)-X(7))-5
618 P(68)=ABS(X(4)-X(8))-4
619 P(69)=ABS(X(4)-X(9))-6
620 P(70)=ABS(X(4)-X(10))-4.5
621 P(71)=ABS(X(4)-X(11))-4
622 P(72)=ABS(X(4)-X(12))-3
623 P(73)=ABS(X(4)-X(13))-6
624 P(74)=ABS(X(4)-X(14))-3
625 P(75)=ABS(X(4)-X(15))-5
626 P(76)=ABS(X(4)-X(16))-3
627 P(77)=ABS(X(4)-X(17))-5
628 P(78)=ABS(X(4)-X(18))-4
629 P(79)=ABS(X(4)-X(19))-6
630 P(80)=ABS(X(4)-X(20))-4.5
631 P(81)=ABS(X(5)-X(6))-5
632 P(82)=ABS(X(5)-X(7))-7
633 P(83)=ABS(X(5)-X(8))-6
634 P(84)=ABS(X(5)-X(9))-8
635 P(85)=ABS(X(5)-X(10))-6.5
636 P(86)=ABS(X(5)-X(11))-6
637 P(87)=ABS(X(5)-X(12))-5
638 P(88)=ABS(X(5)-X(13))-8
639 P(89)=ABS(X(5)-X(14))-5
640 P(90)=ABS(X(5)-X(15))-7
641 P(91)=ABS(X(5)-X(16))-5
642 P(92)=ABS(X(5)-X(17))-7
643 P(93)=ABS(X(5)-X(18))-6
644 P(94)=ABS(X(5)-X(19))-8
645 P(95)=ABS(X(5)-X(20))-6.5
646 P(96)=ABS(X(6)-X(7))-5
647 P(97)=ABS(X(6)-X(8))-4
648 P(98)=ABS(X(6)-X(9))-6
649 P(99)=ABS(X(6)-X(10))-4.5
650 P(100)=ABS(X(6)-X(11))-4
651 P(101)=ABS(X(6)-X(12))-3
652 P(102)=ABS(X(6)-X(13))-6
653 P(103)=ABS(X(6)-X(14))-3
654 P(104)=ABS(X(6)-X(15))-5
655 P(105)=ABS(X(6)-X(16))-3
656 P(106)=ABS(X(6)-X(17))-5
657 P(107)=ABS(X(6)-X(18))-4
658 P(108)=ABS(X(6)-X(19))-6
659 P(109)=ABS(X(6)-X(20))-4.5
660 P(110)=ABS(X(7)-X(8))-6
661 P(111)=ABS(X(7)-X(9))-8
662 P(112)=ABS(X(7)-X(10))-6.5
663 P(113)=ABS(X(7)-X(11))-6
664 P(114)=ABS(X(7)-X(12))-5
665 P(115)=ABS(X(7)-X(13))-8
666 P(116)=ABS(X(7)-X(14))-5
667 P(117)=ABS(X(7)-X(15))-7
668 P(118)=ABS(X(7)-X(16))-5
669 P(119)=ABS(X(7)-X(17))-7
670 P(120)=ABS(X(7)-X(18))-6
671 P(121)=ABS(X(7)-X(19))-8
672 P(122)=ABS(X(7)-X(20))-6.5
673 P(123)=ABS(X(8)-X(9))-7
674 P(124)=ABS(X(8)-X(10))-5.5
675 P(125)=ABS(X(8)-X(11))-5
676 P(126)=ABS(X(8)-X(12))-4
677 P(127)=ABS(X(8)-X(13))-7
678 P(128)=ABS(X(8)-X(14))-4
679 P(129)=ABS(X(8)-X(15))-6
680 P(130)=ABS(X(8)-X(16))-4
681 P(131)=ABS(X(8)-X(17))-6
682 P(132)=ABS(X(8)-X(18))-5
683 P(133)=ABS(X(8)-X(19))-7
684 P(134)=ABS(X(8)-X(20))-5.5
685 P(135)=ABS(X(9)-X(10))-7.5
686 P(136)=ABS(X(9)-X(11))-7
687 P(137)=ABS(X(9)-X(12))-6
688 P(138)=ABS(X(9)-X(13))-9
689 P(139)=ABS(X(9)-X(14))-6
690 P(140)=ABS(X(9)-X(15))-8
691 P(141)=ABS(X(9)-X(16))-6
692 P(142)=ABS(X(9)-X(17))-8
693 P(143)=ABS(X(9)-X(18))-7
694 P(144)=ABS(X(9)-X(19))-9
695 P(145)=ABS(X(9)-X(20))-7.5
696 P(146)=ABS(X(10)-X(11))-5.5
697 P(147)=ABS(X(10)-X(12))-4.5
698 P(148)=ABS(X(10)-X(13))-7.5
699 P(149)=ABS(X(10)-X(14))-4.5
700 P(150)=ABS(X(10)-X(15))-6.5
701 P(151)=ABS(X(10)-X(16))-4.5
702 P(152)=ABS(X(10)-X(17))-6.5
703 P(153)=ABS(X(10)-X(18))-5.5
704 P(154)=ABS(X(10)-X(19))-7.5
705 P(155)=ABS(X(10)-X(20))-6
706 P(156)=ABS(X(11)-X(12))-4
707 P(157)=ABS(X(11)-X(13))-7
708 P(158)=ABS(X(11)-X(14))-4
709 P(159)=ABS(X(11)-X(15))-6
710 P(160)=ABS(X(11)-X(16))-4
711 P(161)=ABS(X(11)-X(17))-6
712 P(162)=ABS(X(11)-X(18))-5
713 P(163)=ABS(X(11)-X(19))-7
714 P(164)=ABS(X(11)-X(20))-5.5
715 P(165)=ABS(X(12)-X(13))-6
716 P(166)=ABS(X(12)-X(14))-3
717 P(167)=ABS(X(12)-X(15))-5
718 P(168)=ABS(X(12)-X(16))-3
719 P(169)=ABS(X(12)-X(17))-5
720 P(170)=ABS(X(12)-X(18))-4
721 P(171)=ABS(X(12)-X(19))-6
722 P(172)=ABS(X(12)-X(20))-4.5
723 P(173)=ABS(X(13)-X(14))-6
724 P(174)=ABS(X(13)-X(15))-8
725 P(175)=ABS(X(13)-X(16))-6
726 P(176)=ABS(X(13)-X(17))-8
727 P(177)=ABS(X(13)-X(18))-7
728 P(178)=ABS(X(13)-X(19))-9
729 P(179)=ABS(X(13)-X(20))-7.5
730 P(180)=ABS(X(14)-X(15))-5
731 P(181)=ABS(X(14)-X(16))-3
732 P(182)=ABS(X(14)-X(17))-5
733 P(183)=ABS(X(14)-X(18))-4
734 P(184)=ABS(X(14)-X(19))-6
735 P(185)=ABS(X(14)-X(20))-4.5
736 P(186)=ABS(X(15)-X(16))-5
737 P(187)=ABS(X(15)-X(17))-7
738 P(188)=ABS(X(15)-X(18))-6
739 P(189)=ABS(X(15)-X(19))-8
740 P(190)=ABS(X(15)-X(20))-6.5
741 P(191)=ABS(X(16)-X(17))-5
742 P(192)=ABS(X(16)-X(18))-4
743 P(193)=ABS(X(16)-X(19))-6
744 P(194)=ABS(X(16)-X(20))-4.5
745 P(195)=ABS(X(17)-X(18))-6
746 P(196)=ABS(X(17)-X(19))-8
747 P(197)=ABS(X(17)-X(20))-6.5
748 P(198)=ABS(X(18)-X(19))-7
749 P(199)=ABS(X(18)-X(20))-5.5
750 P(200)=ABS(X(19)-X(20))-7.5
788 FOR INSI=11 TO 200
791 IF P(INSI)<0 THEN P(INSI)=P(INSI) ELSE P(INSI)=0
795 NEXT INSI
1111 PSUM=0
1115 FOR IOCT=11 TO 200
1118 PSUM=PSUM+P(IOCT)
1121 NEXT IOCT
1131 PS1=99*555555!*PSUM
1238 P11B=0*ABS(X(1)-X(2))+5*ABS(X(1)-X(3))+0*ABS(X(1)-X(4))+5*ABS(X(1)-X(5))+2*ABS(X(1)-X(6))+10*ABS(X(1)-X(7))+3*ABS(X(1)-X(8))+1*ABS(X(1)-X(9))+5*ABS(X(1)-X(10))+5*ABS(X(1)-X(11))
1239 P12B=5*ABS(X(1)-X(12))+0*ABS(X(1)-X(13))+0*ABS(X(1)-X(14))+5*ABS(X(1)-X(15))
1240 P13B=3*ABS(X(2)-X(3))+10*ABS(X(2)-X(4))+5*ABS(X(2)-X(5))+1*ABS(X(2)-X(6))+5*ABS(X(2)-X(7))+1*ABS(X(2)-X(8))+2*ABS(X(2)-X(9))+4*ABS(X(2)-X(10))+2*ABS(X(2)-X(11))
1241 P14B=5*ABS(X(2)-X(12))+0*ABS(X(2)-X(13))+10*ABS(X(2)-X(14))+10*ABS(X(2)-X(15))
1243 P15B=2*ABS(X(3)-X(4))+0*ABS(X(3)-X(5))+5*ABS(X(3)-X(6))+2*ABS(X(3)-X(7))+4*ABS(X(3)-X(8))+4*ABS(X(3)-X(9))+5*ABS(X(3)-X(10))+0*ABS(X(3)-X(11))
1244 P16B=0*ABS(X(3)-X(12))+0*ABS(X(3)-X(13))+5*ABS(X(3)-X(14))+1*ABS(X(3)-X(15))
1245 P17B=1*ABS(X(4)-X(5))+0*ABS(X(4)-X(6))+5*ABS(X(4)-X(7))+2*ABS(X(4)-X(8))+1*ABS(X(4)-X(9))+0*ABS(X(4)-X(10))+10*ABS(X(4)-X(11))
1246 P18B=2*ABS(X(4)-X(12))+2*ABS(X(4)-X(13))+0*ABS(X(4)-X(14))+2*ABS(X(4)-X(15))
1248 P19B=5*ABS(X(5)-X(6))+6*ABS(X(5)-X(7))+5*ABS(X(5)-X(8))+2*ABS(X(5)-X(9))+5*ABS(X(5)-X(10))+2*ABS(X(5)-X(11))+0*ABS(X(5)-X(12))+5*ABS(X(5)-X(13))+1*ABS(X(5)-X(14))+1*ABS(X(5)-X(15))
1249 P20B=5*ABS(X(6)-X(7))+2*ABS(X(6)-X(8))+1*ABS(X(6)-X(9))+6*ABS(X(6)-X(10))+0*ABS(X(6)-X(11))+0*ABS(X(6)-X(12))+10*ABS(X(6)-X(13))+0*ABS(X(6)-X(14))+2*ABS(X(6)-X(15))
1250 P21B=0*ABS(X(7)-X(8))+0*ABS(X(7)-X(9))+0*ABS(X(7)-X(10))+5*ABS(X(7)-X(11))+10*ABS(X(7)-X(12))+2*ABS(X(7)-X(13))+2*ABS(X(7)-X(14))+5*ABS(X(7)-X(15))
1251 P22B=1*ABS(X(8)-X(9))+1*ABS(X(8)-X(10))+10*ABS(X(8)-X(11))+10*ABS(X(8)-X(12))+2*ABS(X(8)-X(13))+0*ABS(X(8)-X(14))+10*ABS(X(8)-X(15))
1255 P23B=2*ABS(X(9)-X(10))+0*ABS(X(9)-X(11))+3*ABS(X(9)-X(12))+5*ABS(X(9)-X(13))+5*ABS(X(9)-X(14))+0*ABS(X(9)-X(15))
1257 P24B=5*ABS(X(10)-X(11))+5*ABS(X(10)-X(12))+0*ABS(X(10)-X(13))+5*ABS(X(10)-X(14))+1*ABS(X(10)-X(15))
1258 P25B=5*ABS(X(11)-X(12))+2*ABS(X(11)-X(13))+5*ABS(X(11)-X(14))+1*ABS(X(11)-X(15))
1259 P26B=2*ABS(X(12)-X(13))+10*ABS(X(12)-X(14))+5*ABS(X(12)-X(15))+2*ABS(X(13)-X(14))+2*ABS(X(13)-X(15))+5*ABS(X(14)-X(15))
1301 P27B=4*ABS(X(1)-X(16))+4*ABS(X(1)-X(17))+0*ABS(X(1)-X(18))+0*ABS(X(1)-X(18))+1*ABS(X(1)-X(20))
1302 P28B=3*ABS(X(2)-X(16))+0*ABS(X(2)-X(17))+5*ABS(X(2)-X(18))+10*ABS(X(2)-X(19))+5*ABS(X(2)-X(20))
1303 P29B=0*ABS(X(3)-X(16))+0*ABS(X(3)-X(17))+5*ABS(X(3)-X(18))+0*ABS(X(3)-X(19))+0*ABS(X(3)-X(20))
1304 P30B=1*ABS(X(4)-X(16))+5*ABS(X(4)-X(17))+2*ABS(X(4)-X(18))+5*ABS(X(4)-X(19))+5*ABS(X(4)-X(20))
1305 P31B=1*ABS(X(5)-X(16))+5*ABS(X(5)-X(17))+2*ABS(X(5)-X(18))+5*ABS(X(5)-X(19))+1*ABS(X(5)-X(20))
1306 P32B=0*ABS(X(6)-X(16))+1*ABS(X(6)-X(17))+0*ABS(X(6)-X(18))+1*ABS(X(6)-X(19))+5*ABS(X(6)-X(20))
1307 P33B=1*ABS(X(7)-X(16))+2*ABS(X(7)-X(17))+1*ABS(X(7)-X(18))+0*ABS(X(7)-X(19))+10*ABS(X(7)-X(20))
1308 P34B=2*ABS(X(8)-X(16))+5*ABS(X(8)-X(17))+2*ABS(X(8)-X(18))+2*ABS(X(8)-X(19))+10*ABS(X(8)-X(20))
1309 P35B=5*ABS(X(9)-X(16))+0*ABS(X(9)-X(17))+0*ABS(X(9)-X(18))+0*ABS(X(9)-X(19))+2*ABS(X(9)-X(20))
1310 P36B=0*ABS(X(10)-X(16))+0*ABS(X(10)-X(17))+5*ABS(X(10)-X(18))+5*ABS(X(10)-X(19))+2*ABS(X(10)-X(20))
1311 P37B=10*ABS(X(11)-X(16))+0*ABS(X(11)-X(17))+2*ABS(X(11)-X(18))+2*ABS(X(11)-X(19))+5*ABS(X(11)-X(20))
1312 P38B=0*ABS(X(12)-X(16))+1*ABS(X(12)-X(17))+1*ABS(X(12)-X(18))+2*ABS(X(12)-X(19))+5*ABS(X(12)-X(20))
1313 P39B=1*ABS(X(13)-X(16))+0*ABS(X(13)-X(17))+0*ABS(X(13)-X(18))+0*ABS(X(13)-X(19))+5*ABS(X(13)-X(20))
1314 P40B=5*ABS(X(14)-X(16))+1*ABS(X(14)-X(17))+5*ABS(X(14)-X(18))+5*ABS(X(14)-X(19))+0*ABS(X(14)-X(20))
1315 P41B=3*ABS(X(15)-X(16))+0*ABS(X(15)-X(17))+5*ABS(X(15)-X(18))+10*ABS(X(15)-X(19))+10*ABS(X(15)-X(20))
1316 P42B=0*ABS(X(16)-X(17))+0*ABS(X(16)-X(18))+2*ABS(X(16)-X(19))+0*ABS(X(16)-X(20))
1317 P43B=5*ABS(X(17)-X(18))+2*ABS(X(17)-X(19))+0*ABS(X(17)-X(20))+1*ABS(X(18)-X(19))+1*ABS(X(18)-X(20))+6*ABS(X(19)-X(20))
1445 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B+P21B+P22B+P23B+P24B+P25B+P26B
1447 P2=P27B+P28B+P29B+P30B+P31B+P32B+P33B+P34B+P35B+P36B+P37B+P38B+P39B+P40B+P41B+P42B+P43B
1448 P3=P1+P2
1449 REM
1450 P=-P3+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P3
1454 FOR KLX=1 TO 20
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1778 REM PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),M,PP1
1888 NEXT JJJ
1890 IF M>-16200 THEN 1916 ELSE 1999
1916 PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),M,PP1
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12),A(13),A(14),A(15)
1922 PRINT A(16),A(17),A(18),A(19),A(20)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and its best candidate solutions from JJJJ=-32000 through JJJJ=-31869 (in compressed form and to be interpreted in accordance with line 1916 through line 1922; copied manually from the computer monitor) are presented below.
-31994 31277.27 31353.78 31382.79 31342.78
31309.77 -15792.07 15792.07
31304.77 31316.77 31335.77 31391.79 31366.28
31346.78 31339.77 31298.77 31361.78 31329.77
31350.78 31290.77 31357.78 31373.79 31323.27
-31870 56521.45 56444.94 56415.94 56450.94
56491.95 -15718.27 15718.27
56486.95 56481.95 56469.95 56406.94 56437.44
56454.94 56465.95 56506.95 56441.94 56460.95
56447.94 56498.95 56422.94 56429.94 56475.45
In summary, this computer run produced candidate solutions with objective function value of 15792.07 at JJJJ=-31994, 15823 at JJJJ=-31980, 15718.27 at JJJJ=-31870, and 15993 at JJJJ=-31869.
The total time for the output above was obtained in 57 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower the corresponding compiler.
If one makes changes to the computer program above, such as a change of changing line 128 to, for example, 128 FOR I=1 TO 3, one may or may not obtain the best objective function value of the output above, 15718.27. For this problem, the optimal objective function value is 15549.0, Amaral [1]. Generally speaking, in order to increase the probability of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128, for example; instead of line 128, another line can be chosen. This multicomputer approach can mitigate the possible danger of missed optimality and can produce a usable solution faster than just running one computer.
References
[1] A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics, in press.
[2] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.
[3] S.S. Heragu, A. Kusiak, Efficient models for the facility layut problem, European Journal of Operational Research 53 (1991) 1-13.
[4] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[5] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[6] D.M. Simmons, One-dimensional space allocation: An ordering algorithm, Operations Research 17 (1969) 812-826.

A General Integer Programming Computer Program Applied to a 30-Facility Space Allocation Problem

Jsun Yui Wong
The problem considered is problem 8 of Heragu and Kusiak [3, p. 9]. The computer program listed below follows the mathematical formulation appearing on their page 4 [3] and on page 139 of Heragu [4]. The lengths of the thirty facilities are from their page 9 [3] and are used in line 561 through line 995 of the computer program below; the inter-facility flows are from Nugent et al. [5, p. 170] and are used in line 1238 through line 1347 of the computer program below.
The following computer program benefits from the computer programs of the present blog and the computer program of Conley [2, pp. 229-232]; the output is also presented here.
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(522)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
25 B(1)=0:B(2)=0:B(3)=0:B(4)=0:B(5)=0:B(6)=0
26 B(7)=0:B(8)=0:B(9)=0:B(10)=0:B(11)=0
27 B(12)=0:B(13)=0:B(14)=0:B(15)=0
31 B(16)=0:B(17)=0:B(18)=0:B(19)=0:B(20)=0
32 B(21)=0:B(22)=0:B(23)=0:B(24)=0:B(25)=0
33 B(26)=0:B(27)=0:B(28)=0:B(29)=0:B(30)=0
37 N(1)=99200!:N(2)=99200!:N(3)=99200!:N(4)=99200!:N(5)=99200!:N(6)=99200!
38 N(7)=99200!:N(8)=99200!:N(9)=99200!:N(10)=99200!:N(11)=92900!
39 N(12)=99200!:N(13)=99200!:N(14)=99200!:N(15)=99200!
41 N(16)=99200!:N(17)=99200!:N(18)=99200!:N(19)=99200!:N(20)=92900!
42 N(21)=99200!:N(22)=99200!:N(23)=99200!:N(24)=99200!:N(25)=92900!
43 N(26)=99200!:N(27)=99200!:N(28)=99200!:N(29)=99200!:N(30)=92900!
48 GOTO 61
51 FOR IOCTT=1 TO 20
53 N(IOCTT)=999999!
57 NEXT IOCTT
61 FOR KLQ=1 TO 30
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 30
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 13
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 30
111 REM
128 FOR I=1 TO 2
129 FOR KKQQ=1 TO 30
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 30
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
305 REM
306 KLPS=FIX(1+RND*90)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+30*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 461
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 461
355 X(JJ)=N(JJ)
461 IF RND>.1 GOTO 561
471 IOCT1=1+FIX(RND*30)
474 IOCT2=1+FIX(RND*30)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P(11)=ABS(X(1)-X(2))-6
562 P(12)=ABS(X(1)-X(3))-3
563 P(13)=ABS(X(1)-X(4))-5
564 P(14)=ABS(X(1)-X(5))-3
565 P(15)=ABS(X(1)-X(6))-5
566 P(16)=ABS(X(1)-X(7))-4
567 P(17)=ABS(X(1)-X(8))-6
568 P(18)=ABS(X(1)-X(9))-4.5
569 P(19)=ABS(X(1)-X(10))-4
570 P(20)=ABS(X(1)-X(11))-3
571 P(21)=ABS(X(1)-X(12))-6
572 P(22)=ABS(X(1)-X(13))-3
573 P(23)=ABS(X(1)-X(14))-5
574 P(24)=ABS(X(1)-X(15))-3
575 P(25)=ABS(X(1)-X(16))-5
576 P(26)=ABS(X(1)-X(17))-4
577 P(27)=ABS(X(1)-X(18))-6
578 P(28)=ABS(X(1)-X(19))-4.5
579 P(29)=ABS(X(1)-X(20))-4
580 P(30)=ABS(X(2)-X(3))-6
581 P(31)=ABS(X(2)-X(4))-8
582 P(32)=ABS(X(2)-X(5))-6
583 P(33)=ABS(X(2)-X(6))-8
584 P(34)=ABS(X(2)-X(7))-7
585 P(35)=ABS(X(2)-X(8))-9
586 P(36)=ABS(X(2)-X(9))-7.5
587 P(37)=ABS(X(2)-X(10))-7
588 P(38)=ABS(X(2)-X(11))-6
589 P(39)=ABS(X(2)-X(12))-9
590 P(40)=ABS(X(2)-X(13))-6
591 P(41)=ABS(X(2)-X(14))-8
592 P(42)=ABS(X(2)-X(15))-6
593 P(43)=ABS(X(2)-X(16))-8
594 P(44)=ABS(X(2)-X(17))-7
595 P(45)=ABS(X(2)-X(18))-9
596 P(46)=ABS(X(2)-X(19))-7.5
597 P(47)=ABS(X(2)-X(20))-7
598 P(48)=ABS(X(3)-X(4))-5
599 P(49)=ABS(X(3)-X(5))-3
600 P(50)=ABS(X(3)-X(6))-5
601 P(51)=ABS(X(3)-X(7))-4
602 P(52)=ABS(X(3)-X(8))-6
603 P(53)=ABS(X(3)-X(9))-4.5
604 P(54)=ABS(X(3)-X(10))-4
605 P(55)=ABS(X(3)-X(11))-3
606 P(56)=ABS(X(3)-X(12))-6
607 P(57)=ABS(X(3)-X(13))-3
608 P(58)=ABS(X(3)-X(14))-5
609 P(59)=ABS(X(3)-X(15))-3
610 P(60)=ABS(X(3)-X(16))-5
611 P(61)=ABS(X(3)-X(17))-4
612 P(62)=ABS(X(3)-X(18))-6
613 P(63)=ABS(X(3)-X(19))-4.5
614 P(64)=ABS(X(3)-X(20))-4
615 P(65)=ABS(X(4)-X(5))-5
616 P(66)=ABS(X(4)-X(6))-7
617 P(67)=ABS(X(4)-X(7))-6
618 P(68)=ABS(X(4)-X(8))-8
619 P(69)=ABS(X(4)-X(9))-6.5
620 P(70)=ABS(X(4)-X(10))-6
621 P(71)=ABS(X(4)-X(11))-5
622 P(72)=ABS(X(4)-X(12))-8
623 P(73)=ABS(X(4)-X(13))-5
624 P(74)=ABS(X(4)-X(14))-7
625 P(75)=ABS(X(4)-X(15))-5
626 P(76)=ABS(X(4)-X(16))-7
627 P(77)=ABS(X(4)-X(17))-6
628 P(78)=ABS(X(4)-X(18))-8
629 P(79)=ABS(X(4)-X(19))-6.5
630 P(80)=ABS(X(4)-X(20))-6
631 P(81)=ABS(X(5)-X(6))-5
632 P(82)=ABS(X(5)-X(7))-4
633 P(83)=ABS(X(5)-X(8))-6
634 P(84)=ABS(X(5)-X(9))-4.5
635 P(85)=ABS(X(5)-X(10))-4
636 P(86)=ABS(X(5)-X(11))-3
637 P(87)=ABS(X(5)-X(12))-6
638 P(88)=ABS(X(5)-X(13))-3
639 P(89)=ABS(X(5)-X(14))-5
640 P(90)=ABS(X(5)-X(15))-3
641 P(91)=ABS(X(5)-X(16))-5
642 P(92)=ABS(X(5)-X(17))-4
643 P(93)=ABS(X(5)-X(18))-6
644 P(94)=ABS(X(5)-X(19))-4.5
645 P(95)=ABS(X(5)-X(20))-4
646 P(96)=ABS(X(6)-X(7))-6
647 P(97)=ABS(X(6)-X(8))-8
648 P(98)=ABS(X(6)-X(9))-6.5
649 P(99)=ABS(X(6)-X(10))-6
650 P(100)=ABS(X(6)-X(11))-5
651 P(101)=ABS(X(6)-X(12))-8
652 P(102)=ABS(X(6)-X(13))-5
653 P(103)=ABS(X(6)-X(14))-7
654 P(104)=ABS(X(6)-X(15))-5
655 P(105)=ABS(X(6)-X(16))-7
656 P(106)=ABS(X(6)-X(17))-6
657 P(107)=ABS(X(6)-X(18))-8
658 P(108)=ABS(X(6)-X(19))-6.5
659 P(109)=ABS(X(6)-X(20))-6
660 P(110)=ABS(X(7)-X(8))-7
661 P(111)=ABS(X(7)-X(9))-5.5
662 P(112)=ABS(X(7)-X(10))-5
663 P(113)=ABS(X(7)-X(11))-4
664 P(114)=ABS(X(7)-X(12))-7
665 P(115)=ABS(X(7)-X(13))-4
666 P(116)=ABS(X(7)-X(14))-6
667 P(117)=ABS(X(7)-X(15))-4
668 P(118)=ABS(X(7)-X(16))-6
669 P(119)=ABS(X(7)-X(17))-5
670 P(120)=ABS(X(7)-X(18))-7
671 P(121)=ABS(X(7)-X(19))-5.5
672 P(122)=ABS(X(7)-X(20))-5
673 P(123)=ABS(X(8)-X(9))-7.5
674 P(124)=ABS(X(8)-X(10))-7
675 P(125)=ABS(X(8)-X(11))-6
676 P(126)=ABS(X(8)-X(12))-9
677 P(127)=ABS(X(8)-X(13))-6
678 P(128)=ABS(X(8)-X(14))-8
679 P(129)=ABS(X(8)-X(15))-6
680 P(130)=ABS(X(8)-X(16))-8
681 P(131)=ABS(X(8)-X(17))-7
682 P(132)=ABS(X(8)-X(18))-9
683 P(133)=ABS(X(8)-X(19))-7.5
684 P(134)=ABS(X(8)-X(20))-7
685 P(135)=ABS(X(9)-X(10))-5.5
686 P(136)=ABS(X(9)-X(11))-4.5
687 P(137)=ABS(X(9)-X(12))-7.5
688 P(138)=ABS(X(9)-X(13))-4.5
689 P(139)=ABS(X(9)-X(14))-6.5
690 P(140)=ABS(X(9)-X(15))-4.5
691 P(141)=ABS(X(9)-X(16))-6.5
692 P(142)=ABS(X(9)-X(17))-5.5
693 P(143)=ABS(X(9)-X(18))-7.5
694 P(144)=ABS(X(9)-X(19))-6
695 P(145)=ABS(X(9)-X(20))-5.5
696 P(146)=ABS(X(10)-X(11))-4
697 P(147)=ABS(X(10)-X(12))-7
698 P(148)=ABS(X(10)-X(13))-4
699 P(149)=ABS(X(10)-X(14))-6
700 P(150)=ABS(X(10)-X(15))-4
701 P(151)=ABS(X(10)-X(16))-6
702 P(152)=ABS(X(10)-X(17))-5
703 P(153)=ABS(X(10)-X(18))-7
704 P(154)=ABS(X(10)-X(19))-5.5
705 P(155)=ABS(X(10)-X(20))-5
706 P(156)=ABS(X(11)-X(12))-6
707 P(157)=ABS(X(11)-X(13))-3
708 P(158)=ABS(X(11)-X(14))-5
709 P(159)=ABS(X(11)-X(15))-3
710 P(160)=ABS(X(11)-X(16))-5
711 P(161)=ABS(X(11)-X(17))-4
712 P(162)=ABS(X(11)-X(18))-6
713 P(163)=ABS(X(11)-X(19))-4.5
714 P(164)=ABS(X(11)-X(20))-4
715 P(165)=ABS(X(12)-X(13))-6
716 P(166)=ABS(X(12)-X(14))-8
717 P(167)=ABS(X(12)-X(15))-6
718 P(168)=ABS(X(12)-X(16))-8
719 P(169)=ABS(X(12)-X(17))-7
720 P(170)=ABS(X(12)-X(18))-9
721 P(171)=ABS(X(12)-X(19))-7.5
722 P(172)=ABS(X(12)-X(20))-7
723 P(173)=ABS(X(13)-X(14))-5
724 P(174)=ABS(X(13)-X(15))-3
725 P(175)=ABS(X(13)-X(16))-5
726 P(176)=ABS(X(13)-X(17))-4
727 P(177)=ABS(X(13)-X(18))-6
728 P(178)=ABS(X(13)-X(19))-4.5
729 P(179)=ABS(X(13)-X(20))-4
730 P(180)=ABS(X(14)-X(15))-5
731 P(181)=ABS(X(14)-X(16))-7
732 P(182)=ABS(X(14)-X(17))-6
733 P(183)=ABS(X(14)-X(18))-8
734 P(184)=ABS(X(14)-X(19))-6.5
735 P(185)=ABS(X(14)-X(20))-6
736 P(186)=ABS(X(15)-X(16))-5
737 P(187)=ABS(X(15)-X(17))-4
738 P(188)=ABS(X(15)-X(18))-6
739 P(189)=ABS(X(15)-X(19))-4.5
740 P(190)=ABS(X(15)-X(20))-4
741 P(191)=ABS(X(16)-X(17))-6
742 P(192)=ABS(X(16)-X(18))-8
743 P(193)=ABS(X(16)-X(19))-6.5
744 P(194)=ABS(X(16)-X(20))-6
745 P(195)=ABS(X(17)-X(18))-7
746 P(196)=ABS(X(17)-X(19))-5.5
747 P(197)=ABS(X(17)-X(20))-5
748 P(198)=ABS(X(18)-X(19))-7.5
749 P(199)=ABS(X(18)-X(20))-7
750 P(200)=ABS(X(19)-X(20))-5.5
751 P(201)=ABS(X(1)-X(21))-3
752 P(202)=ABS(X(1)-X(22))-6
753 P(203)=ABS(X(1)-X(23))-3
754 P(204)=ABS(X(1)-X(24))-5
755 P(205)=ABS(X(1)-X(25))-3
756 P(206)=ABS(X(1)-X(26))-5
757 P(207)=ABS(X(1)-X(27))-4
758 P(208)=ABS(X(1)-X(28))-6
759 P(209)=ABS(X(1)-X(29))-4.5
760 P(210)=ABS(X(1)-X(30))-4
761 P(211)=ABS(X(2)-X(21))-6
762 P(212)=ABS(X(2)-X(22))-9
763 P(213)=ABS(X(2)-X(23))-6
764 P(214)=ABS(X(2)-X(24))-8
765 P(215)=ABS(X(2)-X(25))-6
766 P(216)=ABS(X(2)-X(26))-8
767 P(217)=ABS(X(2)-X(27))-7
768 P(218)=ABS(X(2)-X(28))-9
769 P(219)=ABS(X(2)-X(29))-7.5
770 P(220)=ABS(X(2)-X(30))-7
771 P(221)=ABS(X(3)-X(21))-3
772 P(222)=ABS(X(3)-X(22))-6
773 P(223)=ABS(X(3)-X(23))-3
774 P(224)=ABS(X(3)-X(24))-5
775 P(225)=ABS(X(3)-X(25))-3
776 P(226)=ABS(X(3)-X(26))-5
777 P(227)=ABS(X(3)-X(27))-4
778 P(228)=ABS(X(3)-X(28))-6
779 P(229)=ABS(X(3)-X(29))-4.5
780 P(230)=ABS(X(3)-X(30))-4
781 P(231)=ABS(X(4)-X(21))-5
782 P(232)=ABS(X(4)-X(22))-8
783 P(233)=ABS(X(4)-X(23))-5
784 P(234)=ABS(X(4)-X(24))-7
785 P(235)=ABS(X(4)-X(25))-5
786 P(236)=ABS(X(4)-X(26))-7
787 P(237)=ABS(X(4)-X(27))-6
788 P(238)=ABS(X(4)-X(28))-8
789 P(239)=ABS(X(4)-X(29))-6.5
790 P(240)=ABS(X(4)-X(30))-6
791 P(241)=ABS(X(5)-X(21))-3
792 P(242)=ABS(X(5)-X(22))-6
793 P(243)=ABS(X(5)-X(23))-3
794 P(244)=ABS(X(5)-X(24))-5
795 P(245)=ABS(X(5)-X(25))-3
796 P(246)=ABS(X(5)-X(26))-5
797 P(247)=ABS(X(5)-X(27))-4
798 P(248)=ABS(X(5)-X(28))-6
799 P(249)=ABS(X(5)-X(29))-4.5
800 P(250)=ABS(X(5)-X(30))-4
801 P(251)=ABS(X(6)-X(21))-5
802 P(252)=ABS(X(6)-X(22))-8
803 P(253)=ABS(X(6)-X(23))-5
804 P(254)=ABS(X(6)-X(24))-7
805 P(255)=ABS(X(6)-X(25))-5
806 P(256)=ABS(X(6)-X(26))-7
807 P(257)=ABS(X(6)-X(27))-6
808 P(258)=ABS(X(6)-X(28))-8
809 P(259)=ABS(X(6)-X(29))-6.5
810 P(260)=ABS(X(6)-X(30))-6
811 P(261)=ABS(X(7)-X(21))-4
812 P(262)=ABS(X(7)-X(22))-7
813 P(263)=ABS(X(7)-X(23))-4
814 P(264)=ABS(X(7)-X(24))-6
815 P(265)=ABS(X(7)-X(25))-4
816 P(266)=ABS(X(7)-X(26))-6
817 P(267)=ABS(X(7)-X(27))-5
818 P(268)=ABS(X(7)-X(28))-7
819 P(269)=ABS(X(7)-X(29))-5.5
820 P(270)=ABS(X(7)-X(30))-5
821 P(271)=ABS(X(8)-X(21))-6
822 P(272)=ABS(X(8)-X(22))-9
823 P(273)=ABS(X(8)-X(23))-6
824 P(274)=ABS(X(8)-X(24))-8
825 P(275)=ABS(X(8)-X(25))-6
826 P(276)=ABS(X(8)-X(26))-8
827 P(277)=ABS(X(8)-X(27))-7
828 P(278)=ABS(X(8)-X(28))-9
829 P(279)=ABS(X(8)-X(29))-7.5
830 P(280)=ABS(X(8)-X(30))-7
831 P(281)=ABS(X(9)-X(21))-4.5
832 P(282)=ABS(X(9)-X(22))-7.5
833 P(283)=ABS(X(9)-X(23))-4.5
834 P(284)=ABS(X(9)-X(24))-6.5
835 P(285)=ABS(X(9)-X(25))-4.5
836 P(286)=ABS(X(9)-X(26))-6.5
837 P(287)=ABS(X(9)-X(27))-5.5
838 P(288)=ABS(X(9)-X(28))-7.5
839 P(289)=ABS(X(9)-X(29))-6
840 P(290)=ABS(X(9)-X(30))-5.5
841 P(291)=ABS(X(10)-X(21))-4
842 P(292)=ABS(X(10)-X(22))-7
843 P(293)=ABS(X(10)-X(23))-4
844 P(294)=ABS(X(10)-X(24))-6
845 P(295)=ABS(X(10)-X(25))-4
846 P(296)=ABS(X(10)-X(26))-6
847 P(297)=ABS(X(10)-X(27))-5
848 P(298)=ABS(X(10)-X(28))-7
849 P(299)=ABS(X(10)-X(29))-5.5
850 P(300)=ABS(X(10)-X(30))-5
851 P(301)=ABS(X(11)-X(21))-3
852 P(302)=ABS(X(11)-X(22))-6
853 P(303)=ABS(X(11)-X(23))-3
854 P(304)=ABS(X(11)-X(24))-5
855 P(305)=ABS(X(11)-X(25))-3
856 P(306)=ABS(X(11)-X(26))-5
857 P(307)=ABS(X(11)-X(27))-4
858 P(308)=ABS(X(11)-X(28))-6
859 P(309)=ABS(X(11)-X(29))-4.5
860 P(310)=ABS(X(11)-X(30))-4
861 P(311)=ABS(X(12)-X(21))-6
862 P(312)=ABS(X(12)-X(22))-9
863 P(313)=ABS(X(12)-X(23))-6
864 P(314)=ABS(X(12)-X(24))-8
865 P(315)=ABS(X(12)-X(25))-6
866 P(316)=ABS(X(12)-X(26))-8
867 P(317)=ABS(X(12)-X(27))-7
868 P(318)=ABS(X(12)-X(28))-9
869 P(319)=ABS(X(12)-X(29))-7.5
870 P(320)=ABS(X(12)-X(30))-7
871 P(321)=ABS(X(13)-X(21))-3
872 P(322)=ABS(X(13)-X(22))-6
873 P(323)=ABS(X(13)-X(23))-3
874 P(324)=ABS(X(13)-X(24))-5
875 P(325)=ABS(X(13)-X(25))-3
876 P(326)=ABS(X(13)-X(26))-5
877 P(327)=ABS(X(13)-X(27))-4
878 P(328)=ABS(X(13)-X(28))-6
879 P(329)=ABS(X(13)-X(29))-4.5
880 P(330)=ABS(X(13)-X(30))-4
881 P(331)=ABS(X(14)-X(21))-5
882 P(332)=ABS(X(14)-X(22))-8
883 P(333)=ABS(X(14)-X(23))-5
884 P(334)=ABS(X(14)-X(24))-7
885 P(335)=ABS(X(14)-X(25))-5
886 P(336)=ABS(X(14)-X(26))-7
887 P(337)=ABS(X(14)-X(27))-6
888 P(338)=ABS(X(14)-X(28))-8
889 P(339)=ABS(X(14)-X(29))-6.5
890 P(340)=ABS(X(14)-X(30))-6
891 P(341)=ABS(X(15)-X(21))-3
892 P(342)=ABS(X(15)-X(22))-6
893 P(343)=ABS(X(15)-X(23))-3
894 P(344)=ABS(X(15)-X(24))-5
895 P(345)=ABS(X(15)-X(25))-3
896 P(346)=ABS(X(15)-X(26))-5
897 P(347)=ABS(X(15)-X(27))-4
898 P(348)=ABS(X(15)-X(28))-6
899 P(349)=ABS(X(15)-X(29))-4.5
900 P(350)=ABS(X(15)-X(30))-4
901 P(351)=ABS(X(16)-X(21))-5
902 P(352)=ABS(X(16)-X(22))-8
903 P(353)=ABS(X(16)-X(23))-5
904 P(354)=ABS(X(16)-X(24))-7
905 P(355)=ABS(X(16)-X(25))-5
906 P(356)=ABS(X(16)-X(26))-7
907 P(357)=ABS(X(16)-X(27))-6
908 P(358)=ABS(X(16)-X(28))-8
909 P(359)=ABS(X(16)-X(29))-6.5
910 P(360)=ABS(X(16)-X(30))-6
911 P(361)=ABS(X(17)-X(21))-4
912 P(362)=ABS(X(17)-X(22))-7
913 P(363)=ABS(X(17)-X(23))-4
914 P(364)=ABS(X(17)-X(24))-6
915 P(365)=ABS(X(17)-X(25))-4
916 P(366)=ABS(X(17)-X(26))-6
917 P(367)=ABS(X(17)-X(27))-5
918 P(368)=ABS(X(17)-X(28))-7
919 P(369)=ABS(X(17)-X(29))-5.5
920 P(370)=ABS(X(17)-X(30))-5
921 P(371)=ABS(X(18)-X(21))-6
922 P(372)=ABS(X(18)-X(22))-9
923 P(373)=ABS(X(18)-X(23))-6
924 P(374)=ABS(X(18)-X(24))-8
925 P(375)=ABS(X(18)-X(25))-6
926 P(376)=ABS(X(18)-X(26))-8
927 P(377)=ABS(X(18)-X(27))-7
928 P(378)=ABS(X(18)-X(28))-9
929 P(379)=ABS(X(18)-X(29))-7.5
930 P(380)=ABS(X(18)-X(30))-7
931 P(381)=ABS(X(19)-X(21))-4.5
932 P(382)=ABS(X(19)-X(22))-7.5
933 P(383)=ABS(X(19)-X(23))-4.5
934 P(384)=ABS(X(19)-X(24))-6.5
935 P(385)=ABS(X(19)-X(25))-4.5
936 P(386)=ABS(X(19)-X(26))-6.5
937 P(387)=ABS(X(19)-X(27))-5.5
938 P(388)=ABS(X(19)-X(28))-7.5
939 P(389)=ABS(X(19)-X(29))-6
940 P(390)=ABS(X(19)-X(30))-5.5
941 P(391)=ABS(X(20)-X(21))-4
942 P(392)=ABS(X(20)-X(22))-7
943 P(393)=ABS(X(20)-X(23))-4
944 P(394)=ABS(X(20)-X(24))-6
945 P(395)=ABS(X(20)-X(25))-4
946 P(396)=ABS(X(20)-X(26))-6
947 P(397)=ABS(X(20)-X(27))-5
948 P(398)=ABS(X(20)-X(28))-7
949 P(399)=ABS(X(20)-X(29))-5.5
950 P(400)=ABS(X(20)-X(30))-5
951 P(401)=ABS(X(21)-X(22))-6
952 P(402)=ABS(X(21)-X(23))-3
953 P(403)=ABS(X(21)-X(24))-5
954 P(404)=ABS(X(21)-X(25))-3
955 P(405)=ABS(X(21)-X(26))-5
956 P(406)=ABS(X(21)-X(27))-4
957 P(407)=ABS(X(21)-X(28))-6
958 P(408)=ABS(X(21)-X(29))-4.5
959 P(409)=ABS(X(21)-X(30))-4
960 P(410)=ABS(X(22)-X(23))-6
961 P(411)=ABS(X(22)-X(24))-8
962 P(412)=ABS(X(22)-X(25))-6
963 P(413)=ABS(X(22)-X(26))-8
964 P(414)=ABS(X(22)-X(27))-7
965 P(415)=ABS(X(22)-X(28))-9
966 P(416)=ABS(X(22)-X(29))-7.5
967 P(417)=ABS(X(22)-X(30))-7
968 P(418)=ABS(X(23)-X(24))-5
969 P(419)=ABS(X(23)-X(25))-3
970 P(420)=ABS(X(23)-X(26))-5
971 P(421)=ABS(X(23)-X(27))-4
972 P(422)=ABS(X(23)-X(28))-6
973 P(423)=ABS(X(23)-X(29))-4.5
974 P(424)=ABS(X(23)-X(30))-4
975 P(425)=ABS(X(24)-X(25))-5
976 P(426)=ABS(X(24)-X(26))-7
977 P(427)=ABS(X(24)-X(27))-6
978 P(428)=ABS(X(24)-X(28))-8
979 P(429)=ABS(X(24)-X(29))-6.5
980 P(430)=ABS(X(24)-X(30))-6
981 P(431)=ABS(X(25)-X(26))-5
982 P(432)=ABS(X(25)-X(27))-4
983 P(433)=ABS(X(25)-X(28))-6
984 P(434)=ABS(X(25)-X(29))-4.5
985 P(435)=ABS(X(25)-X(30))-4
986 P(436)=ABS(X(26)-X(27))-6
987 P(437)=ABS(X(26)-X(28))-8
988 P(438)=ABS(X(26)-X(29))-6.5
989 P(439)=ABS(X(26)-X(30))-6
990 P(440)=ABS(X(27)-X(28))-7
991 P(441)=ABS(X(27)-X(29))-5.5
992 P(442)=ABS(X(27)-X(30))-5
993 P(443)=ABS(X(28)-X(29))-7.5
994 P(444)=ABS(X(28)-X(30))-7
995 P(445)=ABS(X(29)-X(30))-5.5
996 REM
997 REM
998 REM
999 REM
1088 FOR INSI=11 TO 445
1091 IF P(INSI)<0 THEN P(INSI)=P(INSI) ELSE P(INSI)=0
1095 NEXT INSI
1111 REM
1115 REM
1118 REM
1121 REM
1131 REM
1211 PSUM=0
1215 FOR IOCT=11 TO 445
1218 PSUM=PSUM+P(IOCT)
1221 NEXT IOCT
1231 PS1=99*555555!*PSUM
1238 P11B=3*ABS(X(1)-X(2))+2*ABS(X(1)-X(3))+0*ABS(X(1)-X(4))+0*ABS(X(1)-X(5))+2*ABS(X(1)-X(6))+10*ABS(X(1)-X(7))+5*ABS(X(1)-X(8))+0*ABS(X(1)-X(9))+5*ABS(X(1)-X(10))+2*ABS(X(1)-X(11))
1239 P12B=5*ABS(X(1)-X(12))+0*ABS(X(1)-X(13))+0*ABS(X(1)-X(14))+2*ABS(X(1)-X(15))
1240 P13B=4*ABS(X(2)-X(3))+0*ABS(X(2)-X(4))+10*ABS(X(2)-X(5))+4*ABS(X(2)-X(6))+0*ABS(X(2)-X(7))+0*ABS(X(2)-X(8))+2*ABS(X(2)-X(9))+2*ABS(X(2)-X(10))+1*ABS(X(2)-X(11))
1241 P14B=0*ABS(X(2)-X(12))+5*ABS(X(2)-X(13))+0*ABS(X(2)-X(14))+0*ABS(X(2)-X(15))
1243 P15B=3*ABS(X(3)-X(4))+4*ABS(X(3)-X(5))+0*ABS(X(3)-X(6))+5*ABS(X(3)-X(7))+5*ABS(X(3)-X(8))+5*ABS(X(3)-X(9))+1*ABS(X(3)-X(10))+4*ABS(X(3)-X(11))
1244 P16B=1*ABS(X(3)-X(12))+0*ABS(X(3)-X(13))+4*ABS(X(3)-X(14))+0*ABS(X(3)-X(15))
1245 P17B=0*ABS(X(4)-X(5))+0*ABS(X(4)-X(6))+0*ABS(X(4)-X(7))+2*ABS(X(4)-X(8))+2*ABS(X(4)-X(9))+0*ABS(X(4)-X(10))+6*ABS(X(4)-X(11))
1246 P18B=0*ABS(X(4)-X(12))+2*ABS(X(4)-X(13))+5*ABS(X(4)-X(14))+2*ABS(X(4)-X(15))
1248 P19B=5*ABS(X(5)-X(6))+2*ABS(X(5)-X(7))+0*ABS(X(5)-X(8))+0*ABS(X(5)-X(9))+0*ABS(X(5)-X(10))+0*ABS(X(5)-X(11))+2*ABS(X(5)-X(12))+0*ABS(X(5)-X(13))+0*ABS(X(5)-X(14))+0*ABS(X(5)-X(15))
1249 P20B=1*ABS(X(6)-X(7))+2*ABS(X(6)-X(8))+2*ABS(X(6)-X(9))+1*ABS(X(6)-X(10))+4*ABS(X(6)-X(11))+10*ABS(X(6)-X(12))+10*ABS(X(6)-X(13))+2*ABS(X(6)-X(14))+5*ABS(X(6)-X(15))
1250 P21B=10*ABS(X(7)-X(8))+10*ABS(X(7)-X(9))+5*ABS(X(7)-X(10))+10*ABS(X(7)-X(11))+10*ABS(X(7)-X(12))+6*ABS(X(7)-X(13))+0*ABS(X(7)-X(14))+0*ABS(X(7)-X(15))
1251 P22B=1*ABS(X(8)-X(9))+3*ABS(X(8)-X(10))+5*ABS(X(8)-X(11))+0*ABS(X(8)-X(12))+0*ABS(X(8)-X(13))+0*ABS(X(8)-X(14))+2*ABS(X(8)-X(15))
1255 P23B=10*ABS(X(9)-X(10))+2*ABS(X(9)-X(11))+1*ABS(X(9)-X(12))+5*ABS(X(9)-X(13))+2*ABS(X(9)-X(14))+0*ABS(X(9)-X(15))
1257 P24B=5*ABS(X(10)-X(11))+5*ABS(X(10)-X(12))+6*ABS(X(10)-X(13))+0*ABS(X(10)-X(14))+1*ABS(X(10)-X(15))
1258 P25B=0*ABS(X(11)-X(12))+0*ABS(X(11)-X(13))+1*ABS(X(11)-X(14))+2*ABS(X(11)-X(15))
1259 P26B=5*ABS(X(12)-X(13))+5*ABS(X(12)-X(14))+2*ABS(X(12)-X(15))+2*ABS(X(13)-X(14))+0*ABS(X(13)-X(15))+2*ABS(X(14)-X(15))
1301 P27B=0*ABS(X(1)-X(16))+5*ABS(X(1)-X(17))+6*ABS(X(1)-X(18))+3*ABS(X(1)-X(18))+0*ABS(X(1)-X(20))
1302 P28B=0*ABS(X(2)-X(16))+0*ABS(X(2)-X(17))+2*ABS(X(2)-X(18))+0*ABS(X(2)-X(19))+1*ABS(X(2)-X(20))
1303 P29B=4*ABS(X(3)-X(16))+0*ABS(X(3)-X(17))+6*ABS(X(3)-X(18))+3*ABS(X(3)-X(19))+2*ABS(X(3)-X(20))
1304 P30B=5*ABS(X(4)-X(16))+1*ABS(X(4)-X(17))+1*ABS(X(4)-X(18))+1*ABS(X(4)-X(19))+1*ABS(X(4)-X(20))
1305 P31B=0*ABS(X(5)-X(16))+2*ABS(X(5)-X(17))+1*ABS(X(5)-X(18))+0*ABS(X(5)-X(19))+0*ABS(X(5)-X(20))
1306 P32B=5*ABS(X(6)-X(16))+0*ABS(X(6)-X(17))+5*ABS(X(6)-X(18))+0*ABS(X(6)-X(19))+0*ABS(X(6)-X(20))
1307 P33B=10*ABS(X(7)-X(16))+2*ABS(X(7)-X(17))+1*ABS(X(7)-X(18))+10*ABS(X(7)-X(19))+1*ABS(X(7)-X(20))
1308 P34B=4*ABS(X(8)-X(16))+5*ABS(X(8)-X(17))+2*ABS(X(8)-X(18))+10*ABS(X(8)-X(19))+6*ABS(X(8)-X(20))
1309 P35B=3*ABS(X(9)-X(16))+0*ABS(X(9)-X(17))+2*ABS(X(9)-X(18))+0*ABS(X(9)-X(19))+0*ABS(X(9)-X(20))
1310 P36B=5*ABS(X(10)-X(16))+5*ABS(X(10)-X(17))+0*ABS(X(10)-X(18))+5*ABS(X(10)-X(19))+2*ABS(X(10)-X(20))
1311 P37B=1*ABS(X(11)-X(16))+0*ABS(X(11)-X(17))+2*ABS(X(11)-X(18))+0*ABS(X(11)-X(19))+0*ABS(X(11)-X(20))
1312 P38B=0*ABS(X(12)-X(16))+0*ABS(X(12)-X(17))+0*ABS(X(12)-X(18))+0*ABS(X(12)-X(19))+2*ABS(X(12)-X(20))
1313 P39B=4*ABS(X(13)-X(16))+2*ABS(X(13)-X(17))+2*ABS(X(13)-X(18))+1*ABS(X(13)-X(19))+0*ABS(X(13)-X(20))
1314 P40B=1*ABS(X(14)-X(16))+0*ABS(X(14)-X(17))+5*ABS(X(14)-X(18))+3*ABS(X(14)-X(19))+10*ABS(X(14)-X(20))
1315 P41B=4*ABS(X(15)-X(16))+5*ABS(X(15)-X(17))+1*ABS(X(15)-X(18))+0*ABS(X(15)-X(19))+1*ABS(X(15)-X(20))
1316 P42B=0*ABS(X(16)-X(17))+3*ABS(X(16)-X(18))+0*ABS(X(16)-X(19))+2*ABS(X(16)-X(20))
1317 P43B=2*ABS(X(17)-X(18))+2*ABS(X(17)-X(19))+0*ABS(X(17)-X(20))+5*ABS(X(18)-X(19))+1*ABS(X(18)-X(20))+0*ABS(X(19)-X(20))
1321 P44B=1*ABS(X(1)-X(21))+10*ABS(X(1)-X(22))+0*ABS(X(1)-X(23))+10*ABS(X(1)-X(24))+2*ABS(X(1)-X(25))+1*ABS(X(1)-X(26))+1*ABS(X(1)-X(27))+1*ABS(X(1)-X(28))+0*ABS(X(1)-X(29))+1*ABS(X(1)-X(30))
1322 P45B=6*ABS(X(2)-X(21))+1*ABS(X(2)-X(22))+0*ABS(X(2)-X(23))+1*ABS(X(2)-X(24))+2*ABS(X(2)-X(25))+2*ABS(X(2)-X(26))+5*ABS(X(2)-X(27))+1*ABS(X(2)-X(28))+10*ABS(X(2)-X(29))+5*ABS(X(2)-X(30))
1323 P46B=5*ABS(X(3)-X(21))+5*ABS(X(3)-X(22))+2*ABS(X(3)-X(23))+1*ABS(X(3)-X(24))+0*ABS(X(3)-X(25))+0*ABS(X(3)-X(26))+3*ABS(X(3)-X(27))+1*ABS(X(3)-X(28))+0*ABS(X(3)-X(29))+2*ABS(X(3)-X(30))
1324 P47B=2*ABS(X(4)-X(21))+2*ABS(X(4)-X(22))+4*ABS(X(4)-X(23))+0*ABS(X(4)-X(24))+2*ABS(X(4)-X(25))+0*ABS(X(4)-X(26))+2*ABS(X(4)-X(27))+2*ABS(X(4)-X(28))+5*ABS(X(4)-X(29))+5*ABS(X(4)-X(30))
1325 P48B=2*ABS(X(5)-X(21))+0*ABS(X(5)-X(22))+5*ABS(X(5)-X(23))+1*ABS(X(5)-X(24))+0*ABS(X(5)-X(25))+2*ABS(X(5)-X(26))+1*ABS(X(5)-X(27))+0*ABS(X(5)-X(28))+2*ABS(X(5)-X(29))+1*ABS(X(5)-X(30))
1326 P49B=0*ABS(X(6)-X(21))+10*ABS(X(6)-X(22))+0*ABS(X(6)-X(23))+0*ABS(X(6)-X(24))+0*ABS(X(6)-X(25))+4*ABS(X(6)-X(26))+0*ABS(X(6)-X(27))+10*ABS(X(6)-X(28))+1*ABS(X(6)-X(29))+1*ABS(X(6)-X(30))
1327 P50B=5*ABS(X(7)-X(21))+5*ABS(X(7)-X(22))+2*ABS(X(7)-X(23))+3*ABS(X(7)-X(24))+5*ABS(X(7)-X(25))+0*ABS(X(7)-X(26))+2*ABS(X(7)-X(27))+0*ABS(X(7)-X(28))+1*ABS(X(7)-X(29))+3*ABS(X(7)-X(30))
1328 P51B=0*ABS(X(8)-X(21))+5*ABS(X(8)-X(22))+5*ABS(X(8)-X(23))+2*ABS(X(8)-X(24))+5*ABS(X(8)-X(25))+0*ABS(X(8)-X(26))+5*ABS(X(8)-X(27))+5*ABS(X(8)-X(28))+0*ABS(X(8)-X(29))+2*ABS(X(8)-X(30))
1329 P52B=4*ABS(X(9)-X(21))+0*ABS(X(9)-X(22))+5*ABS(X(9)-X(23))+2*ABS(X(9)-X(24))+0*ABS(X(9)-X(25))+5*ABS(X(9)-X(26))+2*ABS(X(9)-X(27))+2*ABS(X(9)-X(28))+5*ABS(X(9)-X(29))+2*ABS(X(9)-X(30))
1330 P53B=3*ABS(X(10)-X(21))+5*ABS(X(10)-X(22))+0*ABS(X(10)-X(23))+5*ABS(X(10)-X(24))+2*ABS(X(10)-X(25))+10*ABS(X(10)-X(26))+10*ABS(X(10)-X(27))+1*ABS(X(10)-X(28))+5*ABS(X(10)-X(29))+2*ABS(X(10)-X(30))
1331 P54B=0*ABS(X(11)-X(21))+6*ABS(X(11)-X(22))+6*ABS(X(11)-X(23))+0*ABS(X(11)-X(24))+4*ABS(X(11)-X(25))+5*ABS(X(11)-X(26))+3*ABS(X(11)-X(27))+2*ABS(X(11)-X(28))+2*ABS(X(11)-X(29))+10*ABS(X(11)-X(30))
1332 P55B=0*ABS(X(12)-X(21))+4*ABS(X(12)-X(22))+5*ABS(X(12)-X(23))+10*ABS(X(12)-X(24))+1*ABS(X(12)-X(25))+0*ABS(X(12)-X(26))+0*ABS(X(12)-X(27))+0*ABS(X(12)-X(28))+0*ABS(X(12)-X(29))+1*ABS(X(12)-X(30))
1333 P56B=6*ABS(X(13)-X(21))+2*ABS(X(13)-X(22))+1*ABS(X(13)-X(23))+5*ABS(X(13)-X(24))+5*ABS(X(13)-X(25))+0*ABS(X(13)-X(26))+0*ABS(X(13)-X(27))+1*ABS(X(13)-X(28))+5*ABS(X(13)-X(29))+5*ABS(X(13)-X(30))
1334 P57B=0*ABS(X(14)-X(21))+0*ABS(X(14)-X(22))+4*ABS(X(14)-X(23))+2*ABS(X(14)-X(24))+0*ABS(X(14)-X(25))+0*ABS(X(14)-X(26))+4*ABS(X(14)-X(27))+2*ABS(X(14)-X(28))+5*ABS(X(14)-X(29))+5*ABS(X(14)-X(30))
1335 P58B=0*ABS(X(15)-X(21))+5*ABS(X(15)-X(22))+0*ABS(X(15)-X(23))+2*ABS(X(15)-X(24))+0*ABS(X(15)-X(25))+0*ABS(X(15)-X(26))+5*ABS(X(15)-X(27))+1*ABS(X(15)-X(28))+1*ABS(X(15)-X(29))+0*ABS(X(15)-X(30))
1336 P59B=2*ABS(X(16)-X(21))+0*ABS(X(16)-X(22))+2*ABS(X(16)-X(23))+0*ABS(X(16)-X(24))+5*ABS(X(16)-X(25))+0*ABS(X(16)-X(26))+5*ABS(X(16)-X(27))+2*ABS(X(16)-X(28))+5*ABS(X(16)-X(29))+10*ABS(X(16)-X(30))
1337 P60B=0*ABS(X(17)-X(21))+0*ABS(X(17)-X(22))+6*ABS(X(17)-X(23))+5*ABS(X(17)-X(24))+3*ABS(X(17)-X(25))+5*ABS(X(17)-X(26))+0*ABS(X(17)-X(27))+0*ABS(X(17)-X(28))+5*ABS(X(17)-X(29))+1*ABS(X(17)-X(30))
1338 P61B=2*ABS(X(18)-X(21))+10*ABS(X(18)-X(22))+10*ABS(X(18)-X(23))+4*ABS(X(18)-X(24))+0*ABS(X(18)-X(25))+0*ABS(X(18)-X(26))+5*ABS(X(18)-X(27))+0*ABS(X(18)-X(28))+0*ABS(X(18)-X(29))+0*ABS(X(18)-X(30))
1339 P62B=5*ABS(X(19)-X(21))+5*ABS(X(19)-X(22))+1*ABS(X(19)-X(23))+0*ABS(X(19)-X(24))+5*ABS(X(19)-X(25))+2*ABS(X(19)-X(26))+1*ABS(X(19)-X(27))+2*ABS(X(19)-X(28))+10*ABS(X(19)-X(29))+10*ABS(X(19)-X(30))
1340 P63B=5*ABS(X(20)-X(21))+2*ABS(X(20)-X(22))+1*ABS(X(20)-X(23))+3*ABS(X(20)-X(24))+1*ABS(X(20)-X(25))+5*ABS(X(20)-X(26))+6*ABS(X(20)-X(27))+5*ABS(X(20)-X(28))+5*ABS(X(20)-X(29))+3*ABS(X(20)-X(30))
1341 P64B=4*ABS(X(21)-X(22))+0*ABS(X(21)-X(23))+1*ABS(X(21)-X(24))+0*ABS(X(21)-X(25))+0*ABS(X(21)-X(26))+0*ABS(X(21)-X(27))+5*ABS(X(21)-X(28))+0*ABS(X(21)-X(29))+0*ABS(X(21)-X(30))
1342 P65B=5*ABS(X(22)-X(23))+0*ABS(X(22)-X(24))+4*ABS(X(22)-X(25))+4*ABS(X(22)-X(26))+5*ABS(X(22)-X(27))+0*ABS(X(22)-X(28))+2*ABS(X(22)-X(29))+5*ABS(X(22)-X(30))
1343 P66B=0*ABS(X(23)-X(24))+4*ABS(X(23)-X(25))+4*ABS(X(23)-X(26))+1*ABS(X(23)-X(27))+0*ABS(X(23)-X(28))+2*ABS(X(23)-X(29))+2*ABS(X(23)-X(30))
1344 P67B=5*ABS(X(24)-X(25))+5*ABS(X(24)-X(26))+0*ABS(X(24)-X(27))+1*ABS(X(24)-X(28))+0*ABS(X(24)-X(29))+0*ABS(X(24)-X(30))
1345 P68B=1*ABS(X(25)-X(26))+0*ABS(X(25)-X(27))+10*ABS(X(25)-X(28))+1*ABS(X(25)-X(29))+0*ABS(X(25)-X(30))
1346 P69B=0*ABS(X(26)-X(27))+0*ABS(X(26)-X(28))+0*ABS(X(26)-X(29))+0*ABS(X(26)-X(30))
1347 P70B=0*ABS(X(27)-X(28))+0*ABS(X(27)-X(29))+10*ABS(X(27)-X(30))+2*ABS(X(28)-X(29))+2*ABS(X(28)-X(30))+2*ABS(X(29)-X(30))
1388 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B+P21B+P22B+P23B+P24B+P25B+P26B
1395 P2=P27B+P28B+P29B+P30B+P31B+P32B+P33B+P34B+P35B+P36B+P37B+P38B+P39B+P40B+P41B+P42B+P43B
1397 P3=P44B+P45B+P46B+P47B+P48B+P49B+P50B+P51B+P52B+P53B+P54B+P55B+P56B+P57B+P58B+P59B+P60B
1398 P4=P61B+P62B+P63B+P64B+P65B+P66B+P67B+P68B+P69B+P70B
1448 P5=P1+P2+P3+P4
1449 REM
1450 P=-P5+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P5
1454 FOR KLX=1 TO 30
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1778 REM
1888 NEXT JJJ
1890 IF M>-47000! THEN 1916 ELSE 1999
1916 PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),M,PP1
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12),A(13),A(14),A(15)
1922 PRINT A(16),A(17),A(18),A(19),A(20)
1924 PRINT A(21),A(22),A(23),A(24),A(25)
1926 PRINT A(26),A(27),A(28),A(29),A(30)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and its candidate solutions from JJJJ=-32000 through JJJJ=-31963 (in compressed form and to be interpreted in accordance with line 1916 through line 1926; copied manually from the computer monitor) are presented below.
-31963 39963.88 39924.88 40009.88 40071.88
39937.88 -45961.73 45961.73
39971.88 40005.88 40045.88 40022.38 39986.88
40001.88 39943.88 39998.88 40059.88 39966.88
40034.88 39959.88 39952.88 40028.38 40065.88
40012.88 39979.88 39990.88 39932.88 40039.88
39916.88 39994.88 40079.88 40053.38 40016.88
And this same computer run also produced candidate solutions with objective function values of 46428.14, 46955.42, 46684.12, and 46540.5 at JJJJ=-31988, -31975, -31972, and -31965, respectively.
The total time for the output above was obtained in 55 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter.
If one makes changes to the computer program above, such as a change of changing line 128 to, for example, 128 FOR I=1 TO 3, one may or may not obtain this objective function value of 45961.73. For this problem, the optimal objective function value is 44965.0, Amaral [1]. Generally speaking, in order to increase the probability of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128, for example. This multicomputer approach can mitigate the possible danger of missed optimality and can produce a usable solution faster than just running one computer.
References
[1] A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics, in press.
[2] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.
[3] S.S. Heragu, A. Kusiak, Efficient models for the facility layut problem, European Journal of Operational Research 53 (1991) 1-13.
[4] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[5] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[6] D.M. Simmons, One-dimensional space allocation: An ordering algorithm, Operations Research 17 (1969) 812-826.

A General Integer Programming Computer Program Appliedd to a Three-Dimensional Quadratic Assignment Problem

Jsun Yui Wong
This paper considers an extension to three dimensions of the formulation on page 6 of Heragu and Kusiak [1] and on page 140 of Heragu [2]. The specific problem used by the computer program listed here is a three-dimensional version of the 6-department problem of Nugent et al. [3]; the inter-departmental flows of the 6-department case of Nugent et al. [3, p. 168] are used in line 1238 through line 1349. The following computer program benefits from the computer program of Conley [4, pp. 229-232] and the computer programs of the present blog; its output is also presented here.
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
44 FOR IO=1 TO 18
45 B(IO)=0
46 NEXT IO
51 FOR IOCTT=1 TO 18
53 N(IOCTT)=5
57 NEXT IOCTT
61 FOR KLQ=1 TO 18
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 18
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 2
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 18
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 18
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 18
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*54)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+18*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 18
364 X(I222)=FIX(X(I222))
368 NEXT I222
461 IF RND>.1 GOTO 561
465 IF RND<1/3 THEN 471 ELSE IF RND<2/3 THEN 491 ELSE 521
471 IOCT1=1+FIX(RND*6)
474 IOCT2=1+FIX(RND*6)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
481 GOTO 561
491 IOCT6=7+FIX(RND*6)
494 IOCT7=7+FIX(RND*6)
497 X(IOCT6)=A(IOCT7)
500 X(IOCT7)=A(IOCT6)
511 GOTO 561
521 IOCT13=13+FIX(RND*6)
524 IOCT14=13+FIX(RND*6)
537 X(IOCT13)=A(IOCT14)
540 X(IOCT14)=A(IOCT13)
561 P(11)=ABS(X(1)-X(2))+ABS(X(7)-X(8))+ABS(X(13)-X(14))-1
562 P(12)=ABS(X(1)-X(3))+ABS(X(7)-X(9))+ABS(X(13)-X(15))-1
563 P(13)=ABS(X(1)-X(4))+ABS(X(7)-X(10))+ABS(X(13)-X(16))-1
564 P(14)=ABS(X(1)-X(5))+ABS(X(7)-X(11))+ABS(X(13)-X(17))-1
565 P(15)=ABS(X(1)-X(6))+ABS(X(7)-X(12))+ABS(X(13)-X(18))-1
566 P(16)=ABS(X(2)-X(3))+ABS(X(8)-X(9))+ABS(X(14)-X(15))-1
567 P(17)=ABS(X(2)-X(4))+ABS(X(8)-X(10))+ABS(X(14)-X(16))-1
568 P(18)=ABS(X(2)-X(5))+ABS(X(8)-X(11))+ABS(X(14)-X(17))-1
569 P(19)=ABS(X(2)-X(6))+ABS(X(8)-X(12))+ABS(X(14)-X(18))-1
570 P(20)=ABS(X(3)-X(4))+ABS(X(9)-X(10))+ABS(X(15)-X(16))-1
571 P(21)=ABS(X(3)-X(5))+ABS(X(9)-X(11))+ABS(X(15)-X(17))-1
572 P(22)=ABS(X(3)-X(6))+ABS(X(9)-X(12))+ABS(X(15)-X(18))-1
573 P(23)=ABS(X(4)-X(5))+ABS(X(10)-X(11))+ABS(X(16)-X(17))-1
574 P(24)=ABS(X(4)-X(6))+ABS(X(10)-X(12))+ABS(X(16)-X(18))-1
575 P(25)=ABS(X(5)-X(6))+ABS(X(11)-X(12))+ABS(X(17)-X(18))-1
788 FOR INSI=11 TO 25
791 IF P(INSI)<0 THEN P(INSI)=P(INSI) ELSE P(INSI)=0
795 NEXT INSI
1111 PSUM=0
1115 FOR IOCT=11 TO 25
1118 PSUM=PSUM+P(IOCT)
1121 NEXT IOCT
1131 PS1=99*555555!*PSUM
1238 P11B=5*ABS(X(1)-X(2))+2*ABS(X(1)-X(3))+4*ABS(X(1)-X(4))+1*ABS(X(1)-X(5))+0*ABS(X(1)-X(6))
1239 P12B=5*ABS(X(7)-X(8))+2*ABS(X(7)-X(9))+4*ABS(X(7)-X(10))+1*ABS(X(7)-X(11))+0*ABS(X(7)-X(12))
1240 P13B=3*ABS(X(2)-X(3))+0*ABS(X(2)-X(4))+2*ABS(X(2)-X(5))+2*ABS(X(2)-X(6))
1241 P14B=3*ABS(X(8)-X(9))+0*ABS(X(8)-X(10))+2*ABS(X(8)-X(11))+2*ABS(X(8)-X(12))
1243 P15B=0*ABS(X(3)-X(4))+0*ABS(X(3)-X(5))+0*ABS(X(3)-X(6))
1244 P16B=0*ABS(X(9)-X(10))+0*ABS(X(9)-X(11))+0*ABS(X(9)-X(12))
1245 P17B=5*ABS(X(4)-X(5))+2*ABS(X(4)-X(6))
1246 P18B=5*ABS(X(10)-X(11))+2*ABS(X(10)-X(12))
1247 P19B=10*ABS(X(5)-X(6))
1248 P20B=10*ABS(X(11)-X(12))
1340 P21B=5*ABS(X(13)-X(14))+2*ABS(X(13)-X(15))+4*ABS(X(13)-X(16))+1*ABS(X(13)-X(17))+0*ABS(X(13)-X(18))
1342 P22B=3*ABS(X(14)-X(15))+0*ABS(X(14)-X(16))+2*ABS(X(14)-X(17))+2*ABS(X(14)-X(18))
1345 P23B=0*ABS(X(15)-X(16))+0*ABS(X(15)-X(17))+0*ABS(X(15)-X(18))
1347 P24B=5*ABS(X(16)-X(17))+2*ABS(X(16)-X(18))
1349 P25B=10*ABS(X(17)-X(18))
1445 p1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B+P21B+P22B+P23B+P24B+P25B
1447 P2=0
1448 P3=P1+P2
1450 P=-P3+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P3
1454 FOR KLX=1 TO 18
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-55 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5),A(6)
1918 PRINT A(7),A(8),A(9),A(10),A(11),A(12)
1920 PRINT A(13),A(14),A(15),A(16),A(17),A(18)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the candidate solutions produced from JJJJ=-32000 through JJJJ=-31996 (in compressed form and to be interpreted in accordance with line 1916 through line 1920; copied manually from the computer monitor) are presented below.
-32000 -43 43
0 0 1 0 0
1
1 0 0 1 0
0
0 0 0 1 1
1
-31999 -43 43
0 0 0 0 0
0
0 1 1 0 1
2
1 1 2 0 0
0
-31998 -43 43
1 0 0 1 0
0
0 0 0 1 1
2
0 0 1 0 0
0
-31997 -43 43
0 0 1 0 0
1
1 0 0 1 0
0
1 1 1 0 0
0
-31996 -46 46
1 0 1 1 0
0
1 0 0 2 2
1
0 0 0 0 0
0
The best candidate solutions above are at JJJJ=-32000, -31999, -31998, and -31997 with 43 as the objective function value. The output above was obtained in 2 minutes on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter.
References
[1] S.S. Heragu, A. Kusiak, Efficient models for the facility layut problem, European Journal of Operational Research 53 (1991) 1-13.
[2] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[3] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[4] W. C. Conley, Optimization: A Simplified Approach. Petrocelli, Princeton, New Jersey, 1981, pp. 229-232.

A Computer Program Applied to a Facility Layout Problem from the Literature

Jsun Yui Wong
The specific problem used by the computer program listed here is the 11-facility layout problem in Amaral [1, p. 517] and in Heragu [4, pp. 231-232 and pp. 276-279]. This computer program benefits from the computer programs of the present blog, the computer program of Conley [3, pp. 229-232], and the mathematical formulation on page 117 of Heragu [4]. The output of the computer program listed below is also presented here.
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(111)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
25 B(1)=0:B(2)=0:B(3)=0:B(4)=0:B(5)=0:B(6)=0
26 B(7)=0:B(8)=0:B(9)=0:B(10)=0:B(11)=0
37 N(1)=99200!:N(2)=99200!:N(3)=99200!:N(4)=99200!:N(5)=99200!:N(6)=99200!
38 N(7)=99200!:N(8)=99200!:N(9)=99200!:N(10)=99200!:N(11)=99200!
61 FOR KLQ=1 TO 11
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 11
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 13
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 11
111 KKLL=FIX(1+33*RND)
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 11
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 11
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
305 KLPS=FIX(1+KKLL*RND)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+11*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 461
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 461
355 X(JJ)=N(JJ)
461 IF RND>.1 GOTO 561
471 IOCT1=1+FIX(RND*11)
474 IOCT2=1+FIX(RND*11)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P11=ABS(X(1)-X(2))-6
562 P12=ABS(X(1)-X(3))-3
563 P13=ABS(X(1)-X(4))-5
564 P14=ABS(X(1)-X(5))-3
565 P15=ABS(X(1)-X(6))-5
566 P16=ABS(X(1)-X(7))-4
567 P17=ABS(X(1)-X(8))-6
568 P18=ABS(X(1)-X(9))-4.5
569 P19=ABS(X(1)-X(10))-4
570 P20=ABS(X(1)-X(11))-6.5
571 P21=ABS(X(2)-X(3))-6
572 P22=ABS(X(2)-X(4))-8
573 P23=ABS(X(2)-X(5))-6
574 P24=ABS(X(2)-X(6))-8
575 P25=ABS(X(2)-X(7))-7
576 P26=ABS(X(2)-X(8))-9
577 P27=ABS(X(2)-X(9))-7.5
578 P28=ABS(X(2)-X(10))-7
579 P29=ABS(X(2)-X(11))-9.5
583 P30=ABS(X(3)-X(4))-5
584 P31=ABS(X(3)-X(5))-3
585 P32=ABS(X(3)-X(6))-5
586 P33=ABS(X(3)-X(7))-4
587 P34=ABS(X(3)-X(8))-6
588 P35=ABS(X(3)-X(9))-4.5
589 P36=ABS(X(3)-X(10))-4
590 P37=ABS(X(3)-X(11))-6.5
594 P38=ABS(X(4)-X(5))-5
595 P39=ABS(X(4)-X(6))-7
596 P40=ABS(X(4)-X(7))-6
597 P41=ABS(X(4)-X(8))-8
598 P42=ABS(X(4)-X(9))-6.5
599 P43=ABS(X(4)-X(10))-6
600 P44=ABS(X(4)-X(11))-8.5
601 P45=ABS(X(5)-X(6))-5
602 P46=ABS(X(5)-X(7))-4
603 P47=ABS(X(5)-X(8))-6
604 P48=ABS(X(5)-X(9))-4.5
605 P49=ABS(X(5)-X(10))-4
606 P50=ABS(X(5)-X(11))-6.5
607 P51=ABS(X(6)-X(7))-6
608 P52=ABS(X(6)-X(8))-8
609 P53=ABS(X(6)-X(9))-6.5
610 P54=ABS(X(6)-X(10))-6
611 P55=ABS(X(6)-X(11))-8.5
612 P56=ABS(X(7)-X(8))-7
613 P57=ABS(X(7)-X(9))-5.5
614 P58=ABS(X(7)-X(10))-5
615 P59=ABS(X(7)-X(11))-7.5
616 P60=ABS(X(8)-X(9))-7.5
617 P61=ABS(X(8)-X(10))-7
618 P62=ABS(X(8)-X(11))-9.5
619 P63=ABS(X(9)-X(10))-5.5
620 P64=ABS(X(9)-X(11))-8
621 P65=ABS(X(10)-X(11))-7.5
801 IF P11>=0 THEN P11=0 ELSE P11=P11
802 IF P12>=0 THEN P12=0 ELSE P12=P12
803 IF P13>=0 THEN P13=0 ELSE P13=P13
804 IF P14>=0 THEN P14=0 ELSE P14=P14
805 IF P15>=0 THEN P15=0 ELSE P15=P15
806 IF P16>=0 THEN P16=0 ELSE P16=P16
807 IF P17>=0 THEN P17=0 ELSE P17=P17
808 IF P18>=0 THEN P18=0 ELSE P18=P18
809 IF P19>=0 THEN P19=0 ELSE P19=P19
810 IF P20>=0 THEN P20=0 ELSE P20=P20
811 IF P21>=0 THEN P21=0 ELSE P21=P21
812 IF P22>=0 THEN P22=0 ELSE P22=P22
813 IF P23>=0 THEN P23=0 ELSE P23=P23
814 IF P24>=0 THEN P24=0 ELSE P24=P24
815 IF P25>=0 THEN P25=0 ELSE P25=P25
816 IF P26>=0 THEN P26=0 ELSE P26=P26
817 IF P27>=0 THEN P27=0 ELSE P27=P27
818 IF P28>=0 THEN P28=0 ELSE P28=P28
819 IF P29>=0 THEN P29=0 ELSE P29=P29
820 IF P30>=0 THEN P30=0 ELSE P30=P30
821 IF P31>=0 THEN P31=0 ELSE P31=P31
822 IF P32>=0 THEN P32=0 ELSE P32=P32
823 IF P33>=0 THEN P33=0 ELSE P33=P33
824 IF P34>=0 THEN P34=0 ELSE P34=P34
825 IF P35>=0 THEN P35=0 ELSE P35=P35
826 IF P36>=0 THEN P36=0 ELSE P36=P36
827 IF P37>=0 THEN P37=0 ELSE P37=P37
828 IF P38>=0 THEN P38=0 ELSE P38=P38
829 IF P39>=0 THEN P39=0 ELSE P39=P39
830 IF P40>=0 THEN P40=0 ELSE P40=P40
831 IF P41>=0 THEN P41=0 ELSE P41=P41
832 IF P42>=0 THEN P42=0 ELSE P42=P42
833 IF P43>=0 THEN P43=0 ELSE P43=P43
834 IF P44>=0 THEN P44=0 ELSE P44=P44
835 IF P45>=0 THEN P45=0 ELSE P45=P45
836 IF P46>=0 THEN P46=0 ELSE P46=P46
837 IF P47>=0 THEN P47=0 ELSE P47=P47
838 IF P48>=0 THEN P48=0 ELSE P48=P48
839 IF P49>=0 THEN P49=0 ELSE P49=P49
840 IF P50>=0 THEN P50=0 ELSE P50=P50
841 IF P51>=0 THEN P51=0 ELSE P51=P51
842 IF P52>=0 THEN P52=0 ELSE P52=P52
843 IF P53>=0 THEN P53=0 ELSE P53=P53
844 IF P54>=0 THEN P54=0 ELSE P54=P54
845 IF P55>=0 THEN P55=0 ELSE P55=P55
846 IF P56>=0 THEN P56=0 ELSE P56=P56
847 IF P57>=0 THEN P57=0 ELSE P57=P57
848 IF P58>=0 THEN P58=0 ELSE P58=P58
849 IF P59>=0 THEN P59=0 ELSE P59=P59
850 IF P60>=0 THEN P60=0 ELSE P60=P60
851 IF P61>=0 THEN P61=0 ELSE P61=P61
852 IF P62>=0 THEN P62=0 ELSE P62=P62
853 IF P63>=0 THEN P63=0 ELSE P63=P63
854 IF P64>=0 THEN P64=0 ELSE P64=P64
855 IF P65>=0 THEN P65=0 ELSE P65=P65
1201 PS11=555555!*P11+555555!*P12+555555!*P13+555555!*P14+555555!*P15+555555!*P16+555555!*P17+555555!*P18+555555!*P19+555555!*P20
1202 PS12=555555!*P21+555555!*P22+555555!*P23+555555!*P24+555555!*P25+555555!*P26+555555!*P27+555555!*P28+555555!*P29+555555!*P30
1203 PS13=555555!*P31+555555!*P32+555555!*P33+555555!*P34+555555!*P35+555555!*P36+555555!*P37+555555!*P38+555555!*P39+555555!*P40
1204 PS14=555555!*P41+555555!*P42+555555!*P43+555555!*P44+555555!*P45+555555!*P46+555555!*P47+555555!*P48+555555!*P49+555555!*P50
1205 PS15=555555!*P51+555555!*P52+555555!*P53+555555!*P54+555555!*P55+555555!*P56+555555!*P57+555555!*P58+555555!*P59+555555!*P60
1206 PS16=555555!*P61+555555!*P62+555555!*P63+555555!*P64+555555!*P65
1222 PS1=99*(PS11+PS12+PS13+PS14+PS15+PS16)
1248 P11=20*ABS(X(1)-X(2))+2*ABS(X(1)-X(3))+8*ABS(X(1)-X(4))+0*ABS(X(1)-X(5))+9*ABS(X(1)-X(6))+5*ABS(X(1)-X(7))+7*ABS(X(1)-X(8))+0*ABS(X(1)-X(9))+20*ABS(X(1)-X(10))+3*ABS(X(1)-X(11))
1252 P12=8*ABS(X(2)-X(3))+9*ABS(X(2)-X(4))+13*ABS(X(2)-X(5))+17*ABS(X(2)-X(6))+16*ABS(X(2)-X(7))+1*ABS(X(2)-X(8))+8*ABS(X(2)-X(9))+6*ABS(X(2)-X(10))+7*ABS(X(2)-X(11))
1253 P13=18*ABS(X(3)-X(4))+0*ABS(X(3)-X(5))+10*ABS(X(3)-X(6))+4*ABS(X(3)-X(7))+18*ABS(X(3)-X(8))+5*ABS(X(3)-X(9))+8*ABS(X(3)-X(10))+0*ABS(X(3)-X(11))
1254 P14=6*ABS(X(4)-X(5))+16*ABS(X(4)-X(6))+10*ABS(X(4)-X(7))+4*ABS(X(4)-X(8))+2*ABS(X(4)-X(9))+14*ABS(X(4)-X(10))+6*ABS(X(4)-X(11))
1255 P15=6*ABS(X(5)-X(6))+0*ABS(X(5)-X(7))+11*ABS(X(5)-X(8))+0*ABS(X(5)-X(9))+8*ABS(X(5)-X(10))+2*ABS(X(5)-X(11))
1256 P16=6*ABS(X(6)-X(7))+13*ABS(X(6)-X(8))+2*ABS(X(6)-X(9))+7*ABS(X(6)-X(10))+18*ABS(X(6)-X(11))+1*ABS(X(7)-X(8))+11*ABS(X(7)-X(9))+15*ABS(X(7)-X(10))+7*ABS(X(7)-X(11))
1257 P17=1*ABS(X(8)-X(9))+7*ABS(X(8)-X(10))+2*ABS(X(8)-X(11))+12*ABS(X(9)-X(10))+0*ABS(X(9)-X(11))+3*ABS(X(10)-X(11))
1447 P1=P11+P12+P13+P14+P15+P16+P17
1449 P=-P1+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P1
1454 FOR KLX=1 TO 11
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-7033 THEN 1916 ELSE 1999
1916 PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),A(6),M,PP1
1918 PRINT A(7),A(8),A(9),A(10),A(11)
1919 REM PRINT JJJJ,A(11)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solutions produced from JJJJ=-32000 through JJJJ=-31848 (in compressed form and to be interpreted in accordance with line 1916 and line 1918; copied manually from the computer monitor) are presented below.
-31948 20657.77 20651.77 20672.77 20667.77
20682.77 20677.77 -6933.58 6933.58
20644.77 20688.77 20639.27 20661.77 20698.27
-31940 54873.46 54862.46 54888.53 54883.53
54898.53 54893.53 -6978.203 6978.203
54869.46 54904.53 54854.95 54877.46 54914.03
-31886 54930.57 54919.57 54933.58 54938.58
54950.58 54945.58 -6997.481 6997.481
54912.57 54956.58 54907.07 54926.57 54966.08
-31883 12170.89 12176.89 12155.84 12160.84
12152.84 12147.84 -6953.424 6953.424
12183.9 12139.84 12189.41 12166.89 12130.34
-31848 35864.78 35975.78 35954.68 35959.68
35944.66 35949.67 -6979.793 6979.793
35982.78 35938.63 35988.29 35968.78 35929.12
The best candidate solution above is at JJJJ=-31948 with 6933.58 as the objective function value, and the output above was obtained in 6.2 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter.
If one makes changes to the computer program above, such as a change of changing line 90 to, for example, 90 FOR INEW=1 TO 12, one may or may not obtain 6933.58. This point is relevant to the present problem and beyond it. That leads to a general remedy that in general, in order to increase the chance of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128. Running several computers simultaneously can mitigate the possible danger of missed optimality and can produce a usable solution faster than just running one computer.
References
[1] A. R. S. Amaral, "On the Exact Solution of a Facility Layout Problem," European Journal of Operational Research, 173(2) 508-518 (2006).
[2] A. R. S. Amaral, "An Exact Approach to the One-Dimensional Facility Layout Problem," Operations Research, Vol. 56, No. 4, July-August 2008, pp. 1026-1033.
[3] W. C. Conley, Optimization: A Simplified Approach. Petrocelli, Princeton, New Jersey, 1981, pp. 229-232.
[4] S. Heragu, Facilities Design. PWS Publishing Company, a division of International Thomson Publishing Inc., Boston, MA 02116, 1997.

A Computer Program Applied to a Layout Problem Involving Facilities with Unequal Areas

Jsun Yui Wong
Benefitting from the other computer programs of the present blog and the computer program on pages 229-232 of Conley [3], the following computer program, using Example 4 of Chapter 5 of Heragu [4, pp. 137-138] as a concrete illustration, and its output suggest that the program below can be useful for producing solutions from integer programming formulations.
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(111)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
25 B(1)=0:B(2)=0:B(3)=0:B(4)=0:B(5)=0
26 B(6)=0:B(7)=0:B(8)=0:B(9)=0:B(10)=0
37 N(1)=70:N(2)=70:N(3)=70:N(4)=70:N(5)=70
38 N(6)=70:N(7)=70:N(8)=70:N(9)=70:N(10)=70
61 FOR KLQ=1 TO 10
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 10
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 5
94 FOR J=INEW*2 TO 0 STEP -2
102 FOR JJ=0 TO 10
111 KKLL=FIX(1+10*RND)
128 FOR I=1 TO 20
129 FOR KKQQ=1 TO 10
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 10
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
305 KLPS=FIX(1+KKLL*RND)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+10*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 461
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 461
355 X(JJ)=N(JJ)
461 REM
481 IF RND<1/10 THEN Z12=FIX(RND*2) ELSE IF RND<1/9 THEN Z13=FIX(RND*2) ELSE IF RND<1/8 THEN Z14=FIX(RND*2) ELSE IF RND<1/7 THEN Z15=FIX(RND*2) ELSE IF RND<1/6 THEN Z23=FIX(RND*2) ELSE GOTO 487
485 GOTO 561
487 IF RND<1/5 THEN Z24=FIX(RND*2) ELSE IF RND<1/4 THEN Z25=FIX(RND*2) ELSE IF RND<1/3 THEN Z34=FIX(RND*2) ELSE IF RND<1/2 THEN Z35=FIX(RND*2) ELSE IF RND<1/1 THEN Z45=FIX(RND*2)
561 P11=ABS(X(1)-X(2))-25+5555*Z12
562 P12=ABS(X(1)-X(3))-30+5555*Z13
563 P13=ABS(X(1)-X(4))-27.5+5555*Z14
564 P14=ABS(X(1)-X(5))-30+5555*Z15
565 P15=ABS(X(2)-X(3))-30+5555*Z23
566 P16=ABS(X(2)-X(4))-27.5+5555*Z24
567 P17=ABS(X(2)-X(5))-30+5555*Z25
568 P18=ABS(X(3)-X(4))-32.5+5555*Z34
569 P19=ABS(X(3)-X(5))-35+5555*Z35
570 P20=ABS(X(4)-X(5))-32.5+5555*Z45
581 P21=ABS(X(6)-X(7))-20+5555*(1-Z12)
582 P22=ABS(X(6)-X(8))-25+5555*(1-Z13)
583 P23=ABS(X(6)-X(9))-20+5555*(1-Z14)
584 P24=ABS(X(6)-X(10))-20+5555*(1-Z15)
585 P25=ABS(X(7)-X(8))-25+5555*(1-Z23)
586 P26=ABS(X(7)-X(9))-20+5555*(1-Z24)
587 P27=ABS(X(7)-X(10))-20+5555*(1-Z25)
588 P28=ABS(X(8)-X(9))-25+5555*(1-Z34)
589 P29=ABS(X(8)-X(10))-25+5555*(1-Z35)
590 P30=ABS(X(9)-X(10))-20+5555*(1-Z45)
801 IF P11<0 THEN P11=P11 ELSE P11=0
802 IF P12<0 THEN P12=P12 ELSE P12=0
803 IF P13<0 THEN P13=P13 ELSE P13=0
804 IF P14<0 THEN P14=P14 ELSE P14=0
805 IF P15<0 THEN P15=P15 ELSE P15=0
806 IF P16<0 THEN P16=P16 ELSE P16=0
807 IF P17<0 THEN P17=P17 ELSE P17=0
808 IF P18<0 THEN P18=P18 ELSE P18=0
809 IF P19<0 THEN P19=P19 ELSE P19=0
810 IF P20<0 THEN P20=P20 ELSE P20=0
811 IF P21<0 THEN P21=P21 ELSE P21=0
812 IF P22<0 THEN P22=P22 ELSE P22=0
813 IF P23<0 THEN P23=P23 ELSE P23=0
814 IF P24<0 THEN P24=P24 ELSE P24=0
815 IF P25<0 THEN P25=P25 ELSE P25=0
816 IF P26<0 THEN P26=P26 ELSE P26=0
817 IF P27<0 THEN P27=P27 ELSE P27=0
818 IF P28<0 THEN P28=P28 ELSE P28=0
819 IF P29<0 THEN P29=P29 ELSE P29=0
820 IF P30<0 THEN P30=P30 ELSE P30=0
1201 PS1A=555555!*P11+555555!*P12+555555!*P13+555555!*P14+555555!*P15+555555!*P16+555555!*P17+555555!*P18+555555!*P19+555555!*P20
1203 PS1B=555555!*P21+555555!*P22+555555!*P23+555555!*P24+555555!*P25+555555!*P26+555555!*P27+555555!*P28+555555!*P29+555555!*P30
1222 PS1=PS1A+PS1B
1447 P1A=10*ABS(X(1)-X(2))+15*ABS(X(1)-X(3))+20*ABS(X(1)-X(4))+30*ABS(X(2)-X(3))+35*ABS(X(2)-X(4))+10*ABS(X(2)-X(5))+10*ABS(X(3)-X(4))+20*ABS(X(3)-X(5))+15*ABS(X(4)-X(5))
1448 P1B=10*ABS(X(6)-X(7))+15*ABS(X(6)-X(8))+20*ABS(X(6)-X(9))+30*ABS(X(7)-X(8))+35*ABS(X(7)-X(9))+10*ABS(X(7)-X(10))+10*ABS(X(8)-X(9))+20*ABS(X(8)-X(10))+15*ABS(X(9)-X(10))
1449 P1=P1A+P1B
1450 P=-P1+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P1
1454 FOR KLX=1 TO 10
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1511 ZZ12=Z12
1512 ZZ13=Z13
1513 ZZ14=Z14
1514 ZZ15=Z15
1515 ZZ23=Z23
1516 ZZ24=Z24
1517 ZZ25=Z25
1518 ZZ34=Z34
1519 ZZ35=Z35
1520 ZZ45=Z45
1557 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1711 NEXT INEW
1888 NEXT JJJ
1890 IF M>-5600 THEN 1916 ELSE 1999
1916 PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),M,PP1
1917 PRINT A(6),A(7),A(8),A(9),A(10)
1919 PRINT ZZ12,ZZ13,ZZ14,ZZ15,ZZ23
1920 PRINT ZZ24,ZZ25,ZZ34,ZZ35,ZZ45
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solutions from JJJJ=-32000 through JJJJ=-31568 (in compressed form and to be interpreted in accordance with line 1916 through line 1920) are presented below.
-31942 66.61713 36.6411 36.61562 64.14357
36.61276 -5528.857 5528.857
5.659483 25.72971 .7187784 25.7268 45.74612
0 0 1 0 1
0 1 1 1 1
-31922 36.15961 36.05508 5.967561 36.10956
3.516773 -5570.057 5570.057
48.14135 27.89727 32.98768 7.891593 7.773934
1 0 1 0 0
1 0 1 1 0
-31568 5.338229 35.01043 35.36419 7.4749
34.92083 -5555.654 5555.654
5.998369 26.88303 1.872796 26.87574 46.92579
1 0 1 1 1
0 1 1 1 1
The best candidate solution above is at JJJJ=-31942 with 5528.857 as the objective function value, and the output above was obtained in 20 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter.
If one makes changes to the computer program above, such as a change of changing line 128 to, for example, 128 FOR I=1 TO 19, one may or may not obtain 5528.857, which may or may not optimal. This point is relevant to the present problem AND beyond it. That leads to a general remedy that in general, in order to increase the chance of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128. Running several computers simultaneously can mitigate the possible danger of missed optimality and can produce a usable solution faster than just running one computer.
References
[1] A. R. S. Amaral, "On the exact solution of a facility layout problem," European Journal of Operational Research, 173(2) 508-518 (2006).
[2] A. R. S. Amaral, "An Exact Approach to the One-Dimensional Facility Layout Problem," Operations Research, Vol. 56, No. 4, July-August 2008, pp. 1026-1033.
[3] W. C. Conley, Optimization: A Simplified Approach. Petrocelli, Princeton, New Jersey, 1981, pp. 229-232.
[4] S. Heragu, Facilities Design. PWS Publishing Company, a division of International Thomson Publishing Inc., Boston, MA 02116, 1997, pp. 117-123.

A Computer Program for a Facility Layout Problem

Jsun Yui Wong
Benefitting from the other computer programs of the present blog and the computer program on pages 229-232 of Conley [2], the following computer program, using Example 1 of Chapter 5 of Heragu [3, pp. 117-123] as a concrete illustration, and its output suggest that the program below can be useful for producing solutions from integer programming formulations.
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(111)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
25 B(1)=0:B(2)=0:B(3)=0:B(4)=0
26 B(5)=0
37 N(1)=70:N(2)=70:N(3)=70:N(4)=70
38 N(5)=70
61 FOR KLQ=1 TO 5
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 5
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 5
94 FOR J=INEW*2 TO 0 STEP -2
102 FOR JJ=0 TO 5
111 KKLL=FIX(1+5*RND)
128 FOR I=1 TO 15
129 FOR KKQQ=1 TO 5
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 5
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
305 KLPS=FIX(1+KKLL*RND)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+5*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 561
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 561
355 X(JJ)=N(JJ)
561 P11=ABS(X(1)-X(2))-15
562 P12=ABS(X(1)-X(3))-15
563 P13=ABS(X(1)-X(4))-20
564 P14=ABS(X(1)-X(5))-17.5
565 P15=ABS(X(2)-X(3))-10
566 P16=ABS(X(2)-X(4))-15
567 P17=ABS(X(2)-X(5))-12.5
568 P18=ABS(X(3)-X(4))-15
569 P19=ABS(X(3)-X(5))-12.5
570 P20=ABS(X(4)-X(5))-17.5
801 IF P11<0 THEN P11=P11 ELSE P11=0
802 IF P12<0 THEN P12=P12 ELSE P12=0
803 IF P13<0 THEN P13=P13 ELSE P13=0
804 IF P14<0 THEN P14=P14 ELSE P14=0
805 IF P15<0 THEN P15=P15 ELSE P15=0
806 IF P16<0 THEN P16=P16 ELSE P16=0
807 IF P17<0 THEN P17=P17 ELSE P17=0
808 IF P18<0 THEN P18=P18 ELSE P18=0
809 IF P19<0 THEN P19=P19 ELSE P19=0
810 IF P20<0 THEN P20=P20 ELSE P20=0
1201 PS1=555555!*P11+555555!*P12+555555!*P13+555555!*P14+555555!*P15+555555!*P16+555555!*P17+555555!*P18+555555!*P19+555555!*P20
1448 P1=12*ABS(X(1)-X(2))+8*ABS(X(1)-X(3))+20*ABS(X(1)-X(4))+4*ABS(X(2)-X(3))+6*ABS(X(2)-X(4))+2*ABS(X(2)-X(5))+10*ABS(X(3)-X(4))+3*ABS(X(4)-X(5))
1449 P=-P1+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P1
1454 FOR KLX=1 TO 5
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-1658 THEN 1916 ELSE 1999
1916 PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),M,PP1
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solutions from JJJJ=-32000 through JJJJ=-31976 (in compressed form and to be interpreted in accordance with line 1916) are presented below.
-31998 44.28932 29.2874 79.29092 64.28973
12.02846 -1611.386 1611.386
-31997 49.80558 64.80558 14.80556 29.80557
77.30559 -1587.5 1587.5
-31977 43.83988 58.83988 8.839874 23.83988
71.33991 -1587.5 1587.5
-31976 37.1569 22.1569 72.1569 57.1569
9.656881 -1587.5 1587.5
The best candidate solutions above are at JJJJ=-31997, JJJJ=-31977, and JJJJ=-31976 with 1587.5 as the objective function value, and the output above was obtained in 15 minutes on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter. One can conclude that this computer program can be useful as a model for other one-dimensional layout problem instances; perhaps it can also be useful for problems of similar nature.
References
[1] A. R. S. Amaral, "On the exact solution of a facility layout problem," European Journal of Operational Research, 173(2) 508-518 (2006).
[2] W. C. Conley, Optimization: A Simplified Approach. Petrocelli, Princeton, New Jersey, 1981, pp. 229-232.
[3] S. Heragu, Facilities Design. PWS Publishing Company, a division of International Thomson Publishing Inc., Boston, MA 02116, 1997, pp. 117-123.

Conversions of Values Should Precede Checking for Feasibility

Conversions of values should precede checking for feasibility. For example, line 503 and line 504 in the present blog's post "An Integer Programming Computer Program Applied to a Nonlinear Problem with General Integer Variables and Continuous Variables" should become line 461 and line 462, respectively. Then line 461 and line 462 of the same post "An Integer Programming Computer Program Applied to a Nonlinear Problem with General Integer Variables and Continuous Variables" should become line 503 and line 504, respectively.
Also, a candidate solution should be checked to make sure all constraints are satisfied. Then it is a valid candidate solution.