An Integer-Programming Computer Program Applied to a One-Dimensional Space
Allocation Problem, Second Edition
Jsun Yui Wong
The computer program listed below seeks to solve Problem S8 of Amaral (2006),
which is a problem from Simmons (1969). In order to have integer locations, the
department lengths used in the computer program below have been made twice as
long as the given department lengths.
0 DEFINT A-Z
15 DIM X(11),A(11)
16 DIM TM(24,24),HR(24,24),HS(24,24)
21 FOR IW=1 TO 7
23 FOR JW=IW+1 TO 8
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
32 DATA 5,6,7,8,5,9,6,7,8,9,6,10,7,9,10,7,11,8,11,8,12,9,9,13,10,10,7,11
41 FOR IZ=1 TO 7
43 FOR JZ=IZ+1 TO 8
46 READ HS(IZ,JZ)
48 NEXT JZ
49 NEXT IZ
52 DATA 6,4,1,7,3,5,0,1,2,5,2,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-32000
85 FOR II=1 TO 8
88 A(II)=RND*99
89 NEXT II
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 8
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*8)
234 X(IJL)=RND*99
533 FOR IX=1 TO 7
534 FOR JX=IX+1 TO 8
543 IF ABS(X(IX)-X(JX))-HR(IX,JX)<-.0001 THEN TM(IX,JX)=1000 ELSE TM(IX,JX)=0
545 NEXT JX
547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 7
1614 FOR IR2=IR1+1 TO 8
1616 SUMTL=SUMTL+TM(IR1,IR2)
1617 NEXT IR2
1619 NEXT IR1
1631 SUMUL=0
1632 FOR IS1=1 TO 7
1634 FOR IS2=IS1+1 TO 8
1636 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1637 NEXT IS2
1639 NEXT IS1
1645 P=-SUMUL-SUMTL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-1605 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions through JJJJ=-21042 are presented below. What immediately follows is a manual copy from the computer screen.
67 72 49 26 59
34 82 41 -1602 -31520
38 33 56 79 46
71 23 64 -1602 -25855
60 65 42 19 52
27 75 34 -1602 -25642
19 14 37 60 27
52 4 45 -1602 -22630
54 59 36 13 46
21 69 28 -1602 -22263
62 67 44 21 54
29 77 36 -1602 -22006
75 80 57 34 67
42 90 49 -1602 -21959
70 75 52 29 62
37 85 44 -1602 -21042
1602 is optimal. Interpreted in accordance with line 1912 and line 1914, the output through JJJJ=-21042 was produced in three hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Amaral, A. R. S., "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518 (2006).
Simmons, D. M., "One-dimensional space allocation: an ordering algorithm," Operations Research 17, 812-826 (1969).
