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