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.