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